Optimization Online


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

Jean-Philippe Richard (jprichar***at***ecn.purdue.edu)
Mohit Tawarmalani (mtawarma***at***purdue.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)


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

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society