Solving multiple knapsack problems by cutting planes

被引:45
作者
Ferreira, CE [1 ]
Martin, A [1 ]
Weismantel, R [1 ]
机构
[1] KONRAD ZUSE ZENTRUM INFORMAT TECH BERLIN,D-10711 BERLIN,GERMANY
关键词
multiple knapsack problem; cutting planes; branch and cut; separation;
D O I
10.1137/S1052623493254455
中图分类号
O29 [应用数学];
学科分类号
070104 ;
摘要
In this paper ve consider the multiple knapsack problem, which is defined as follows: given a set N of items with weights f(i), i is an element of N, a set M of knapsacks with capacities F-k, k is an element of M, and a profit function c(ik),i is an element of N, k is an element of M, find an assignment of a subset of the set of items to the set of knapsacks that yields minimum cost. We consider the multiple knapsack problem from a polyhedral point of view. The inequalities that we describe here serve as the theoretical basis for a cutting plane algorithm. We present some of the implementation details of this algorithm, including a discussion and evaluation of different separation and primal heuristics. Our algorithm is applied to practical problem instances arising in the design of main frame computers, in the layout of electronic circuits, and in sugar cane alcohol production.
引用
收藏
页码:858 / 877
页数:20
相关论文
共 18 条
[1]   FACETS OF KNAPSACK POLYTOPE [J].
BALAS, E .
MATHEMATICAL PROGRAMMING, 1975, 8 (02) :146-164
[2]   FACETS OF KNAPSACK POLYTOPE FROM MINIMAL COVERS [J].
BALAS, E ;
ZEMEL, E .
SIAM JOURNAL ON APPLIED MATHEMATICS, 1978, 34 (01) :119-148
[3]  
BOYD EA, 1992, NETWORKS, V22, P503, DOI 10.1002/net.3230220507
[4]   SOLVING LARGE-SCALE ZERO-ONE LINEAR-PROGRAMMING PROBLEMS [J].
CROWDER, H ;
JOHNSON, EL ;
PADBERG, M .
OPERATIONS RESEARCH, 1983, 31 (05) :803-834
[5]  
Ferreira C. E., 1993, ZOR, Methods and Models of Operations Research, V38, P77, DOI 10.1007/BF01416008
[6]  
FERREIRA CE, 1994, THESIS TECHNISCHE U
[7]  
Fiduccia C. M., 1982, P IEEE ACM DES AUT C, P175, DOI DOI 10.1109/DAC.1982.1585498
[8]   THE GENERALIZED ASSIGNMENT PROBLEM - VALID INEQUALITIES AND FACETS [J].
GOTTLIEB, ES ;
RAO, MR .
MATHEMATICAL PROGRAMMING, 1990, 46 (01) :31-52
[9]   (1,K)-CONFIGURATION FACETS FOR THE GENERALIZED ASSIGNMENT PROBLEM [J].
GOTTLIEB, ES ;
RAO, MR .
MATHEMATICAL PROGRAMMING, 1990, 46 (01) :53-60
[10]   FACET OF REGULAR 0-1 POLYTOPES [J].
HAMMER, PL ;
JOHNSON, EL ;
PELED, UN .
MATHEMATICAL PROGRAMMING, 1975, 8 (02) :179-206