A computational study of exact knapsack separation for the generalized assignment problem

被引:36
作者
Avella, Pasquale [2 ]
Boccia, Maurizio [2 ]
Vasilyev, Igor [1 ]
机构
[1] Russian Acad Sci, Inst Syst Dynam & Control Theory, Siberian Branch, Irkutsk 664033, Russia
[2] Univ Sannio, Res Ctr Software Technol, I-82100 Benevento, Italy
关键词
Generalized assignment problem; Cutting plane algorithm; Exact separation; FENCHEL CUTTING PLANES; VALID INEQUALITIES; INTEGER PROGRAMS; PRICE ALGORITHM; TABU SEARCH; FACETS; CUTS;
D O I
10.1007/s10589-008-9183-8
中图分类号
C93 [管理学]; O22 [运筹学];
学科分类号
070105 ; 12 ; 1201 ; 1202 ; 120202 ;
摘要
The Generalized Assignment Problem is a well-known NP-hard combinatorial optimization problem which consists of minimizing the assignment costs of a set of jobs to a set of machines satisfying capacity constraints. Most of the existing algorithms are of a Branch-and-Price type, with lower bounds computed through Dantzig-Wolfe reformulation and column generation. In this paper we propose a cutting plane algorithm working in the space of the variables of the basic formulation, whose core is an exact separation procedure for the knapsack polytopes induced by the capacity constraints. We show that an efficient implementation of the exact separation procedure allows to deal with large-scale instances and to solve to optimality several previously unsolved instances.
引用
收藏
页码:543 / 555
页数:13
相关论文
共 26 条
[1]   Independent and cooperative parallel search methods for the generalized assignment problem [J].
Asahiro, Y ;
Ishibashi, M ;
Yamashita, M .
OPTIMIZATION METHODS & SOFTWARE, 2003, 18 (02) :129-141
[2]   OR-LIBRARY - DISTRIBUTING TEST PROBLEMS BY ELECTRONIC MAIL [J].
BEASLEY, JE .
JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY, 1990, 41 (11) :1069-1072
[3]  
BONAMI MP, 2003, THESIS U PARIS 6
[4]   GENERATING FENCHEL CUTTING PLANES FOR KNAPSACK POLYHEDRA [J].
Boyd, E. A. .
SIAM JOURNAL ON OPTIMIZATION, 1993, 3 (04) :734-750
[5]  
Boyd E.A, 1993, IPCO, P209
[7]   FENCHEL CUTTING PLANES FOR INTEGER PROGRAMS [J].
BOYD, EA .
OPERATIONS RESEARCH, 1994, 42 (01) :53-64
[8]   A branch-and-price algorithm for the capacitated p-median problem [J].
Ceselli, A ;
Righini, G .
NETWORKS, 2005, 45 (03) :125-142
[9]   A genetic algorithm for the generalised assignment problem [J].
Chu, PC ;
Beasley, JE .
COMPUTERS & OPERATIONS RESEARCH, 1997, 24 (01) :17-23
[10]   A convex-analysis perspective on disjunctive cuts [J].
Cornuéjols, G ;
Lemaréchal, C .
MATHEMATICAL PROGRAMMING, 2006, 106 (03) :567-586