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

Jean-Philippe Richard (jpricharecn.purdue.edu)
Mohit Tawarmalani (mtawarmapurdue.edu)

Abstract: 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.

Keywords: nonlinear mixed-integer programming, cutting planes, bilinear knapsacks, convex extensions, sequence-independent lifting, elementary closures

Category 1: Global Optimization

Category 2: Integer Programming

Category 3: Nonlinear Optimization

Citation: Accepted, Mathematical Programming (2008)

Download:

Entry Submitted: 08/17/2007
Entry Accepted: 09/01/2007
Entry Last Modified: 05/09/2008

Modify/Update this entry