Conic Mixed-Integer Rounding Cuts

Alper Atamturk (atamturkberkeley.edu)
Vishnu Narayanan (vishnuieor.berkeley.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 mixed-integer sets defined by second-order conic constraints. We introduce general-purpose cuts for conic mixed-integer programming based on polyhedral conic substructures of second-order conic sets. These cuts can be readily incorporated in branch-and-bound algorithms that solve either second-order conic programming or linear programming relaxations of conic integer programs at the nodes of the branch-and-bound tree. Central to our approach is a reformulation of the second-order conic constraints with polyhedral second-order 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 mixed-integer programming. The reformulation also allows the use of polyhedral methods for conic integer programming. We report computational results on solving unstructured second-order conic mixed-integer problems as well as mean-variance capital budgeting problems and least-squares estimation problems with binary inputs. Our computational experiments show that conic mixed-integer rounding cuts are very effective in reducing the integrality gap of continuous relaxations of conic mixed-integer programs and, hence, improving their solvability.

Keywords:

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

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

Citation: Research Report BCOL.06.03, IEOR, University of California-Berkeley. December 2006. Revised March 2008.

Download: [PDF]

Entry Submitted: 06/26/2007
Entry Accepted: 06/27/2007
Entry Last Modified: 04/15/2008

Modify/Update this entry