Optimization Online


Lifting for Conic Mixed-Integer Programming

Alper Atamturk (atamturk***at***berkeley.edu)
Vishnu Narayanan (vishnu***at***ieor.berkeley.edu)

Abstract: Lifting is a procedure for deriving valid inequalities for mixed-integer sets from valid inequalities for suitable restrictions of those sets. Lifting has been shown to be very effective in developing strong valid inequalities for linear integer programming and it has been successfully used to solve such problems with branch-and-cut algorithms. Here we generalize the theory of lifting to conic integer programming, i.e., integer programs with conic constraints. We show how to derive conic valid inequalities for a conic integer program from conic inequalities valid for its lower-dimensional restrictions. In order to simplify computations, we also discuss sequence-independent lifting for conic integer programs. When the cones are restricted to nonnegative orthants, conic lifting reduces to the lifting for linear integer programming.

Keywords: Valid inequalities, conic optimization, integer programming

Category 1: Integer Programming

Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming )

Citation: Forthcoming in Mathematical Programming. Check http://www.ieor.berkeley.edu/~atamturk/


Entry Submitted: 11/28/2007
Entry Accepted: 11/29/2007
Entry Last Modified: 05/21/2009

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