Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

Yannick Vimont (), Sylvain Boussier () and Michel Vasquez ()
Additional contact information
Yannick Vimont: Parc Scientifique Georges Besse
Sylvain Boussier: Parc Scientifique Georges Besse
Michel Vasquez: Parc Scientifique Georges Besse

Journal of Combinatorial Optimization, 2008, vol. 15, issue 2, No 3, 165-178

Abstract: Abstract In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.

Keywords: Multidimensional knapsack problem; Implicit enumeration; Variable fixing; Reduced costs; Constraint propagation (search for similar items in EconPapers)
Date: 2008
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (8)

Downloads: (external link)
http://link.springer.com/10.1007/s10878-007-9074-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:jcomop:v:15:y:2008:i:2:d:10.1007_s10878-007-9074-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-007-9074-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().