Local and global lifted cover inequalities for the 0-1 multidimensional knapsack problem. (English) Zbl 1138.90016
Summary: The 0-1 multidimensional knapsack problem (0-1 MKP) is a well-known (and strongly \(\mathcal {NP}\)-hard) combinatorial optimization problem with many applications. Up to now, the majority of upper bounding techniques for the 0-1 MKP have been based on Lagrangian or surrogate relaxation. We show that good upper bounds can be obtained by a cutting plane method based on lifted cover inequalities (LCIs). As well as using traditional LCIs, we use some new ‘global’ LCIs, which take the whole constraint matrix into account.
References:
| [1] | Atamturk, A., Cover and pack inequalities for (mixed) integer programming, Annals of Operations Research, 139, 21-38 (2005) · Zbl 1091.90053 |
| [2] | Balas, E., Facets of the knapsack polytope, Mathematical Programming, 8, 146-164 (1975) · Zbl 0316.90046 |
| [3] | Balas, E.; Zemel, E., Facets of the knapsack polytope from minimal covers, SIAM Journal on Applied Mathematics, 34, 119-148 (1978) · Zbl 0385.90083 |
| [4] | Bektas, T.; Oguz, O., On separating cover inequalities for the multidimensional knapsack problem, Computers and Operations Research, 34, 1771-1776 (2007) · Zbl 1159.90460 |
| [5] | Boyd, E. A., Generating Fenchel cutting planes for knapsack polyhedra, SIAM Journal on Optimization, 3, 734-750 (1993) · Zbl 0797.90067 |
| [6] | Chvátal, V., Edmonds polytopes and a hierarchy of combinatorial problems, Discrete Mathematics, 4, 305-337 (1973) · Zbl 0253.05131 |
| [7] | Chu, P. C.; Beasley, J. E., A genetic algorithm for the multidimensional knapsack problem, Journal of Heuristics, 4, 63-86 (1998) · Zbl 0913.90218 |
| [8] | Crowder, H.; Johnson, E.; Padberg, M., Solving large-scale 0-1 linear programming programs, Operations Research, 31, 803-834 (1983) · Zbl 0576.90065 |
| [9] | Ferreira, C. E.; Martin, A.; Weismantel, R., Solving multiple knapsack problems by cutting planes, SIAM Journal on Optimizaton, 6, 858-877 (1996) · Zbl 0856.90082 |
| [10] | Fréville, A., The multidimensional 0-1 knapsack problem: An overview, European Journal of Operational Research, 155, 1-21 (2004) · Zbl 1045.90050 |
| [11] | Fréville, A.; Hanafi, S., multidimensional 0-1 knapsack problem: Bounds and computational aspects, Annals of Operations Research, 139, 195-227 (2005) · Zbl 1091.90042 |
| [12] | Gabrel, V.; Minoux, M., A scheme for exact separation of extended cover inequalities and application to multidimensional knapsack problems, Operations Research Letters, 30, 252-264 (2002) · Zbl 1049.90074 |
| [13] | Garey, M. R.; Johnson, D. S., Computers and Intractability: An Introduction to the Theory of \(NP\)-completeness (1979), W.H. Freeman: W.H. Freeman San Francisco · Zbl 0411.68039 |
| [14] | Gu, Z.; Nemhauser, G. L.; Savelsbergh, M. W.P., Cover inequalities for 0-1 linear programs: computation, Informs Journal on Computing, 10, 427-437 (1998) |
| [15] | Gu, Z.; Nemhauser, G. L.; Savelsbergh, M. W.P., Cover inequalities for 0-1 linear programs: Complexity, Informs Journal on Computing, 11, 117-123 (1999) · Zbl 1092.90527 |
| [16] | Gu, Z.; Nemhauser, G. L.; Savelsbergh, M. W.P., Sequence independent lifting in mixed integer programming, Journal of Combinatorial Optimization, 4, 109-129 (2000) · Zbl 0964.90030 |
| [17] | Guignard, M.; Kim, S., Lagrangean decomposition: A model yielding strong Lagrangean bounds, Mathematical Programming, 39, 215-228 (1987) · Zbl 0638.90074 |
| [18] | Klabjan, D.; Nemhauser, G.; Tovey, C., The complexity of cover inequality separation, Operations Research Letters, 23, 35-40 (1998) · Zbl 0957.90094 |
| [19] | Letchford, A. N.; Lodi, A., Strengthening Chvátal-Gomory cuts and Gomory fractional cuts, Operations Research Letters, 32, 74-82 (2002) · Zbl 1027.90062 |
| [20] | Martin, A.; Weismantel, R., The intersection of knapsack polyhedra and extensions, (Bixby, R. E.; Boyd, E. A.; Rios-Mercado, R. Z., Proceedings of the Sixth IPCO Conference. Proceedings of the Sixth IPCO Conference, Lecture Notes in Computer Science, vol. 1412 (1998), Springer-Verlag) · Zbl 0910.90223 |
| [21] | Nemhauser, G. L.; Wolsey, L. A., Integer and Combinatorial Optimization (1988), Wiley: Wiley New York · Zbl 0469.90052 |
| [22] | Nobili, P.; Sassano, A., A separation routine for the set covering polytope, (Balas, E.; Cornuéjols, G.; Kannan, R., Proceedings of the Second IPCO Conference (1992), CMU Press: CMU Press Pittsburgh) · Zbl 0712.90060 |
| [23] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack Problems (2004), Springer-Verlag · Zbl 1103.90003 |
| [24] | Wolsey, L. A., Faces for linear inequalities in 0-1 variables, Mathematical Programming, 8, 165-178 (1975) · Zbl 0314.90063 |
| [25] | Wolsey, L. A., Facets and strong valid inequalities for integer programs, Operations Research, 24, 367-372 (1976) · Zbl 0339.90036 |
| [26] | Zemel, E., Easily computable facets of the knapsack polytope, Mathematics of Operations Research, 14, 760-765 (1989) · Zbl 0689.90057 |
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.
