Abstract
In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4(1):63–86
Chvátal V (1983) Linear programming. Freeman, New York
Fayard D, Plateau G (1982) An algorithm for the solution of the 0–1 knapsack problem. Computing 28(3):269–287
Fréville A (2004) The multidimensional 0–1 knapsack problem: an overview. Eur J Oper Res 155:1–21
Fréville A, Plateau G (1994) An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem. Discret Appl Math 49:189–212
James RJW, Nakagawa Y (2005) Enumeration methods for repeatedly solving multidimensional knapsack sub-problems. Technical report E88-D, 10:83-103, The Institute of Electronics, Information and Communication Engineers
Oliva C, Michelon P, Artigues C (2001) Constraint and linear programming: using reduced costs for solving the zero/one multiple knapsack problem. In International conference on constraint programming, CP 01, proceedings of the workshop on cooperative solvers in constraint programming (CoSolv 01), pp 87–98
Saunders RM, Schinzinger R (1970) A shrinking boundary algorithm for discrete system models. IEEE Trans Syst Sci Cybern 6:133–140
Vasquez M, Hao JK (2001) An hybrid approach for the 0–1 multidimensional knapsack problem. In Proceedings of the 17th international joint conference on artificial intelligence, IJCAI-01, Seattle, WA
Vasquez M, Vimont Y (2005) Improved results on the 0-1 multidimensional knapsack problem. Eur J Oper Res 165(1):70–81
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Vimont, Y., Boussier, S. & Vasquez, M. Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem. J Comb Optim 15, 165–178 (2008). https://doi.org/10.1007/s10878-007-9074-4
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-007-9074-4