Summary: BCOL RESEARCH REPORT 06.03
Industrial Engineering & Operations Research
University of California, Berkeley, CA
Forthcoming in Mathematical Programming
CONIC MIXED-INTEGER ROUNDING CUTS
ALPER ATAMTšURK AND VISHNU NARAYANAN
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 con-
straints 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 com-
putationally efficient implementation of nonlinear cuts for conic mixed-integer