zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem. (English) Zbl 1138.90014

Summary: 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 the 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.

MSC:
90C09Boolean programming
Software:
OR-Library
References:
[1]Chu PC, Beasley JE (1998) A genetic algorithm for the multidimensional knapsack problem. J Heuristics 4(1):63–86 · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[2]Chvátal V (1983) Linear programming. Freeman, New York
[3]Fayard D, Plateau G (1982) An algorithm for the solution of the 0–1 knapsack problem. Computing 28(3):269–287 · Zbl 0475.90062 · doi:10.1007/BF02241754
[4]Fréville A (2004) The multidimensional 0–1 knapsack problem: an overview. Eur J Oper Res 155:1–21 · Zbl 1045.90050 · doi:10.1016/S0377-2217(03)00274-1
[5]Fréville A, Plateau G (1994) An efficient preprocessing procedure for the multidimensional 0–1 knapsack problem. Discret Appl Math 49:189–212 · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[6]James RJW, Nakagawa Y (2005) Enumeration methods for repeatedly solving multidimensional knapsack sub-problems. Technical report E88-D, 10:83-103, The Institute of Electronics, Information and Communication Engineers
[7]Oliva C, Michelon P, Artigues C (2001) Constraint and linear programming: using reduced costs for solving the zero/one multiple knapsack problem. In International conference on constraint programming, CP 01, proceedings of the workshop on cooperative solvers in constraint programming (CoSolv 01), pp 87–98
[8]Saunders RM, Schinzinger R (1970) A shrinking boundary algorithm for discrete system models. IEEE Trans Syst Sci Cybern 6:133–140 · doi:10.1109/TSSC.1970.300288
[9]Vasquez M, Hao JK (2001) An hybrid approach for the 0–1 multidimensional knapsack problem. In Proceedings of the 17th international joint conference on artificial intelligence, IJCAI-01, Seattle, WA
[10]Vasquez M, Vimont Y (2005) Improved results on the 0-1 multidimensional knapsack problem. Eur J Oper Res 165(1):70–81 · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024