Collaborative Research: Generating Stronger Cuts for Nonlinear Programs Via Orthogonal Disjunctions and Lifting Techniques

The award is funded under American Recovery and Reinvestment Act of 2009 (Public Law 111-5).

The expressive power of nonlinear programs allows the formulation of a remarkable number of application problems from business, science, engineering, and economics. In the presence of nonconvexity, global optimization of such programs poses unmistakable challenges. The objective of this project is to explore how lifting and orthogonal disjunctions can generate computationally tractable cutting planes and convex relaxations for nonlinear programs. The proposed research departs from existing techniques in two crucial dimensions. First, instead of relaxing the left-hand-side and right-hand-side of an inequality independently of each other, tighter relaxations are derived by considering them simultaneously. Second, the techniques do not add new variables, a feature with obvious computational advantages over existing approaches. The objective is to (i) derive, preferably in closed-form, new strong cuts or relaxations for commonly occurring nonlinear structures in areas such as process design and bi-clustering, (ii) characterize structures of nonconvex inequalities where the proposed techniques yield provably tight relaxations, and (iii) design computational procedures that automatically generate strong cuts and evaluate the impact of integrating them in a branch-and-bound algorithm.

If successful, this project will provide an impetus to theoretical, algorithmic, and computational advances in deterministic global optimization through research on convexification procedures. A significant expected outcome of this research project is the improvement of the branch-and-bound algorithm for nonconvex programs through the derivation of new and stronger convex relaxations. This project will invigorate the research at the interface of integer programming and global optimization and benefit both communities. The proposed relaxation schemes will be implemented in software enabling the solution of larger nonconvex problems, which, in turn, will impact many application contexts in science, engineering, business, and economics. Work on solving specially-structured problems will bring operational efficiencies in those contexts.