A branch-and-cut method for 0-1 mixed convex programming

被引:181
作者
Stubbs, RA [1 ]
Mehrotra, S [1 ]
机构
[1] Northwestern Univ, MLSB, Dept IE MS, Evanston, IL 60208 USA
关键词
mixed integer programming; convex programming;
D O I
10.1007/s101070050103
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
We generalize the disjunctive approach of Balas, Ceria, and Cornuejols [2] and develop a branch-and-cut method for solving 0-1 convex programming problems. We show that cuts can be generated by solving a single convex program. We show how to construct regions similar to those of Sherari and Adams [20] and Lovasz and Schrijver [12] for the convex case. Finally, we give some preliminary computational results for our method.
引用
收藏
页码:515 / 532
页数:18
相关论文
共 21 条
[1]   LINEARIZATION STRATEGIES FOR A CLASS OF ZERO-ONE MIXED INTEGER PROGRAMMING-PROBLEMS [J].
ADAMS, WP ;
SHERALI, HD .
OPERATIONS RESEARCH, 1990, 38 (02) :217-226
[2]   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
[3]   Mixed 0-1 programming by lift-and-project in a branch-and-cut framework [J].
Balas, E ;
Ceria, S ;
Cornuejols, G .
MANAGEMENT SCIENCE, 1996, 42 (09) :1229-1246
[4]  
Bazaraa M.S., 2013, Nonlinear Programming-Theory and Algorithms, V3rd
[5]   AN OUTER-APPROXIMATION ALGORITHM FOR A CLASS OF MIXED-INTEGER NONLINEAR PROGRAMS [J].
DURAN, MA ;
GROSSMANN, IE .
MATHEMATICAL PROGRAMMING, 1986, 36 (03) :307-339
[6]  
DURAN MA, 1984, THESIS CARNEGIE MELL
[7]  
Floudas C.A., 1995, NONLINEAR MIXED INTE
[8]  
Geoffrion A. M., 1972, Journal of Optimization Theory and Applications, V10, P237, DOI 10.1007/BF00934810
[9]  
Hansen P., 1993, ORSA Journal on Computing, V5, P97, DOI 10.1287/ijoc.5.2.97
[10]  
HIRIARTURUTY JB, 1993, CONVEX ANAL MINIMIZA, V305