On separating cover inequalities for the multidimensional knapsack problem. (English) Zbl 1159.90460
Summary: We propose a simple and a quite efficient separation procedure to identify cover inequalities for the multidimensional knapsack problem. It is based on the solution of a conventional integer programming model. Solving this kind of integer programs is usually considered expensive and the proposed method may have been overlooked because of this assumption. The results of our experiments with a small set of randomly generated problems and problems taken from the literature indicate that the method may be a reasonable alternative to the one currently in use.
References:
| [1] | Kellerer, H.; Pferschy, U.; Pisinger, D., Knapsack problems (2004), Springer: Springer Berlin · Zbl 1103.90003 |
| [2] | Crowder, H.; Johnson, E. L.; Padberg, M. W., Solving large scale zero-one linear programming problems, Operations Research, 31, 803-834 (1983) · Zbl 0576.90065 |
| [3] | Gu, Z.; Nemhauser, G. L.; Savelsbergh, M. W.P., Lifted cover inequalities for 0-1 integer programs: computation, INFORMS Journal on Computing, 10, 4, 427-437 (1998) |
| [4] | Johnson, E. L.; Nemhauser, G. L.; Savelsbergh, M. W.P., Progress in linear programming-based algorithms for integer programming: an exposition, INFORMS Journal on Computing, 12, 1, 2-23 (2000) · Zbl 1052.90048 |
| [5] | Wolsey, L. A., Integer programming (1998), Wiley: Wiley New York · Zbl 0299.90012 |
| [6] | Nemhauser, G. L.; Wolsey, L. A., Integer and combinatorial optimization (1999), Wiley: Wiley New York · Zbl 0469.90052 |
| [7] | OR-Library. Available at \(\langle;\) http://people.brunel.ac.uk/\( \sim;\rangle;\); OR-Library. Available at \(\langle;\) http://people.brunel.ac.uk/\( \sim;\rangle;\) |
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.
