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: | Glover Fred, Hammer Peter, Osorio Mara A. |
Keywords: | knapsack problem, duality |
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.