Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions

María Osorio (), Fred Glover and Peter Hammer

Annals of Operations Research, 2002, vol. 117, issue 1, 93 pages

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. Copyright Kluwer Academic Publishers 2002

Keywords: multidimensional knapsack problem; surrogate constraints; duality; constraint pairing; logic cuts (search for similar items in EconPapers)
Date: 2002
References: Add references at CitEc
Citations: View citations in EconPapers (12)

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1021513321301 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:117:y:2002:i:1:p:71-93:10.1023/a:1021513321301

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1021513321301

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().