Solving the 0-1 Multidimensional Knapsack Problem with Resolution Search

Authors :: Boussier, Sylvain
Vasquez, Michel
Vimont, Yannick
Hanafi, Said
Michelon, Philippe
Source :: VI ALIO/EURO Workshop on Applied Combinatorial Optimization, Buenos Aires : Argentine (2008)
Publication Year :: 2009
Abstract: We propose an exact method which combines the resolution search and branch & bound algorithms for solving the 0?1 Multidimensional Knapsack Problem. This algorithm is able to prove large?scale strong correlated instances. The optimal values of the 10 constraint, 500 variable instances of the OR-Library are exposed. These values were previously unknown.

Database :: arXiv
Journal :: VI ALIO/EURO Workshop on Applied Combinatorial Optimization, Buenos Aires : Argentine (2008)
Publication Type :: Report
Accession number :: edsarx.0905.0848
Document Type :: Working Paper

Tools