GENERATING FENCHEL CUTTING PLANES FOR KNAPSACK POLYHEDRA

被引:31
作者
Boyd, E. A. [1 ]
机构
[1] Texas A&M Univ, Dept Ind Engn, College Stn, TX 77843 USA
基金
美国国家科学基金会;
关键词
cutting planes; integer programming; knapsack polyhedron;
D O I
10.1137/0803038
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
The author recently proposed a class of cutting planes for integer programs called Fenchel cuts which distinguish themselves from more conventional cuts in that they are generated by directly seeking to solve the separation problem rather than by using explicit knowledge of the polyhedral structure of the integer program. An algorithm for generating Fenchel cuts is presented and described in detail for the separation problem associated with knapsack polyhedra. Computational results are presented for a collection of real-world integer programs to demonstrate the effectiveness of the cutting planes.
引用
收藏
页码:734 / 750
页数:17
相关论文
共 26 条
[1]  
[Anonymous], 1989, HDB OPERATIONS RES M, DOI [DOI 10.1016/S0927-0507(89)01008-X, 10.1016/s0927-0507(89)01008-x]
[2]  
[Anonymous], 1988, GEOMETRIC ALGORITHMS, DOI DOI 10.1007/978-3-642-97881-4
[3]  
BERTSEKAS D., 1979, LIDSR919 MIT DEP EL
[4]  
BIXBY R. E., 1991, COMPUTATIONAL UNPUB
[5]  
BOYD E. A., OPER RES IN PRESS
[6]  
BOYD E. A., 1991, TR9121 RIC U DEP MAT
[7]  
BOYD E. A., SIAM J OPTI IN PRESS
[8]   SOLVING LARGE-SCALE ZERO-ONE LINEAR-PROGRAMMING PROBLEMS [J].
CROWDER, H ;
JOHNSON, EL ;
PADBERG, M .
OPERATIONS RESEARCH, 1983, 31 (05) :803-834
[9]   THE LAGRANGIAN-RELAXATION METHOD FOR SOLVING INTEGER PROGRAMMING-PROBLEMS [J].
FISHER, ML .
MANAGEMENT SCIENCE, 1981, 27 (01) :1-18
[10]  
FORRES J., 1991, STEEPEST EDGE SIMPLE