zbMATH — the first resource for mathematics

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.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
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)
Improved core problem based heuristics for the 0/1 multi-dimensional knapsack problem. (English) Zbl 1251.90279
Summary: We consider the $0/1$ multi-dimensional knapsack problem and discuss the performances of a new heuristic procedure particularly suitable for a parallel computing environment embedding core problem approaches and a branching scheme based on reduced costs of the corresponding LP relaxation solution value. The proposed approach compared favorably to the recent state of the art procedures available in the literature on the well known OR-Library multi-dimensional knapsack problem benchmarks instances.

90C10Integer programming
90C27Combinatorial optimization
Full Text: DOI
[1] Balas, E.; Zemel, E.: An algorithm for large zero-one knapsack problems, Operations research 28, 1130-1154 (1980) · Zbl 0449.90064 · doi:10.1287/opre.28.5.1130
[2] Boussier, S.; Vasquez, M.; Vimont, Y.; Hanafi, S.; Michelon, P.: A multi-level search strategy for the 0/1 multidimensional knapsack problem, Discrete applied mathematics 158, 97-109 (2010) · Zbl 1185.90170 · doi:10.1016/j.dam.2009.08.007
[3] Chu, P. C.; Beasley, J. E.: A genetic algorithm for the multidimensional knapsack problem, Journal of heuristics 4, 63-86 (1998) · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[4] Driebeek, N. J.: An algorithm for the solution of mixed integer programming problems, Management science 12, 576-587 (1966)
[5] Danna, E.; Rothberh, E.; Le Pape, C.: Exploring relaxation induced neighborhood to improve MIP solutions, Mathematical programming 102, 71-90 (2005) · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7
[6] Fischetti, M.; Lodi, A.: Local branching, Mathematical programming 98, 23-47 (2003) · Zbl 1060.90056 · doi:10.1007/s10107-003-0395-5
[7] Fréville, A.: The multidimensional 0--1 knapsack problem: an overview, European journal of operational research 155, 1-21 (2004) · Zbl 1045.90050 · doi:10.1016/S0377-2217(03)00274-1
[8] Fréville, A.; Hanafi, S.: The multidimensional 0--1 knapsack problem--bounds and computational aspects, Annals of operations research 139, 195-227 (2004) · Zbl 1091.90042 · doi:10.1007/s10479-005-3448-8
[9] Hanafi S, Wilbaut C. Improved convergent heuristics for the 0--1 multi-dimensional knapsack problem. Annals of Operations Research, Annals of Operations Research, 2011;183:125--142(18), doi: 10.1007/s10479-009-0546-z. · Zbl 1215.90045 · doi:10.1007/s10479-009-0546-z
[10] Kellerer, H.; Pferschy, U.; Pisinger, D.: Knapsack problems, (2004) · Zbl 1103.90003
[11] Linderoth, J. T.; Savelsbergh, P.; Luenberger, D. G.: A computational study of search strategies for mixed integer programming, INFORMS journal on computing 11, 173-187 (1999) · Zbl 1040.90535 · doi:10.1287/ijoc.11.2.173
[12] Lorie, J.; Savage, L. J.: Three problems in capital rationing, Journal of business 28, 229-239 (1955)
[13] Puchinger J, Raidl GR, Pferschy U. The multidimensional knapsack problem: structure and algorithms. INFORMS Journal on Computing 2010;22:250--65. · Zbl 1243.90190
[14] Soyster, A. L.; Lev, B.; Slivka, W.: Zero-one programming with many variables and few constraints, European journal of operational research 2, 195-201 (1978) · Zbl 0381.90076 · doi:10.1016/0377-2217(78)90093-0
[15] Vasquez, M.; Vimont, Y.: Improved results on the 0--1 multidimensional knapsack problem, European journal of operational research 165, 70-81 (2005) · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[16] Vimont, Y.; Boussier, S.; Vasquez, M.: Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem, Journal of combinatorial optimization 15, 165-178 (2008) · Zbl 1138.90014 · doi:10.1007/s10878-007-9074-4
[17] Wilbaut, C.; Hanafi, S.: New convergent heuristics for 0--1 mixed integer programming, European journal of operational research 195, 62-74 (2009) · Zbl 1161.90448 · doi:10.1016/j.ejor.2008.01.044