Conic mixed-integer rounding cuts

被引:73
作者
Atamtuerk, Alper [1 ]
Narayanan, Vishnu [1 ]
机构
[1] Univ Calif Berkeley, Dept Ind Engn & Operat Res, Berkeley, CA 94720 USA
基金
美国国家科学基金会;
关键词
Conic programming; Integer programming; Mixed-integer rounding; Branch-and-cut algorithms; SEMIDEFINITE; OPTIMIZATION; RELAXATIONS; ALGORITHMS; MATRICES; CONES;
D O I
10.1007/s10107-008-0239-4
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:1 / 20
页数:20
相关论文
共 45 条
[1]   Second-order cone programming [J].
Alizadeh, F ;
Goldfarb, D .
MATHEMATICAL PROGRAMMING, 2003, 95 (01) :3-51
[2]   INTERIOR-POINT METHODS IN SEMIDEFINITE PROGRAMMING WITH APPLICATIONS TO COMBINATORIAL OPTIMIZATION [J].
ALIZADEH, F .
SIAM JOURNAL ON OPTIMIZATION, 1995, 5 (01) :13-51
[3]  
[Anonymous], 1987, THEORY LINEAR INTEGE
[4]  
[Anonymous], 2006, ANLMCSP13740906
[5]  
[Anonymous], ACM T MATH SOF UNPUB
[6]  
ATAMTURK A, 2007, BCOL0704 IEOR U CAL
[7]   A LIFT-AND-PROJECT CUTTING PLANE ALGORITHM FOR MIXED 0-1 PROGRAMS [J].
BALAS, E ;
CERIA, S ;
CORNUEJOLS, G .
MATHEMATICAL PROGRAMMING, 1993, 58 (03) :295-324
[8]  
Balas E., 1979, ANN DISCRETE MATH, V5, P3, DOI DOI 10.1016/S0167-5060(08)70342-X
[9]   SOME PROBLEMS IN APPLYING CONTINUOUS PORTFOLIO SELECTION MODEL TO DISCRETE CAPITAL-BUDGETING PROBLEM [J].
BAUM, S ;
CARLSON, RC ;
JUCKER, JV .
JOURNAL OF FINANCIAL AND QUANTITATIVE ANALYSIS, 1978, 13 (02) :333-344
[10]  
Ben-Tal A., 2001, Lectures on modern convex optimization, V2