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)
A multi-level search strategy for the 0-1 multidimensional knapsack problem. (English) Zbl 1185.90170
Summary: We propose an exact method based on a multi-level search strategy for solving the 0-1 Multidimensional Knapsack Problem. Our search strategy is primarily based on the reduced costs of the non-basic variables of the LP-relaxation solution. Considering that the variables are sorted in decreasing order of their absolute reduced cost value, the top level branches of the search tree are enumerated following Resolution Search strategy, the middle level branches are enumerated following Branch & Bound strategy and the lower level branches are enumerated according to a simple Depth First Search enumeration strategy. Experimentally, this cooperative scheme is able to solve optimally large-scale strongly correlated 0-1 Multidimensional Knapsack Problem instances. The optimal values of all the 10 constraint, 500 variable instances and some of the 30 constraint, 250 variable instances of the OR-Library were found. These values were previously unknown.

90C27Combinatorial optimization
90C09Boolean programming
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
Full Text: DOI EuDML
[1] Balas, E.; Martin, C.: Pivot and complement-heuristic for 0-1 programming, Management science 26, No. 1, 86-96 (1980) · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86
[2] Beasley, J.: Or-library: distributing test problems by electronic mail, Journal of operational research society 41, 1069-1072 (1990)
[3] S. Boussier, Étude de Resolution Search pour la programmation linaire en variables binaires, Ph.D. Thesis, University of Montpellier II, 2008
[4] 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
[5] Chvátal, V.: Resolution search, Discrete applied mathematics 73, 81-99 (1997) · Zbl 0869.90055 · doi:10.1016/S0166-218X(96)00003-0 · http://www.elsevier.com/locate/dam
[6] Codato, G.; Fischetti, M.: Combinatorial benders’ cuts, Integer programming and combinatorial optimization, 178-195 (2004) · Zbl 1092.90529
[7] S. Demassey, C. Artigues, P. Michelon, An application of resolution search to the rcpsp, in: 17th European Conference on Combinatorial Optimization ECCO’04, Beyrouth, Lebanon, 2004 · Zbl 1239.90062
[8] Fayard, D.; Plateau, G.: An algorithm for the solution of the 0-1 knapsack problem, Computing 28, No. 3, 269-287 (1982) · Zbl 0468.90045 · doi:10.1007/BF02241754
[9] Fréville, 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
[10] 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
[11] Fréville, A.; Hanafi, S.: The multidimensional 0-1 knapsack problem - bounds and computational aspect. Advances in operations research, Annals of operations research 139, No. 1, 195-227 (2005) · Zbl 1091.90042 · doi:10.1007/s10479-005-3448-8
[12] Gavish, B.; Pirkul, H.: Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Mathematical programming 31, 78-105 (1985) · Zbl 0571.90065 · doi:10.1007/BF02591863
[13] Gilmore, P.; Gomory, R.: The theory and computation of knapsack functions, Operations research 14, 1045-1075 (1966) · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045
[14] Ginsberg, M. L.: Dynamic backtracking, Journal of artificial intelligence research 1, 25 (1993) · Zbl 0900.68179 · http://www.jair.org/contents/v1.html
[15] Glover, F.; Tangedahl, L.: Dynamic strategies for branch and bound, OMEGA, the international journal of management science 4, No. 5, 571-575 (1976)
[16] C. Green, Two algorithms for solving independent multidimensional knapsack problems, Management Science Report, no. 110, Carnegie Institute of Technology, Graduate School of Industrial Administration, Pittsburgh, USA, 1967
[17] Hanafi, S.; Glover, F.: Resolution search and dynamic branch-and-bound, Journal of combinatorial optimization 6, No. 4, 401-423 (2002) · Zbl 1046.90048 · doi:10.1023/A:1019573820792
[18] James, R.; Nakagawa, Y.: Enumeration methods for repeatedly solving multidimensional knapsack sub-problems, IEICE - transactions on information and systems 88-D, 2329-2340 (2005)
[19] Kellerer, H.; Pferschy, U.; Pisinger, D.: Knapsack problems, (2004) · Zbl 1103.90003
[20] Martello, S.; Toth, P.: Knapsack problems: algorithms and computer implementations, Series in discrete mathematics and optimization (1990) · Zbl 0708.68002
[21] C. Oliva, P. Michelon, C. Artigues, 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, 2001, pp. 87--98
[22] M. Palpant, C. Artigues, C. Oliva, Mars: A hybrid scheme based on resolution search and constraint programming for constraint satisfaction problems, laas report 07194, Tech. Rep, LAAS-CNRS, Université de Toulouse, France, 2007
[23] Saunders, R. M.; Schinzinger, R.: A shrinking boundary algorithm for discrete system models, IEEE transactions on systems science and cybernetics 6, No. 2, 133-140 (1970) · Zbl 0198.52503
[24] Shih, W.: A branch and bound method for the multiconstraint zero-one knapsack problem, Journal of operational reasearch society 30, 369-378 (1979) · Zbl 0411.90050 · doi:10.2307/3009639
[25] M. Vasquez, J. Hao, An hybrid approach for the 0-1 multidimensional knapsack problem, in: Proc. 17th International Joint Conference on Artificial Intelligence, IJCAI-01, Seattle, WA, 2001 · Zbl 1015.90056
[26] 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
[27] 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
[28] Weigartner, H.; Ness, D.: Methods for the solution of the multidimensional 0/1 knapsack problem, Operations research 15, 83-103 (1967)
[29] 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