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)
The multidimensional 0-1 knapsack problem: an overview. (English) Zbl 1045.90050
Summary: The multidimensional 0-1 knapsack problem is one of the most well-known integer programming problems and has received wide attention from the operational research community during the last four decades. Although recent advances have made possible the solution of medium size instances, solving this NP-hard problem remains a very interesting challenge, especially when the number of constraints increases. This paper surveys the main results published in the literature. The focus is on the theoretical properties as well as approximate or exact solutions of this special 0-1 program.

MSC:
90C27Combinatorial optimization
90C59Approximation methods and heuristics
90C57Polyhedral combinatorics, branch-and-bound, branch-and-cut
WorldCat.org
Full Text: DOI
References:
[1] Aboudi, R.; Hallefjord, A.; Helming, R.; Jornsten, K.: A note on the pivot and complement heuristic for 0--1 programming problems. Operations research letters 8, 21-23 (1989) · Zbl 0661.90062
[2] Aboudi, R.; Jornsten, K.: Tabu search for general zero--one integer programs using the pivot and complement heuristics. ORSA journal of computing 6, 82-93 (1994) · Zbl 0798.90105
[3] Andonov, R.: Finding facets of the knapsack polytope which cut off a given point. Comptes rendus de l’académie bulgare des sciences, 41-44 (1987) · Zbl 0664.90062
[4] R. Andonov, S. Balev, A. Fréville, N. Yanev, A dynamic programming based reduction procedure for the multidimensional 0--1 knapsack problem, Working paper, University of Valenciennes, presented at FRANCORO III, Québec, Canada, May 2001. Forthcoming in European Journal of Operational Research · Zbl 1138.90015
[5] Averbakh, I.: Probabilistic properties of the dual structure of the multidimensional knapsack problem and fast statistically efficient algorithms. Mathematical programming 65, 311-330 (1994) · Zbl 0828.90090
[6] Balas, E.: An additive algorithm for solving linear programs with zero--one variables. Operations research 13, 517-546 (1965) · Zbl 0194.19903
[7] Balas, E.: Discrete programming by the filter method. Operations research 19, 915-957 (1967) · Zbl 0153.21401
[8] Balas, E.; Ceria, S.; Dawande, M.; Margot, F.; Pataki, G.: OCTANE: A new heuristic for pure 0--1 programs. Operations research 49, 207-225 (2001) · Zbl 1163.90654
[9] Balas, E.; Martin, C. H.: Pivot and complement----A heuristic for 0--1 programming. Management sciences 26, 86-96 (1980) · Zbl 0442.90060
[10] E. Balas, C.H. Martin, Pivot and shift----a heuristic for mixed integer programming, Working paper, GSIA, Carnegie Mellon University, USA, 1986
[11] Balas, E.; Zemel, E.: An algorithm for large zero--one knapsack problems. Operations research 28, 1130-1145 (1980) · Zbl 0449.90064
[12] Barcia, P.: The bound improving sequence algorithm. Operations research letters 4, 27-30 (1985) · Zbl 0568.90065
[13] Barcia, H.; Holm, S.: A revised bound improvement sequence algorithm. European journal of operational research 36, 202-206 (1988) · Zbl 0643.90062
[14] Battiti, R.; Tecchiolli, G.: Parallel biased search for combinatorial optimization: genetic algorithms and tabu search. Microprocessors and microsystems 16, 351-367 (1992)
[15] Battiti, R.; Tecchiolli, G.: The reactive tabu search. ORSA journal on computing 6, 126-140 (1994) · Zbl 0807.90094
[16] Battiti, R.; Tecchiolli, G.: Local search with memory: benchmarking RTS. OR-spektrum 17, 67-86 (1995) · Zbl 0843.90094
[17] Beale, E. M. L: Branch and bound methods for mathematical programming systems. Annals of discrete mathematics 5, 201-219 (1979) · Zbl 0405.90049
[18] J.E. Beasley, OR-Library: Distributed test problems by electronic mail, Journal of the Operational Research Society 41 (1990) 1069-1072 (http://mscmga.ms.ic.ac.uk/info.html)
[19] Beaujon, G. J.; Martin, S. P.; Mcdonald, C. C.: Balancing and optimizing a portfolio of R&D projects. Naval research logistics 48, 18-40 (2001) · Zbl 0976.91030
[20] Bellman, R.: Dynamic programming. (1957) · Zbl 0077.13605
[21] Bradley, G. H.; Hammer, P. L.; Wolsey, L.: Coefficient reduction for inequalities in 0--1 variables. Mathematical programming 7, 263-282 (1974) · Zbl 0292.90038
[22] Breu, R.; Burdet, C. A.: Branch and bound experiments in zero--one programming. Mathematical programming study 2, 1-50 (1974) · Zbl 0358.90038
[23] Cabot, A. V.: An enumeration algorithm for knapsack problems. Operations research 18, 306-311 (1970) · Zbl 0195.20801
[24] P. Cappanera, M. Trubian, A local search based heuristic for the demand constrained multidimensional knapsack problem, Working paper presented at Congress Adaptive Memory and Evolution: Tabu Search and Scatter Search, Oxford, USA, March 2001
[25] E.D. Chajakis, M. Guignard, A model for delivery of groceries in vehicles with multiple compartments and Lagrangean approximation schemes, VI Congreso Latino-Ibero-Americano de Investigaciones e Ingenieria de Sistemas, Mexico City, October 1992
[26] Chandra, A. K.; Hirschberg, D. S.; Wong, C. K.: Approximation algorithms for some generalized knapsack problems. Theoretical computer sciences 3, 293-304 (1976) · Zbl 0359.90053
[27] Charon, I.; Hudry, O.: The noising method: A new method for combinatorial optimization. Operations research letters 14, 133-137 (1993) · Zbl 0798.90118
[28] Chu, P.; Beasley, J.: A genetic algorithm for the multidimensional knapsack problem. Journal of heuristics 4, 63-86 (1998) · Zbl 0913.90218
[29] CPLEX Optimization, Inc. (1994), Using the CPLEX callable library and CPLEX mixed integer library, Version 3.0
[30] Crama, Y.; Mazzola, J.: On the strength of relaxations of multidimensional knapsack problems. Infor 32, 219-225 (1994) · Zbl 0823.90093
[31] F. Dammeyer, S. Voss, Application of tabu search strategies for solving multiconstraint zero--one knapsack problems, Working paper, Technische Hochschule Darmstadt, Germany, 1991
[32] Dammeyer, F.; Voss, S.: Dynamic tabu list management using reverse elimination method. Annals of operations research, 31-46 (1993) · Zbl 0775.90290
[33] DASH Associates, 1994, XPRESS-MP User Manual
[34] Dobson, G.: Worst-case analysis of greedy heuristics for integer programming with non-negative date. Mathematics of operations research 7, 515-531 (1982) · Zbl 0498.90061
[35] Drexl, A.: A simulated annealing approach to the multiconstraint zero--one knapsack problem. Computing 40, 1-8 (1988) · Zbl 0638.65053
[36] Dueck, G.; Scheuer, T.: Threshold accepting: A general purpose optimization algorithm. Journal of computational physics 90, 161-175 (1990) · Zbl 0707.65039
[37] G. Dueck, J. Wirshing, Threshold accepting algorithms for multi-constraint 0--1 knapsack problems, Working paper, TR 89 10 016, IBM Heidelberg Scientific Center, Germany, 1989
[38] Dyer, H. E.: Calculating surrogate constraints. Mathematical programming 19, 255-278 (1980) · Zbl 0464.90067
[39] Dyer, M. E.; Frieze, A. M.: Probabilistic analysis of the multidimensional knapsack problem. Mathematics of operations research 14, 162-176 (1989) · Zbl 0676.90046
[40] Echols, R. E.; Cooper, L.: Solution of integer linear programming problems with direct search. Journal of the association for computational machinery 15, 75-84 (1968) · Zbl 0157.50204
[41] Edmonds, J.: Minimum partition of a matroid into independent subsets. Journal of research of the national bureau of standards 69B, 67-72 (1965) · Zbl 0192.09101
[42] J. Etcheberry, C. Conca, E. Stacchetti, An implicit enumeration approach for integer programming using subgradient optimization, Working paper no 78-04-c, Universidad de Chile, 1978
[43] Escudero, L. F.; Martello, S.; Toth, P.: A framework for tightening 0--1 programs based on extensions of pure 0--1 KP and SS problems. Proceedings of the 4th international IPCO conference, 110-123 (1996)
[44] Iii, H. Everett: Generalized Lagrange multiplier method for solving problems of optimum allocation of resources. Operations research 11, 399-417 (1963) · Zbl 0113.14202
[45] Faaland, B.; Hillier, F. S.: Interior path methods for heuristic integer programming procedures. Operations research 27, 1069-1087 (1979) · Zbl 0442.90062
[46] Fayard, D.; Plateau, G.: Reduction algorithm for single and multiple constraints 0--1 linear programming problems. (1977)
[47] Fayard, D.; Plateau, G.: Algorithm 47: an algorithm for the solution of the knapsack problem. Computing 28, 269-287 (1982) · Zbl 0468.90045
[48] Fischer, M. L.: Worst-case analysis of heuristic algorithms. Management sciences 26, 1-17 (1980) · Zbl 0448.90041
[49] Fischer, M. L.: The Lagrangean relaxation method for solving integer programming problems. Management sciences 27, 1-18 (1981)
[50] Fontanari, J. F.: A statistical analysis of the knapsack problem. Journal of physics A----mathematical and general 28, 4751-4759 (1995) · Zbl 0867.90080
[51] Fontarani, J. F.; Meir, R.: The statistical mechanics of the Ising perceptron. Journal of physics A----mathematical and general 26, 1077-1089 (1993)
[52] A. Fréville, Contribution à l’optimisation en nombres entiers, Habilitation à diriger des recherches, Université de Paris-Nord, France, 1991
[53] A. Fréville, S. Hanafi, Bornes duales robustes pour le sac à dos bi-dimensionel en variables 0--1, Working paper presented at FRANCORO III, Québec, Canada, May 2001
[54] A. Fréville, G. Plateau, Méthodes heuristiques performantes pour les programmes en variables 0--1, Working paper, ANO-91, Université de Lille 1, France, 1982
[55] Fréville, A.; Plateau, G.: Heuristics and reduction methods for multiple constraints 0--1 linear programming problems. European journal of operational research 24, 206-215 (1986) · Zbl 0579.90066
[56] Fréville, A.; Plateau, G.: Hard 0--1 multiknapsack test problems for size reduction methods. Investigacion operativa 1, 251-270 (1990)
[57] Fréville, A.; Plateau, G.: SAC-à-DoS multidimensionel en variables 0--1: encadrement de la somme des variables à l’optimum. RAIRO operations research 27, 169-187 (1993) · Zbl 0777.90032
[58] Fréville, A.; Plateau, G.: An exact search for the solution of the surrogate dual of the 0--1 bidimensional knapsack problem. European journal of operational research 68, 413-421 (1993) · Zbl 0782.90069
[59] Fréville, A.; Plateau, G.: An efficient preprocessing procedure for the multidimensional knapsack problem. Discrete applied mathematics 49, 189-212 (1994) · Zbl 0802.90077
[60] Fréville, A.; Plateau, G.: The 0--1 bidimensional knapsack problem: towards an efficient high-level primitive tool. Journal of heuristics 2, 147-167 (1996) · Zbl 0870.90084
[61] Frieze, A. M.; Clarke, M. R.: Approximate algorithms for the m-dimensional 0--1 knapsack problem: worst-case and probabilistic analyses. European journal of operational research 15, 100-109 (1984) · Zbl 0532.90075
[62] Gabrel, V.; Knippel, A.; Minoux, M.: Exact solutions of multicommodity network optimization problems with general step cost functions. Operations research letters 25, 15-23 (1999) · Zbl 0967.90012
[63] Gavish, B.; Pirkul, H.: Allocation of databases and processors in a distributed data processing. Management of distributed data processing, 215-231 (1982)
[64] Gavish, B.; Pirkul, H.: Efficient algorithms for solving multiconstraint zero--one knapsack problems to optimality. Mathematical programming 31, 78-105 (1985) · Zbl 0571.90065
[65] Gearing, C. E.; Swart, W. W.; Var, T.: Determining the optimal investment policy for the tourism sector of a developing country. Management sciences 20, 487-497 (1973)
[66] Gens, G. V.; Levner, E. V.: Complexity and approximation algorithms for combinatorial problems: A survey, central economic and mathematical institute. (1979) · Zbl 0414.90060
[67] Van De Gerr, S.; Stougie, L.: On rates of convergence and asymptotic normality in the multiknapsack problem. Mathematical programming 51, 349-358 (1991) · Zbl 0753.90045
[68] Geoffrion, A. M.: An improved implicit enumeration approach for integer programming. Operations research 17, 437-454 (1969) · Zbl 0174.20801
[69] A.M. Geoffrion, A.B. Nelson, Users instructions for (0--1) integer linear programming code RIP30C”, Rand Memorandum RM-5627-PR, 1968
[70] Gilmore, P. C.; Gomory, R. E.: The theory and computation of knapsack functions. Operations research 14, 1045-1075 (1966) · Zbl 0173.21502
[71] Glover, F.: A multiphase-dual algorithm for the zero--one integer programming problem. Operations research 13, 879-919 (1965) · Zbl 0163.41301
[72] Glover, F.: Surrogate constraints. Operations research 16, 741-749 (1968) · Zbl 0165.22602
[73] Glover, F.: Surrogate constraints duality in mathematical programming. Operations research 23, 434-451 (1975) · Zbl 0314.90093
[74] Glover, F.: Heuristics for integer programming using surrogate constraints. Decision sciences 8, 156-166 (1977)
[75] Glover, F.: Tabu search, part 1. ORSA journal on computing 1, 190-206 (1989) · Zbl 0753.90054
[76] F. Glover, Tutorial on surrogate constraint approaches for optimization in graphs, Working paper, Hearin Center for Enterprise Science, University of Mississippi, USA, 2001
[77] Glover, F.; Kochenberger, G. A.: Critical event tabu search for multidimensional knapsack problems. Meta-heuristics: theory and applications, 407-427 (1996) · Zbl 0877.90055
[78] Glover, F.; Sherali, H.; Lee, Y.: Generating cuts from surrogate constraint analysis for zero--one and multiple choice programming. Computational optimization and applications 8, 154-184 (1977) · Zbl 0886.90103
[79] J. Gotlieb, On the effectivity of evolutionary algorithms for multidimensional knapsack problem, Proceedings of the 4th European Conference of Artificial Evolution, Dunkerque, France, LNCS no. 1829, 1999, pp. 23--27
[80] C.J. Green, Two algorithms for solving independent multidimensional knapsack problems, Management Sciences Report, no. 110, Carnegie institute of Technology, Graduate School of Industrial Administration, Pittsburgh, USA, 1967
[81] Greenberg, H.; Pierskalla, W.: Surrogate mathematical programs. Operations research 18, 924-939 (1970) · Zbl 0232.90059
[82] M. Guignard, G. Plateau, G. Yu, An application of Lagrangean decomposition to the 0--1 biknapsack problem, Working paper, Wharton School, University of Pennsylvania, presented at TIMS/ORSA Meeting, Vancouver, Canada, 1989
[83] Guignard, M.; Spielberg, K.: Search techniques with adaptive features for certain integer and mixed integer programming problems. Proceedings information processing 1968, 238-244 (1969) · Zbl 0203.48801
[84] Guignard, M.; Spielberg, K.: Logical reduction methods in zero--one programming (minimal preferred variables). Operations research 29, 49-74 (1981) · Zbl 0452.90044
[85] S. Hanafi, Contribution à la résolution de problèmes duaux de grande taille en optimisation combinatoire, PhD thesis, University of Valenciennes, France, 1993
[86] Hanafi, S.; Fréville, A.: An efficient tabu search approach for the 0--1 multidimensional knapsack problem. European journal of operational research 106, 659-675 (1998) · Zbl 0991.90089
[87] Hanafi, S.; Fréville, A.: Extension of reverse elimination method through a dynamic management of the tabu list. RAIRO operations research 35, 251-267 (2001) · Zbl 1014.90079
[88] Hanafi, S.; Fréville, A.; El Abdellaoui, A.: Comparison of heuristics for the 0--1 multidimensional knapsack problem. Meta-heuristics: theory and applications, 449-466 (1996) · Zbl 0877.90056
[89] Haul, C.; Voss, S.: Using surrogate constraints in genetic algorithms for solving multidimensional knapsack problems. Advances in computational and stochastic optimization, logic programming, and heuristic search, 235-251 (1998) · Zbl 0891.68042
[90] Held, M.; Karp, R. M.: The traveling salesman problem and minimum spanning trees. Operations research 18, 1138-1162 (1970) · Zbl 0226.90047
[91] Held, M.; Karp, R. M.: The traveling salesman problem and minimum spanning trees: part II. Mathematical programming 1, 6-25 (1971) · Zbl 0232.90038
[92] Hill, R.; Reilly, C.: The effects of coefficient correlation structure in two-dimensional knapsack problems on solution procedure performance. Management sciences 46, 302-317 (2000) · Zbl 1231.90323
[93] Hillier, F. S.: Efficient heuristic procedures for integer linear programming with an interior. Operations research 17, 600-637 (1969) · Zbl 0176.49902
[94] Ibaraki, T.: Enumerative approaches to combinatorial optimization----part II. Annals of operations research 11 (1987)
[95] Ibaraki, T.; Ohashi, E.; Mine, H.: A heuristic algorithm for mixed-integer programming problems. Mathematical programming study 2, 115-136 (1974) · Zbl 0353.90061
[96] Ibarra, O. H.; Kim, C. E.: Fast approximation algorithms for the knapsack and sum of subset problems. Journal of association for computing machinery 22, 463-468 (1975) · Zbl 0345.90049
[97] IBM Corporation, Optimization subroutine library, Guide and Reference, 1990
[98] S. Isaka, Double relaxation dynamic programming methods for the multi-dimensional knapsack problem, Master Thesis, Department of Applied Mathematics and Physics, Kyoto University, Japan, 1983
[99] Jeroslow, R. G.; Smith, T. H. C: Experimental results on hillier’s search. Mathematical programming 9, 371-376 (1975) · Zbl 0314.90066
[100] Johnson, E. J.; Nemhauser, G. L.; Savelsbergh, M. W. P: Progress in linear programming-based algorithms for integer programming: an exposition. INFORMS journal on computing 12, 2-23 (2000) · Zbl 1052.90048
[101] Kaplan, S.: Solution of the lorie-savage and similar integer programming problem by the generalized Lagrange multiplier method. Operations research 14, 1130-1136 (1966) · Zbl 0158.38406
[102] Karwan, M. H.; Rardin, R. L.: Some relationships between Lagrangian and surrogate duality in integer programming. Mathematical programming 17, 320-334 (1979) · Zbl 0421.90056
[103] Karwan, M. H.; Rardin, R. L.: Searchability of the composite and multiple surrogate dual functions. Operations research 28, 1251-1257 (1980) · Zbl 0449.90068
[104] Karwan, M. H.; Rardin, R. L.: Surrogate dual multiplier search procedures in integer programming. Operations research 32, 52-69 (1984) · Zbl 0538.90060
[105] Karwan, M. H.; Rardin, R. L.; Sarin, S.: A new surrogate dual multiplier search procedure. Naval research logistics 34, 431-450 (1987) · Zbl 0656.90068
[106] Khuri, S. T.; Batarekh, A.: Heuristics for the integer knapsack problem. Proceedings of the 10th international computer science conference, 161-172 (1990)
[107] Khuri, S.; Back, T.; Heitkotter, J.: The zero/one multiple knapsack problem and genetic algorithms. Proceedings of the 1994 ACM symposium on applied computing, (SAC’99), 188-193 (1994)
[108] D.N. Kleinmuntz, C.E. Kleinmuntz, Multiobjective capital budgeting in not-for-profit hospitals and healthcare systems, Working paper, University of Illinois, Urbana-Champaign, USA, October 2001
[109] Kochenberger, G.; Mccarl, G.; Wymann, F.: A heuristic for general integer programming. Decision sciences 5, 36-44 (1974)
[110] Korte, B.; Schnader, R.: On the existence of fast approximate schemes. Nonlinear programming, 415-437 (1980)
[111] Korutcheva, E.; Opper, M.; Lopez, B.: Statistical mechanics of the knapsack problem. Journal of physics A: mathematics and general 27, L645-L650 (1994) · Zbl 0843.90100
[112] Kwak, W.; Shi, Y.; Lee, H.; Lee, C. F.: Capital budgeting with multiple criteria and multiple decision makers. Review of quantitative finance and accounting 7, 97-112 (1996)
[113] Laguna, M.; Kelly, J. P.; Velarde, J. L. Gonzalez; Glover, F.: Tabu search for the multilevel generalized assignment problem. European journal of operational research 82, 176-189 (1995) · Zbl 0905.90122
[114] Lawler, E. L.: Fast approximation algorithms for knapsack problems. Mathematics of operations research 4, 339-356 (1979) · Zbl 0425.90064
[115] Lee, J. S.; Guignard, M.: An approximate algorithm for multidimensional zero--one knapsack problems: A parametric approach. Management sciences 34, 402-410 (1988) · Zbl 0638.90069
[116] Lemke, C. E.; Spielberg, K.: Direct search algorithms for zero--one and mixed-integer programming. Operations research 15, 892-914 (1967) · Zbl 0168.18201
[117] Lokketangen, A.; Glover, F.: Probabilistic move selection in tabu search for zero--one mixed integer programming problems. Meta-heuristics: theory and applications, 467-487 (1996) · Zbl 0877.90058
[118] Lokketangen, A.; Glover, F.: Solving zero--one mixed integer programming problems using tabu search. Special issue on tabu search, European journal of operational research 106, 624-658 (1998) · Zbl 0991.90091
[119] Lokketangen, A.; Jornsten, K.; Storoy, S.: Tabu search within a pivot and complement framework. International transactions of operations research 1, 305-316 (1994)
[120] Lorie, J.; Savage, L. J.: Three problems in capital rationing. Journal of business 28, 229-239 (1955)
[121] Loulou, R.; Michaelides, E.: New greedy-like heuristics for the multidimensional 0--1 knapsack problem. Operations research 27, 1101-1114 (1979) · Zbl 0442.90058
[122] Magazine, M. J.; Chern, M. S.: A note on approximation schemes for multidimensional knapsack problems. Mathematics of operations research 9, 244-247 (1984) · Zbl 0589.90059
[123] Magazine, M. J.; Oguz, O.: A fully polynomial approximation algorithm for the 0--1 knapsack problem. European journal of operational research 8, 270-273 (1981) · Zbl 0473.90056
[124] Magazine, M. J.; Oguz, O.: A heuristic algorithm for the multidimensional zero--one knapsack problem. European journal of operational research 16, 319-326 (1984) · Zbl 0532.90070
[125] Mamer, J. W.; Schilling, K. E.: On the growth of random knapsacks. Discrete applied mathematics 28, 223-230 (1990) · Zbl 0703.90065
[126] Manne, A. S.; Markowitz, H. M.: On the solution of discrete programming problems. Econometrica 25, 84-110 (1957) · Zbl 0078.34005
[127] B. Mans, Contribution à l’algorithmique non numérique parallèle: Parallélisation de méthodes de recherche arborescente, Thèse de Doctorat, Université Paris 6, France, 1992
[128] R.E. Marsten and T.L. Morin, MMPD, a computer code for solving multiconstraint knapsack problems in integer variables, Working paper, Operations Research Center, MIT, Cambridge, USA, 1976
[129] Marsten, R. E.; Morin, T. L.: Optimal solutions found for senju and toyoda’0/1 integer programming problems. Management sciences 23, 1364-1365 (1977)
[130] Marsten, R. E.; Morin, T. L.: A hybrid approach to discrete mathematical programming. Mathematical programming 14, 21-40 (1978) · Zbl 0388.90055
[131] Martello, S.; Toth, P.: A new algorithm for the 0--1 knapsack problem. Management sciences 34, 633-644 (1988) · Zbl 0645.90054
[132] Martello, S.; Toth, P.: Knapsack problems: algorithms and computer implementations. Series in discrete mathematics and optimization (1990) · Zbl 0708.68002
[133] Martello, S.; Toth, P.: Upper bounds and algorithms for hard 0--1 knapsack problems. Operations research 45, 768-778 (1997) · Zbl 0902.90125
[134] Martello, S.; Pisinger, D.; Toth, P.: New trends in exact algorithms for the 0--1 knapsack problem. European journal of operational research 123, 325-336 (1999) · Zbl 0961.90090
[135] Mcmillan, C.; Plaine, D. R.: Resource allocation via 0--1 programming. Decision sciences 4, 119-132 (1973)
[136] Meanti, M.; Kan, A. H. G Rinnooy; Stougie, L.; Vercellis, C.: A probabilistic analysis of the multiknapsack value function. Mathematical programming 46, 237-247 (1990) · Zbl 0694.90072
[137] Meier, H.; Christofides, N.; Salkin, G.: Capital budgeting under uncertainty----an integrated approach using contingent claims analysis and integer programming. Operations research 49, 196-206 (2001) · Zbl 1163.90665
[138] M. Nediak and J. Eckstein, Pivot, cut and dive: A heuristic for 0--1 mixed integer programming, Rutcor research report, Rutgers University, USA, October 2001
[139] Nemhauser, G. L.; Savelsbergh, M. W. P; Sigismondi, G. C.: MINTO, a mixed integer optimizer. Operations research letters 15, 47-58 (1993)
[140] Nemhauser, G. L.; Ullmann, Z.: Discrete dynamic programming and capital allocation. Management sciences 15, 494-505 (1969) · Zbl 1231.90339
[141] S. Niar, A. Fréville, A parallel tabu search algorithm for the 0--1 multidimensional knapsack problem, International Parallel Processing Symposium’97 IEEE Computer Society Press, Suisse, 1997, pp. 512--516
[142] Ohlssen, M.; Peterson, C.; Soderberg, B.: Neural networks for optimization problems with inequality constraints: the knapsack problem. Neural computation 5, 331-339 (1993)
[143] C. Oliva, P. Michelon, C. Artigues, Integrating linear programming and constraint programming techniques for solving mixed-integer programming problems, Working paper, University of Avignon, presented at INFORMS 2001 Annual Meeting, Miami Beach, USA, 4--7 November 2001
[144] M.A. Osorio, F. Glover, P. Hammer, Cutting and surrogate constraint analysis for improved multidimensional knapsack solutions, Research report, University of Puebla, Mexico, presented at IFORS, Mexico, September 2000, Annals of Operational Research, submitted for publication · Zbl 1028.90042
[145] Padberg, M.: (1,k)-configurations and facets for packing problems. Mathematical programming 18, 94-99 (1980) · Zbl 0431.90050
[146] Petersen, C. C.: Computational experience with variants of the balas algorithm applied to the selection of R&D projects. Management sciences 13, 736-750 (1967)
[147] Petersen, C. C.: A capital budgeting heuristic algorithm using exchange operations. AIIE transactions 6, 143-150 (1974)
[148] Pirkul, H.: A heuristic solution procedure for the multiconstraint zero--one knapsack problem. Naval research logistics 34, 161-172 (1987) · Zbl 0609.90092
[149] Pisinger, D.: An expanding-core algorithm for the exact 0--1 knapsack problem. European journal of operational research 87, 175-187 (1995) · Zbl 0914.90199
[150] Pisinger, D.: A minimal algorithm for the bounded knapsack problem. ORSA journal on computing 12, 75-84 (2000) · Zbl 1034.90010
[151] Plateau, A.; Tachat, D.; Tolla, P.: A hybrid search combining interior point methods and metaheuristics for 0--1 programming. International transactions in operational research 9, 731-746 (2002) · Zbl 1044.90047
[152] G. Plateau, Réduction de la taille des problèmes linéaires en variables 0--1, Working paper, ANO-71, Université de Lille 1, France, 1976
[153] Plateau, G.; Elkihel, M.: A hybrid method for the 0--1 knapsack problem. Methods of operations research 49, 277-293 (1985) · Zbl 0564.90037
[154] G. Plateau, C. Roucairol, A supercomputer algorithm for the 0--1 multiknapsack problem, in: R. Sharda, B. Golden, E. Wasil, O. Balei, W. Stewart (Eds.), Impacts of Recent Computer Advances on Operations Research, Operations Research Series, 1989, pp. 144--157
[155] Pursglove, C. J.; Boffey, T. B.: Heuristic improvement methods: how should starting solutions be chosen. Mathematical programming study 13, 135-142 (1980) · Zbl 0442.90057
[156] G.R. Raidl, An improved genetic algorithm for the multiconstraint knapsack problem, in: Proceedings of the 5th IEEE International Conference on Evolutionary Computation, 1998, pp. 207--211
[157] Reilly, C. H.: Optimization test problems with uniformly distributed coefficients. Proceedings of the 1991 winter simulation conference, 866-874 (1991)
[158] Kan, A. H. G Rinnooy; Stougie, L.; Vercellis, C.: A class of generalized greedy algorithms for the multi-knapsack problem. Discrete applied mathematics 42, 279-290 (1993) · Zbl 0785.90072
[159] Roth, R. H.: An approach to solving linear discrete optimization problems. Journal of the association for computing machinery 17, 303-313 (1970) · Zbl 0195.20703
[160] Savelsbergh, M. W. P: Preprocessing and probing techniques for mixed integer programming problems. ORSA journal of computing 6, 445-454 (1994) · Zbl 0814.90093
[161] Schilling, K. E.: The growth of m-constraint random knapsacks. European journal of operational research 46, 109-112 (1990) · Zbl 0708.90057
[162] Schilling, K. E.: Random knapsacks with many constraints. Discrete applied mathematics 48, 163-174 (1994) · Zbl 0791.90038
[163] Senju, S.; Toyada, Y.: An approach to linear programming problems with 0--1 variables. Management sciences 15, 196-207 (1968)
[164] Shani, S.: Approximate algorithms for the 0--1 knapsack problem. Journal of association for computing machinery 22, 115-124 (1975) · Zbl 0362.90066
[165] Shih, W.: A branch and bound method for the multiconstraint zero--one knapsack problem. Journal of the operations research society 30, 369-378 (1979) · Zbl 0411.90050
[166] J.A. Sikorski, A branch-and-bound solver for multiconstraint 0--1 knapsack problems, Working paper, Systems Research Institute, Polish Academy of Sciences, Warszawa, Poland, 1994
[167] 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
[168] Spielberg, K.: Algorithms for the simple plant location problem with some side conditions. Operations research 17, 85-111 (1969) · Zbl 0165.54104
[169] Spielberg, K.: Plant location with generalized search origin. Management science 19, 165-168 (1969)
[170] Straszak, A.; Libura, M.; Siborski, J.; Wagner, D.: Computer-assisted constrained approval voting. Group decision and negotiation 2, 375-385 (1993)
[171] Szkatula, K.: The growth of multi-constraint random knapsacks with various right-hand sides of the constraints. European journal of operational research 73, 199-204 (1994)
[172] Szkatula, K.: The growth of multi-constraint random knapsacks with large right-hand sides of the constraints. Operations research letters 21, 25-30 (1997) · Zbl 0885.90084
[173] K. Szkatula, How fast the random knapsacks with many constraints grow? Working paper presented at ECCO XIII conference, Capri, Italy, 2000
[174] Thesen, A.: A recursive branch and bound algorithm for the multidimensional knapsack problem. Naval research quarterly 22, 341-353 (1975) · Zbl 0307.90054
[175] Thiel, J.; Voss, S.: Some experiences on solving multiconstraint zero--one knapsack problems with genetic algorithms. Infor 32, 226-242 (1994) · Zbl 0823.90092
[176] Toulouse, M.; Crainic, T. G.; Gendreau, M.: Communication issues in designing cooperative multithread parallel searches. Meta-heuristics: theory and applications, 503-522 (1996) · Zbl 0877.90067
[177] Toyoda, Y.: A simplified algorithm for obtaining approximate solutions to zero--one programming problems. Management sciences 21, 1417-1427 (1975) · Zbl 0307.90056
[178] Trauth, C. A.; Woolsey, R. E.: Integer linear programming: A study in computational effectiveness. Management sciences 15, 481-494 (1969) · Zbl 0172.22302
[179] Vasquez, M.; Hao, J. K.: A logic-constrained knapsack formulation and a tabu algorithm for the daily photograph scheduling of an Earth observation satellite. Computational optimization and applications 20, 137-157 (2001) · Zbl 0983.90082
[180] Vasquez, M.; Hao, J. K.: Une approche hybride pour le SAC à DoS multidimensionel en variables 0--1. RAIRO operations research 35, 415-438 (2001)
[181] Volgenant, A.; Zoon, J. A.: An improved heuristic for multidimensional 0--1 knapsack problems. Journal of the operational research society 41, 963-970 (1990) · Zbl 0724.90044
[182] S. Voss, Tabu search: Applications and prospects, in: D.Z. Du, P.M. Pardalos (Eds.), Network Optimization Problems, 1993, pp. 333--353
[183] Weingartner, H. M.: Mathematical programming and the analysis of capital budgeting problems. (1963)
[184] Weingartner, H. M.; Ness, D. N.: Method for the solution for the multidimensional 0--1 knapsack problem. Operations research 15, 83-103 (1967)
[185] Wyman, F. P.: Binary programming: A decision rule for selecting optimal vs heuristic techniques. The computer journal 16, 135-140 (1973)
[186] Wolsey, L. A.: Heuristic analysis, linear programming and branch and bound. Mathematical programming study 13, 121-134 (1980) · Zbl 0442.90061
[187] J. Yang, A computational study on 0--1 knapsack problems generated under explicit correlation induction, MS Thesis, Department of Industrial and Systems Engineering, The Ohio State University, Columbus, USA, 1994
[188] Zanakis, S. H.: Heuristic 0--1 linear programming: an experimental comparison of three methods. Management sciences 24, 91-104 (1977) · Zbl 0369.90086