Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions

Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions

0.00 Avg rating0 Votes
Article ID: iaor20032511
Country: Netherlands
Volume: 117
Issue: 1
Start Page Number: 71
End Page Number: 93
Publication Date: Nov 2002
Journal: Annals of Operations Research
Authors: , ,
Keywords: knapsack problem, duality
Abstract:

We use surrogate analysis and constraint pairing in multidimensional knapsack problems to fix some variables to zero and to separate the rest into two groups – those that tend to be zero and those that tend to be one, in an optimal integer solution. Using an initial feasible integer solution, we generate logic cuts based on our analysis before solving the problem with branch and bound. Computational testing, including the set of problems in the OR-library and our own set of difficult problems, shows our approach helps to solve difficult problems in a reasonable amount of time and, in most cases, with a fewer number of nodes in the search tree than leading commercial software.

Reviews

Required fields are marked *. Your email address will not be published.