  


Lifting for Conic MixedInteger Programming
Alper Atamturk (atamturkberkeley.edu) Abstract: Lifting is a procedure for deriving valid inequalities for mixedinteger 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 branchandcut 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 lowerdimensional restrictions. In order to simplify computations, we also discuss sequenceindependent 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/ Download: Entry Submitted: 11/28/2007 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  