  


Conic MixedInteger Rounding Cuts
Alper Atamturk (atamturkberkeley.edu) Abstract: A conic integer program is an integer programming problem with conic constraints. Many problems in finance, engineering, statistical learning, and probabilistic optimization are modeled using conic constraints. Here we study mixedinteger sets defined by secondorder conic constraints. We introduce generalpurpose cuts for conic mixedinteger programming based on polyhedral conic substructures of secondorder conic sets. These cuts can be readily incorporated in branchandbound algorithms that solve either secondorder conic programming or linear programming relaxations of conic integer programs at the nodes of the branchandbound tree. Central to our approach is a reformulation of the secondorder conic constraints with polyhedral secondorder conic constraints in a higher dimensional space. In this representation the cuts we develop are linear, even though they are nonlinear in the original space of variables. This feature leads to a computationally efficient implementation of nonlinear cuts for conic mixedinteger programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured secondorder conic mixedinteger problems as well as meanvariance capital budgeting problems and leastsquares estimation problems with binary inputs. Our computational experiments show that conic mixedinteger rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixedinteger programs and, hence, improving their solvability. Keywords: Category 1: Integer Programming ((Mixed) Integer Linear Programming ) Category 2: Integer Programming ((Mixed) Integer Nonlinear Programming ) Citation: Forthcoming in Mathematical Programming. Check http://www.ieor.berkeley.edu/~atamturk/ Download: Entry Submitted: 06/26/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  