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)
Fast, effective heuristics for the 0-1 multi-dimensional knapsack problem. (English) Zbl 1179.90282
Summary: The objective of the multi-dimensional knapsack problem (MKP) is to find a subset of items with maximum value that satisfies a number of knapsack constraints. Solution methods for MKP, both heuristic and exact, have been researched for several decades. This paper introduces several fast and effective heuristics for MKP that are based on solving the LP relaxation of the problem. Improving procedures are proposed to strengthen the results of these heuristics. Additionally, the heuristics are run with appropriate deterministic or randomly generated constraints imposed on the linear relaxation that allow generating a number of good solutions. All algorithms are tested experimentally on a widely used set of benchmark problem instances to show that they compare favourably with the best-performing heuristics available in the literature.
MSC:
90C27Combinatorial optimization
90C59Approximation methods and heuristics
90C09Boolean programming
References:
[1]Freville, A.; Plateau, G.: An efficient preprocessing procedure for the multidimensional 0 – 1 knapsack problem, Discrete applied mathematics 49, 189-212 (1994) · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[2]Bertsimas, D.; Demir, R.: An approximate dynamic programming approach to multidimensional knapsack problems, Management science 48, No. 4, 550-565 (2002) · Zbl 1232.90322 · doi:10.1287/mnsc.48.4.550.208
[3]Rothkopf MH, Pekec A, Harstad RM. Computationally manageable combinatorial auctions. Technical Report 95-09, Rutgers University, Piscataway, NJ; 1995.
[4]DeVries S, Vohra R. Combinatorial auctions: a survey. Technical Report, Northwestern University, Evanston, IL; 2000.
[5]Ferreira, C.; Grotschel, M.; Kiefl, S.; Krispenz, C.; Martin, A.; Weismantel, R.: Some integer programs arising in the design of mainframe computers, ZOR — methods models operation research 38, No. 1, 77-110 (1993)
[6]Peterson, C. C.: Computational experience with variants of the balas algorithm applied to the selection of research and development projects, Management science 13, 736-750 (1967)
[7]Gilmore, P. C.; Gomory, R. E.: The theory and computation of knapsack functions, Operations research 14, 1045-1075 (1966) · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045
[8]Freville, 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
[9]Freville, A.; Hanafi, S.: The multidimensional 0 – 1 knapsack problem-bounds and computational aspects, Annals of operations research 139, No. 1, 195-227 (2005) · Zbl 1091.90042 · doi:10.1007/s10479-005-3448-8
[10]Hanafi, S.; Glover, F.: Exploiting nested inequalities and surrogate constraints, European journal of operational research 179, No. 1, 50-63 (2007)
[11]Osorio, M. A.; Glover, F.; Hammer, P.: Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Annals of operations research 117, No. 1 – 4, 71-93 (2002) · Zbl 1028.90042 · doi:10.1023/A:1021513321301
[12]Akcay, Y.; Li, H.; Xu, S. H.: Greedy algorithm for the general multidimensional knapsack problem, Annals of operations research 150, No. 1, 17-29 (2007) · Zbl 1144.90466 · doi:10.1007/s10479-006-0150-4
[13]Toyoda, Y.: A simplified algorithm for obtaining approximate solutions to zero – one programming problems, Management science 21, 1417-1427 (1975) · Zbl 0307.90056 · doi:10.1287/mnsc.21.12.1417
[14]Senju, S.; Toyoda, Y.: An approach to linear programming with 0 – 1 linear variables, Management science 15, 196-207 (1968)
[15]Loulou, R.; Michaelides, E.: New greedy-like heuristics for the multidimensional 0 – 1 knapsack problem, Operations research 27, No. 6, 1101-1114 (1979) · Zbl 0442.90058 · doi:10.1287/opre.27.6.1101
[16]Kochenberger, G. A.; Mccarl, B. A.; Wyman, F. P.: A heuristic for general integer programming, Decision sciences 5, No. 1, 36-44 (1974)
[17]Magazine, M. J.; Oguz, O.: Heuristic algorithm for the multidimensional zero – one knapsack problem, European journal of operational research 16, No. 3, 319-326 (1984) · Zbl 0532.90070 · doi:10.1016/0377-2217(84)90286-8
[18]Volgenant, A.; Zoon, J. A.: An improved heuristic for multidimensional 0 – 1 knapsack problem, Journal of operational research society 41, No. 10, 963-970 (1990) · Zbl 0724.90044
[19]Volgenant, A.; Zwiers, I. Y.: Partial enumeration in heuristics for some combinatorial optimization problems, Journal of the operational research society 58, No. 1, 73-79 (2007) · Zbl 1156.90029 · doi:10.1057/palgrave.jors.2602102
[20]Chu, P. C.; Beasley, J. E.: A genetic algorithm for the multidimensional knapsack problem, Journal of heuristics 4, No. 1, 63-86 (1998) · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[21]Vasquez M, Hao J-K. A hybrid approach for the 0 – 1 multidimensional knapsack problem. In: IJCAI-01 Proceedings of the 7th international joint conference on artificial intelligence, Seatle, Washington, 2001. p. 328 – 33.
[22]Vasquez, M.; Vimont, Y.: Improved results on the 0 – 1 multidimensional knapsack problem, European journal of operational research 165, No. 1, 70-81 (2005) · Zbl 1112.90366 · doi:10.1016/j.ejor.2004.01.024
[23]Pirkul, H.: Heuristic solution procedure for the multiconstraint zero – one knapsack problem, Naval research logistics 34, No. 2, 161-172 (1987) · Zbl 0609.90092 · doi:10.1002/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A
[24]Gavish, B.; Pirkul, H.: Efficient algorithms for solving multiconstraint zero – one knapsack problems to optimality, Mathematical programming 31, No. 1, 78-105 (1985) · Zbl 0571.90065 · doi:10.1007/BF02591863