Lifting Inequalities: A framework for generating strong cuts in nonlinear programs

In this paper, we propose lifting techniques for generating strong cuts for nonlinear programs that are globally-valid. The theory is geometric and provides intuition into lifting-based cut generation procedures. As a special case, we find short proofs of earlier results on lifting techniques for mixed-integer programs. Using convex extensions, we obtain conditions that allow sequence-independent liftings in nonlinear settings. Our framework subsumes the superadditive lifting theory for integer programs. We specialize our lifting results to mixed-integer nonlinear knapsack sets and, in particular, derive facets for mixed-integer bilinear knapsack sets. Finally, we show that these facet-defining inequalities are hard to obtain using traditional integer programming techniques.


Accepted, Mathematical Programming (2008)