×

zbMATH — the first resource for mathematics

An implementation of exact knapsack separation. (English) Zbl 1355.90051
Summary: Cutting planes have been used with great success for solving mixed integer programs. In recent decades, many contributions have led to successive improvements in branch-and-cut methods which incorporate cutting planes in branch and bound algorithm. Using advances that have taken place over the years on 0-1 knapsack problem, we investigate an efficient approach for 0-1 programs with knapsack constraints as local structure. Our approach is based on an efficient implementation of knapsack separation problem which consists of the four phases: preprocessing, row generation, controlling numerical errors and sequential lifting. This approach can be used independently to improve formulations with cutting planes generated or incorporated in branch and cut to solve a problem. We show that this approach allows us to efficiently solve large-scale instances of generalized assignment problem, multilevel generalized assignment problem, capacitated \(p\)-median problem and capacitated network location problem to optimality.

MSC:
90C10 Integer programming
90C27 Combinatorial optimization
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Ceselli, A, Two exact algorithms for the capacitated p-Median problem, 4OR, 1, 319-340, (2003) · Zbl 1109.90054
[2] Ceselli, A; Righini, G, A branch and price algorithm for the capacitated \(p\)-Median problem, Networks, 45, 125-142, (2004) · Zbl 1101.68722
[3] 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 (2005) · Zbl 1203.90137
[4] Avella, P; Boccia, M; Vasilyev, I, A computational study of exact knapsack separation for the generalized assignment problem, Comput. Optim. Appl., 45, 543-555, (2010) · Zbl 1190.90153
[5] Boccia, M; Sforza, A; Sterle, C; Vasilyev, I, A cut and branch approach for the capacitated \(p\)-Median problem based on Fenchel cutting planes, J. Math. Model. Algorithms, 7, 43-58, (2007) · Zbl 1170.90521
[6] Vasilev, I, A cutting plane method for knapsack polytope, J. Comput. Syst. Sci. Int., 48, 70-77, (2009) · Zbl 1269.90097
[7] Nemhauser, G.L., Wolsey, L.A.: Integer and Combinatorial Optimization. Wiley, New York (1988) · Zbl 0652.90067
[8] Boyd, EA, Generating Fenchel cutting planes for knapsack polyhedra, SIAM J. Optim., 3, 734-750, (1993) · Zbl 0797.90067
[9] Boyd, EA, Solving integer programs with cutting planes and preprocessing, IPCO, 1993, 209-220, (1993) · Zbl 0923.90118
[10] Boyd, EA, Fenchel cutting planes for integer programming, Oper. Res., 42, 53-64, (1994) · Zbl 0809.90104
[11] Boyd, EA, On the convergence of Fenchel cutting planes in mixed-integer programming, SIAM J. Optim., 5, 421-435, (1995) · Zbl 0834.90095
[12] Fukasawa, R; Goycoolea, M, On the exact separation of mixed integer knapsack cuts, Math. Program., 128, 19-41, (2011) · Zbl 1218.90126
[13] Kaparis, K; Letchford, AN, Separation algorithms for 0-1 knapsack polytopes, Math. Program., 124, 69-91, (2010) · Zbl 1198.90297
[14] Bonami, M.P.: Étude et mise en oeuvre dapproches polyédriques pour la résolution de programmes en nombres entiers ou mixtes généraux. Ph.D. thesis, L’Université Paris 6 (2003) · Zbl 0923.90118
[15] Espinoza, D.G.: On Linear Programming, Integer Programming and Cutting Planes. PhD thesis, Georgia Institute of Technology, School of Industrial and Systems Engineering (2006)
[16] Avella, P; Boccia, M; Vasilyev, I, Computational testing of a separation procedure for the knapsack set with a single continuous variable, INFORMS J. Comput., 24, 165-171, (2012) · Zbl 1462.90101
[17] Avella, P; Boccia, M; Vasilyev, I, Computational experience with general cutting planes for the set covering problem, Oper. Res. Lett., 37, 16-20, (2009) · Zbl 1154.90603
[18] Applegate, D; Bixby, R; Chvatal, V; Cook, W, Implementing the Dantzig-fulkerson-Johnson algorithm for large traveling salesman problems, Math. Program., 97, 91-153, (2003) · Zbl 1106.90369
[19] Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J.: The Traveling Salesman Problem: A Computational Study (Princeton Series in Applied Mathematics). Princeton University Press, Princeton (2007)
[20] Cornuejols, G; Lemarechal, C, A convex-analysis perspective on disjunctive cuts, Math. Program., 106, 567-586, (2006) · Zbl 1149.90175
[21] Pisinger, D, A minimal algorithm for the 0-1 knapsack problem, Oper. Res., 46, 758-767, (1995) · Zbl 0902.90126
[22] Kellerer, H., Pferschy, U., Pisinger, D.: Knapsack Problems. Springer, Berlin (2005) · Zbl 1103.90003
[23] Martello, S., Toth, P.: Knapsack Problems: Algorithms and Computer Implementations. Wiley, London (1990) · Zbl 0708.68002
[24] Posta, M; Ferland, JA; Michelon, P, An exact method with variable fixing for solving the generalized assignment problem, Comput. Optim. Appl., 52, 629-644, (2012) · Zbl 1259.90062
[25] Beasley, JE, Or-library: distributing test problems by electronic mail, J. Oper. Res. Soc., 41, 1069-1072, (1990)
[26] Glover, F; Hultz, J; Klingman, D, Improved computer-based planning techniques. part ii, Interfaces, 9, 12-20, (1979)
[27] French, AP; Wilson, JM, Heuristic solution methods for the multilevel generalized assignment problem, J. Heuristics, 8, 143-153, (2002) · Zbl 1013.90087
[28] Laguna, M; Kelly, JP; Gonzlez-Velarde, JL; Glover, F, Tabu search for the multilevel generalized assignment problem, Eur. J. Oper. Res., 82, 176-189, (1995) · Zbl 0905.90122
[29] Osorio, MA; Laguna, M, Logic cuts for multilevel generalized assignment problems, Eur. J. Oper. Res., 151, 238-246, (2003) · Zbl 1033.90066
[30] Ceselli, A; Righini, G, A branch-and-price algorithm for the multilevel generalized assignment problem, Oper. Res., 54, 1172-1184, (2006) · Zbl 1167.90531
[31] Baldacci, R; Hadjiconstantinou, E; Maniezzo, V; Mingozzi, A, A new method for solving capacitated location problems based on a set partitioning approach, Comput. Oper. Res., 29, 365-386, (2002) · Zbl 0994.90087
[32] Lorena, L; Senne, E, A column generation approach to capacitated p-Median problems, Comput. Oper. Res., 31, 863-876, (2004) · Zbl 1048.90132
[33] Ceselli, A; Liberatore, Federico; Righini, Giovanni, A computational evaluation of a general branch-and-price framework for capacitated network location problems, Ann. Oper. Res., 167, 209-251, (2009) · Zbl 1172.90007
[34] Holmberg, K; Rnnqvist, M; Yuan, D, An exact algorithm for the capacitated facility location problems with single sourcing, Eur. J. Oper. Res., 113, 544-559, (1999) · Zbl 0947.90059
[35] Daz, JA; Fernndez, E, A branch-and-price algorithm for the single source capacitated plant location problem, J. Oper. Res. Soc., 53, 728-740, (2002) · Zbl 1130.90354
[36] Dolan, ED; More, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.