Solving the 0-1 Multidimensional Knapsack Problem with Resolution Search
作者： Sylvain Boussier , Yannick Vimont , Said Hanafi , Michel Vasquez , Philippe Michelon
DOI:
关键词: Mathematical optimization 、 Continuous knapsack problem 、 Constraint (information theory) 、 Variable (computer science) 、 Mathematics 、 Scale (ratio) 、 Resolution (logic) 、 Knapsack problem 、 Change-making problem 、 Cutting stock problem
摘要: We propose an exact method which combines the resolution search and branch & bound algorithms for solving 0?1 Multidimensional Knapsack Problem. This algorithm is able to prove large?scale strong correlated instances. The optimal values of 10 constraint, 500 variable instances OR-Library are exposed. These were previously unknown.
arxiv.org
harvard.edu参考文章(6)
Jin-Kao Hao, Michel Vasquez, A hybrid approach for the 0-1 multidimensional knapsack problem international joint conference on artificial intelligence. pp. 328- 333 ,(2001)
R. J.W. JAMES, Enumeration Methods for Repeatedly Solving Multidimensional Knapsack Sub-Problems The IEICE transactions on information and systems. ,vol. 88, pp. 2329- 2340 ,(2005) , 10.1093/IETISY/E88-D.10.2329
J. E. Beasley, OR-Library: Distributing Test Problems by Electronic Mail Journal of the Operational Research Society. ,vol. 41, pp. 1069- 1072 ,(1990) , 10.1057/JORS.1990.166
Yannick Vimont, Sylvain Boussier, Michel Vasquez, Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem Journal of Combinatorial Optimization. ,vol. 15, pp. 165- 178 ,(2008) , 10.1007/S10878-007-9074-4
Michel Vasquez, Yannick Vimont, Improved results on the 0–1 multidimensional knapsack problem European Journal of Operational Research. ,vol. 165, pp. 70- 81 ,(2005) , 10.1016/J.EJOR.2004.01.024
V. Chvatal, Resolution Search ,(1995)