A computational study of exact knapsack separation for the generalized assignment problem. (English) Zbl 1190.90153
Summary: 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.
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.
References:
| [1] | Asahiro, Y., Ishibashi, M., Yamashita, M.: Independent and cooperative parallel search methods for the generalized assignment problem. Optim. Methods Softw. 18(2), 129–141 (2003) · Zbl 1070.90066 · doi:10.1080/1055678031000107105 |
| [2] | Beasley, J.E.: Or-library: distributing test problems by electronic mail. J. Oper. Res. Soc. 41(11), 1069–1072 (1990) |
| [3] | Bonami, M.P.: Étude et mise en oeuvre d’approches polyédriques pour la résolution de programmes en nombres entiers ou mixtes généraux. Ph.D. thesis, L’Université Paris 6 (2003) |
| [4] | Boyd, E.A.: Generating Fenchel cutting planes for knapsack polyhedra. SIAM J. Optim. 3, 734–750 (1993) · Zbl 0797.90067 · doi:10.1137/0803038 |
| [5] | Boyd, E.A.: Solving integer programs with cutting planes and preprocessing. In: IPCO 1993, pp. 209–220 (1993) · Zbl 0923.90118 |
| [6] | Boyd, E.A.: Fenchel cutting planes for integer programming. Oper. Res. 42, 53–64 (1994) · Zbl 0809.90104 · doi:10.1287/opre.42.1.53 |
| [7] | Boyd, E.A.: On the convergence of Fenchel cutting planes in mixed-integer programming. SIAM J. Optim. 5, 421–435 (1995) · Zbl 0834.90095 · doi:10.1137/0805021 |
| [8] | Ceselli, A., Righini, G.: A branch and price algorithm for the capacitated p-median problem. Networks 45(3), 125–142 (2004) · Zbl 1101.68722 · doi:10.1002/net.20059 |
| [9] | Chu, P.C., Beasley, J.E.: A genetic algorithm for the generalised assignment problem. Comput. Oper. Res. 24, 17–23 (1997) · Zbl 0881.90070 · doi:10.1016/S0305-0548(96)00032-9 |
| [10] | Cornuejols, G., Lemarechal, C.: A convex-analysis perspective on disjunctive cuts. Math. Program. 106(3), 567–586 (2006) · Zbl 1149.90175 · doi:10.1007/s10107-005-0670-8 |
| [11] | De Farias, I.R., Nemhauser, G.L.: A family of inequalities for the generalized assignment polytope. Oper. Res. Lett. 29, 49–51 (2001) · Zbl 0981.90050 · doi:10.1016/S0167-6377(01)00086-4 |
| [12] | Fukasawa, R., Goycoolea, M.: On the exact separation of mixed integer knapsack cuts. In: Proceedings of the twelfth Integer Programming and Combinatorial Optimization Conference IPCO’07, Ithaca, NY. Lecture Notes in Computer Science, vol. 4513, pp. 225–239 (2007) · Zbl 1136.90418 |
| [13] | Gottlieb, E.S., Rao, M.R.: The generalized assignment problem: Valid inequalities and facets. Math. Program. 46, 31–52 (1990) · Zbl 0694.90071 · doi:10.1007/BF01585725 |
| [14] | Gottlieb, E.S., Rao, M.R.: (1,k)-configuration facets for the generalized assignment problem. Math. Program. 46, 53–60 (1990) · Zbl 0701.90065 · doi:10.1007/BF01585726 |
| [15] | Kaparis, K., Letchford, A.N.: Separation algorithms for 0-1 knapsack polytopes. Working paper. Department of Management Science, Lancaster University (2008). Available at http://www.optimization-online.org/DB_HTML/2007/06/1677.html (2007, in preparation) |
| [16] | Laguna, M., Kelly, J.P., Conzalez-Velarde, J.L., Glover, F.F.: Tabu search for the generalized assignment problem. Eur. J. Oper. Res. 82, 176–189 (1995) · Zbl 0905.90122 · doi:10.1016/0377-2217(93)E0174-V |
| [17] | Nauss, R.M.: Solving the generalized assignment problem: An optimizing and heuristic approach. INFORMS J. Comput. 15(3), 249–266 (2003) · Zbl 1238.90090 · doi:10.1287/ijoc.15.3.249.16075 |
| [18] | Osman, I.H.: Heuristics for the generalized assignment problem: Simulated annealing and tabu search approaches. OR Spektrum 17, 211–225 (1995) · Zbl 0841.90098 · doi:10.1007/BF01720977 |
| [19] | Padberg, M.W.: On the facial structure of set packing polyhedra. Math. Program. 5, 199–215 (1973) · Zbl 0272.90041 · doi:10.1007/BF01580121 |
| [20] | Pigatti, A., Poggi de Aragao, M., Uchoa, E.: Stabilized branch-and-cut-and-price for the generalized assignment problem. In: 2nd Brazilian Symposium on Graphs, Algorithms and Combinatorics. Electronic Notes in Discrete Mathematics, vol. 19, pp. 389–395. Elsevier, Amsterdam (2005) · Zbl 1203.90137 |
| [21] | Pisinger, D.: A minimal algorithm for the 0-1 knapsack problem. Oper. Res. 46, 758–767 (1995) · Zbl 0902.90126 |
| [22] | Savelsbergh, M.: A branch-and-price algorithm for the generalized assignment problem. Oper. Res. 45(6), 831–841 (1997) · Zbl 0895.90161 · doi:10.1287/opre.45.6.831 |
| [23] | Wolsey, L.A.: Facets and strong valid inequalities for integer programs. Oper. Res. 24, 367–372 (1976) · Zbl 0339.90036 · doi:10.1287/opre.24.2.367 |
| [24] | Yagiura, M., Ibaraki, T., Glover, F.: An ejection chain approach for the generalized assignment problem. INFORMS J. Comput. 16, 133–151 (2004) · Zbl 1239.90091 · doi:10.1287/ijoc.1030.0036 |
| [25] | Yagiura, M., Ibaraki, T., Glover, F.: A path relinking approach with ejection chains for the generalized assignment problem. Eur. J. Oper. Res. 169, 548–569 (2006) · Zbl 1079.90119 · doi:10.1016/j.ejor.2004.08.015 |
| [26] | Yagiura, M., Yamaguchi, T., Ibaraki, T.: A variable depth search algorithm with branching search for the generalized assignment problem. Optim. Methods Softw. 10, 419–441 (1998) · Zbl 0947.90070 · doi:10.1080/10556789808805722 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
