Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions |
| |
Authors: | María A. Osorio Fred Glover Peter Hammer |
| |
Affiliation: | (1) Autonomous University of Puebla, Puebla, 72560, México;(2) Hearin Center for Enterprise Science, School of Business, University of Mississippi, MS 38677, USA;(3) Rutgers Center for Operations Research, Rutgers University, Piscataway, NJ 08854-8003, USA |
| |
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. |
| |
Keywords: | multidimensional knapsack problem surrogate constraints duality constraint pairing logic cuts |
本文献已被 SpringerLink 等数据库收录! |
|