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)
The multidimensional 0-1 knapsack problem – bounds and computational aspects. (English) Zbl 1091.90042
Summary: The multidimensional 0-1 knapsack problem (MKP) is a resource allocation model that is one of the most well-known integer programming problems. During the last few decades, an impressive amount of research on the 0-1 knapsack problem has been published in the literature, and efficient special-purpose methods have become available for solving very large-scale instances. However, the multidimensional case has received less attention from the operational research community. Although recent advances have made solving medium size instances possible, solving the NP-hard problem remains a very interesting challenge, especially when the number of constraints increases. This paper surveys the principal results published in the literature concerning both the problem’s theoretical properties and its approximate or exact solutions. The paper focuses on the more recent results-for example, those relevant to surrogate and composite duality, new preprocessing approaches creating enhanced versions of leading commercial software, and efficient metaheuristic-based methods.
90C09Boolean programming
90C59Approximation methods and heuristics
[1]Aboudi, R., A. Hallefjord, R. Helming, and K. Jornsten. (1989). ”A Note on the Pivot and Complement Heuristic for 0-1 Programming Problems.” Operation Research Letters 8, 21–23. · Zbl 0661.90062 · doi:10.1016/0167-6377(89)90028-X
[2]Aboudi, R. and K. Jornsten. (1994). ”Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristics.” ORSA Journal of Computing 6, 82–93.
[3]Andonov, R., Balev S., A. Fréville, and N. Yanev. (2001). ”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.
[4]Averbakh, I. (1994). ”Probabilistic Properties of the Dual Structure of the Multidimensional Knapsack Problem and Fast Statistically Efficient Algorithms.” Mathematical Programming 65, 311–330. · Zbl 0828.90090 · doi:10.1007/BF01581700
[5]Balas, E., S. Ceria, M. Dawande, F. Margot, and G. Pataki. (2001). ”OCTANE: A New Heuristic for Pure 0-1 Programs.” Operations Research 49, 207–225. · Zbl 1163.90654 · doi:10.1287/opre.
[6]Balas, E. and C.H. Martin. (1980). ”Pivot and Complement–A Heuristic for 0-1 Programming.” Management Sciences 26, 86–96. · Zbl 0442.90060 · doi:10.1287/mnsc.26.1.86
[7]Balas, E. and E. Zemel. (1980). ”An Algorithm for Large Zero-One Knapsack Problems.” Operations Research 28, 1130–1145. · Zbl 0449.90064 · doi:10.1287/opre.28.5.1130
[8]Battiti, R. and G. Tecchiolli. (1992). ”Parallel Biased Search for Combinatorial Optimization: Genetic Algorithms and Tabu Search.” Microprocessors and Microsystems 16, 351–367. · doi:10.1016/0141-9331(92)90003-C
[9]Battiti, R. and G. Tecchiolli. (1994). ”The Reactive Tabu Search.” ORSA Journal on Computing 6, 126– 140.
[10]Battiti, R. and G. Tecchiolli. (1995). ”Local Search with Memory: Benchmarking RTS.” OR-Spektrum 17, 67–86. · Zbl 0843.90094 · doi:10.1007/BF01719249
[11]Beasley, J.E. (1990). ”OR-Library: Distributed Test Problems by Electronic Mail.” Journal of the Operational Research Society 41, 1069–1072 (http://mscmga.ms.ic.ac.uk/info.html).
[12]Beaujon, G.J., S.P. Martin, and C.C. McDonald. (2001). ”Balancing and Optimizing a Portfolio of R&D Projects.” Naval Research Logistics 48, 18–40. · doi:10.1002/1520-6750(200102)48:1<18::AID-NAV2>3.0.CO;2-7
[13]Bixby, R.E., M. Fenelon, Z. Gu, E. Rothberg, and R. Wunderling. (2000). ”MIP: Theory and Practice–Closing the Gap.” Research paper, ILOG CPLEX Division.
[14]Bradley, G.H., P.L. Hammer, and L. Wolsey. (1974). ”Coefficient Reduction for Inequalities in 0-1 Variables.” Mathematical Programming 7, 263–282. · Zbl 0292.90038 · doi:10.1007/BF01585527
[15]Cabot, A.V. (1970). ”An Enumeration Algorithm for Knapsack Problems.” Operations Research 18, 306–311. · Zbl 0195.20801 · doi:10.1287/opre.18.2.306
[16]Chandra A.K., D.S. Hirschberg, and C.K. Wong. (1976). ”Approximation Algorithms for Some Generalized Knapsack Problems.” Theoretical Computer Sciences 3, 293–304. · Zbl 0359.90053 · doi:10.1016/0304-3975(76)90048-7
[17]Chu, P. and J. Beasley. (1998). ”A Genetic Algorithm for the Multidimensional Knapsack Problem.” Journal of Heuristics 4, 63–86. · Zbl 0913.90218 · doi:10.1023/A:1009642405419
[18]CPLEX Optimization, Inc. (1994). ”Using the CPLEX Callable Library and CPLEX Mixed Integer Library.” Version 3.0.
[19]Crama, Y. and J. Mazzola. (1994). ”On the Strength of Relaxations of Multidimensional Knapsack Problems.” INFOR 32, 219–225.
[20]Crowder, H., E. Johnson, and M. Padberg. (1983). ”Solving Large-Scale Zero-One Linear Programming Problems.” Operations Research 31, 803–834. · Zbl 0576.90065 · doi:10.1287/opre.31.5.803
[21]Dammeyer, F. and S. Voss. (1991).”Application of Tabu Search Strategies for Solving Multiconstraint Zero-One Knapsack Problems.” Working paper, Technische Hochschule Darmstadt, Germany.
[22]Dammeyer, F. and S. Voss. (1993). ”Dynamic Tabu List Management Using Reverse Elimination Method.” Annals of Operations Research 31–46.
[23]DASH Associates. (1994). XPRESS-MP User Manual.
[24]Dietrich, B.L. and L.F. Escudero. (1990). ”Coefficient Reduction Procedure for Knapsack-Like Constraints in 0-1 Programs with Variable Upper Bounds.” Operations Research Letters 9, 9–14. · Zbl 0701.90063 · doi:10.1016/0167-6377(90)90034-3
[25]Dietrich, B.L., L.F. Escudero, and F. Chance. (1993). ”Effect Reformulation for 0-1 Programs: Methods and Computational Results.” Discrete Applied Mathematics 42, 147–175. · Zbl 0776.90056 · doi:10.1016/0166-218X(93)90044-O
[26]Dobson, G. (1982). ”Worst-Case Analysis of Greedy Heuristics for Integer Programming with Non-Negative Date.” Mathematics of Operations Research 7, 515–531. · Zbl 0498.90061 · doi:10.1287/moor.7.4.515
[27]Drexl, A. (1988). ”A Simulated Annealing Approach to the Multiconstraint Zero-One Knapsack Problem.” Computing 40, 1–8. · Zbl 0638.65053 · doi:10.1007/BF02242185
[28]Dueck, G. and T. Scheuer. (1990). ”Threshold Accepting: A General Purpose Optimization Algorithm.” Journal of Computational Physics 90, 161–175. · Zbl 0707.65039 · doi:10.1016/0021-9991(90)90201-B
[29]Dueck, G. and J. Wirshing. (1989). ”Threshold Accepting Algorithms for Multi-Constraint 0-1 Knapsack Problems.” Working paper, TR 89 10 016, IBM Heidelberg Scientific Center, Germany.
[30]Dyer, H.E. (1980). ”Calculating Surrogate Constraints.” Mathematical Programming 19, 255–278. · Zbl 0464.90067 · doi:10.1007/BF01581647
[31]Dyer, M.E. and A.M. Frieze. (1989). ”Probabilistic Analysis of the Multidimensional Knapsack Problem.” Mathematics of Operations Research 14, 162–176. · Zbl 0676.90046 · doi:10.1287/moor.14.1.162
[32]Escudero, L.F., S. Martello, and P. Toth. (1996). ”A Framework for Tightening 0-1 Programs Based on Extensions of Pure 0-1 KP and SS Problems.” In E. Balas and J. Clausen, (eds.), Proceedings of the 4th international IPCO Conference, Berlin: Springer, pp. 110–123.
[33]Fayard, D. and G. Plateau. (1977). ”Reduction Algorithm for Single and Multiple Constraints 0-1 Linear Programming Problems.” In Proceedings of Congress Methods of Mathematical Programming, Zakopane, Poland.
[34]Fayard, D. and G. Plateau. (1982). ”Algorithm 47: An Algorithm for the Solution of the Knapsack Problem.” Computing 28, 269–287. · Zbl 0475.90062 · doi:10.1007/BF02241754
[35]Fischer, M.L. (1980). ”Worst-Case Analysis of Heuristic Algorithms.” Management Sciences 26, 1–17. · Zbl 0448.90041 · doi:10.1287/mnsc.26.1.1
[36]Fischer, M.L. (1981). ”The Lagrangean Relaxation Method for Solving Integer Programming Problems.” Management Sciences 27, 1–18. · Zbl 0466.90054 · doi:10.1287/mnsc.27.1.1
[37]Fontarani, J.F. (1995). ”A Statistical Analysis of the Knapsack Problem.” Journal of Physics A–Mathematical and General 28, 4751–4759. · Zbl 0867.90080 · doi:10.1088/0305-4470/28/17/011
[38]Fontarani, J.F. and R. Meir. (1993). ”The Statistical Mechanics of the Ising Perceptron.” Journal of Physics A–Mathematical and General 26, 1077–1089. · doi:10.1088/0305-4470/26/5/027
[39]Fréville, A. (2003). ”The Multidimensional 0-1 Knapsack Problem: An Overview.” Invited Paper to Appear in European Journal of Operational Research.
[40]Fréville, A. and S. Hanafi (2001). ”Bornes duales robustes pour le sac à dos bi-dimensionnel en variables 0-1.” Working paper presented at FRANCORO III, Québec, Canada, May 2001.
[41]Fréville, A. and F. Malca (2002). ”Comparaison de méthodes pour la résolution du dual agrégé du sac à dos multidimensionnel en variables 0-1.” Rapport de recherche n–2002, Université de Valenciennes et du Hainaut-Cambrésis, France.
[42]Fréville, A. et G. Plateau. (1982). ”Méthodes heuristiques performantes pour les programmes en variables 0-1.” Working paper, ANO-91, Université de Lille 1, France.
[43]Fréville, A. and G. Plateau. (1986). ”Heuristics and Reduction Methods for Multiple Constraints 0-1 Linear Programming Problems.” European Journal of Operational Research, 24, 206–215. · Zbl 0579.90066 · doi:10.1016/0377-2217(86)90042-1
[44]Fréville, A. and G. Plateau. (1990). ”Hard 0-1 Multiknapsack Test Problems for Size Reduction Methods.” Investigacion Operativa 1, 251–270.
[45]Fréville, A. and G. Plateau. (1993a). ”Sac-à-dos Multidimensionnel en Variables 0-1: Encadrement de la somme des Variables à l’optimum.” RAIRO Operations Research 27, 169–187.
[46]Fréville, A. and G. Plateau. (1993b). ”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. · Zbl 0782.90069 · doi:10.1016/0377-2217(93)90197-U
[47]Fréville, A. and G. Plateau. (1994). ”An Efficient Preprocessing Procedure for the Multidimensional Knapsack Problem.” Discrete Applied Mathematics 49, 189–212. · Zbl 0802.90077 · doi:10.1016/0166-218X(94)90209-7
[48]Fréville, A. and G. Plateau. (1996). ”The 0-1 Bidimensional Knapsack Problem: Towards An Efficient High-Level Primitive Tool.” Journal of Heuristics 2, 147–167.
[49]Frieze, A.M. and M.R. Clarke. (1984). ”Approximate Algorithms for the m-Dimensional 0-1 Knapsack Problem: Worst-Case and Probabilistic Analyses.” European Journal of Operational Research 15, 100–109. · Zbl 0532.90075 · doi:10.1016/0377-2217(84)90053-5
[50]Gabrel, V., A. Knippel, and M. Minoux. (1999). ”Exact Solutions of Multicommodity Network Optimization Problems with General Step Cost Functions.” Operations Research Letters 25, 15–23. · Zbl 0967.90012 · doi:10.1016/S0167-6377(99)00020-6
[51]Gabrel, V. and M. Minoux (2002). ”A Scheme for Exact Separation of Extended Cover Inequalities and Application to Multidimensional Knapsack Problem.” Operations Research Letters.
[52]Gavish, B. and H. Pirkul. (1985). ”Efficient Algorithms for Solving Multiconstraint Zero-One Knapsack Problems to Optimality.” Mathematical Programming 31, 78–105. · Zbl 0571.90065 · doi:10.1007/BF02591863
[53]Gens, G.V. and E.V. Levner. (1979). ”Complexity and Approximation Algorithms for Combinatorial Problems: A Survey.” Central economic and Mathematical Institute, Academy of Sciences of the USSR, Moscow.
[54]Geoffrion, A.M. (1974). ”The Lagrangean Relaxation for Integer Programming.” Mathematical Programming Study 2, 82–114.
[55]van de Gerr, S., L. Stougie. (1991). ”On Rates of Convergence and Asymptotic Normality in the Multiknapsack Problem.” Mathematical Programming 51, 349–358. · Zbl 0753.90045 · doi:10.1007/BF01586944
[56]Gilmore P.C. and R.E. Gomory. (1966). ”The Theory and Computation of Knapsack Functions.” Operations Research 14, 1045–1075. · Zbl 0173.21502 · doi:10.1287/opre.14.6.1045
[57]Glover, F. (1965). ”A Multiphase-Dual Algorithm for the Zero-One Integer Programming Problem.” Operations Research 13, 879–919. · Zbl 0163.41301 · doi:10.1287/opre.13.6.879
[58]Glover, F. (1968). ”Surrogate Constraints.” Operations Research 16, 741–749. · Zbl 0165.22602 · doi:10.1287/opre.16.4.741
[59]Glover, F. (1975). ”Surrogate Constraints Duality in Mathematical Programming.” Operations Research 23, 434–451. · Zbl 0314.90093 · doi:10.1287/opre.23.3.434
[60]Glover, F. (1977). ”Heuristics for Integer Programming Using Surrogate Constraints.” Decision Sciences 8, 156–166. · doi:10.1111/j.1540-5915.1977.tb01074.x
[61]Glover, F. (1986). ”Future Paths for Integer Programming and Links to Artificial Intelligence.” Computers and Operations Research 19, 533–549. · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
[62]Glover, F. (1989). ”Tabu Search, Part 1.” ORSA Journal on Computing 1, 190–206.
[63]Glover, F. (2001). ”Tutorial on Surrogate Constraint Approaches for Optimization in Graphs.” Working paper, Hearin Center for Enterprise Science, University of Mississippi, USA.
[64]Glover, F. (2003). ”Exploiting Nested Inequalities and Surrogate Constraint.” Private communication.
[65]Glover, F. and G.A. Kochenberger. (1996). ”Critical Event Tabu Search for Multidimensional Knapsack Problems.” In I.H. Osman and J.P. Kelly (eds.), Meta-heuristics: Theory and Applications. Kluwer Academic Publishers, pp. 407–427.
[66]Glover, F., Sherali H, and Y. Lee. (1997). ”Generating Cuts from Surrogate Constraint Analysis for Zero-One and Multiple Choice Programming.” Computational Optimization and Applications 8, 154– 184. · Zbl 0886.90103 · doi:10.1023/A:1008621204567
[67]Gotlieb, J. (1999). ”On the Effectivity of Evolutionary Algorithms for Multidimensional Knapsack Problem.” Proceedings of Artificial Evolution (forth coming).
[68]Green, C.J. (1967). ”Two Algorithms for Solving Independent Multidimensional Knapsack Problems.” Management Sciences Report n110, Carnegie institute of Technology, Graduate School of Industrial Administration, Pittsburgh, USA.
[69]Greenberg, H. and W. Pierskalla. (1970). ”Surrogate Mathematical Programs.” Operations Research 18, 924–939. · Zbl 0232.90059 · doi:10.1287/opre.18.5.924
[70]Guignard, M. and S. Kim. (1987a). ”Lagrangean Decomposition: A Model Yielding Stronger Lagrangean Bounds.” Mathematical Programming Study 39, 215–228. · Zbl 0638.90074 · doi:10.1007/BF02592954
[71]Guignard, M. and S. Kim. (1987b). ”Lagrangean Decomposition for Integer Programming: Theory and Applications.” RAIRO 21, 307–323.
[72]Guignard, M. and K. Spielberg. (1969). ”Search Techniques with Adaptive Features for Certain Integer and Mixed Integer Programming Problems.” Proceedings Information Processing 1968, Edinburgh, North Holland Publishing Company, pp. 238–244.
[73]Guignard, M. and K. Spielberg. (1981), ”Logical Reduction Methods in Zero-One Programming (Minimal Preferred Variables).” Operations Research 29, 49–74. · Zbl 0452.90044 · doi:10.1287/opre.29.1.49
[74]Hammer, P., M. Padberg, and U. Peled. (1975). ”Constraint Pairing in Integer Programming.” INFOR 13, 68–81.
[75]Hanafi, S. (1993). ”Contribution à la Résolution de Problèmes Duaux de Grande Taille en Optimisation Combinatoire.” PhD thesis, University of Valenciennes, France.
[76]Hanafi, S. and A. Fréville. (1998). ”An Efficient Tabu Search Approach for the 0-1 Multidimensional Knapsack Problem.” European Journal of Operational Research 106, 659–675. · Zbl 0991.90089 · doi:10.1016/S0377-2217(97)00296-8
[77]Hanafi, S. and A. Fréville (2001). ”Extension of Reverse Elimination Method Through a Dynamic Management of the Tabu List.” RAIRO Operations Research 35, 251–267. · Zbl 1014.90079 · doi:10.1051/ro:2001113
[78]Haul, C. and S. Voss. (1998). ”Using Surrogate Constraints in Genetic Algorithms for Solving Multidimensional Knapsack Problems.” in D.L. Woodruff (ed.), Advances in Computational and Stochastic Optimization, Logic Programming, and Heuristic Search, Kluwer Academic Publishers, pp. 235–251.
[79]Hill, R. and C. Reilly (2000). ”The Effects of Coefficient Correlation Structure in Two-Dimensional Knapsack Problems on Solution Procedure Performance.” Management Sciences 46, 302–317. · Zbl 1231.90323 · doi:10.1287/mnsc.46.2.302.11930
[80]Hillier, F.S. (1969). ”Efficient Heuristic Procedures for Integer Linear Programming with an Interior.” Operations Research 17, 600–637. · Zbl 0176.49902 · doi:10.1287/opre.17.4.600
[81]Ibaraki, T. (1987). ”Enumerative Approaches to Combinatorial Optimization–Part II.” Annals of Operations Research vol. 11.
[82]Ibarra, O.H. and C.E. Kim. (1975). ”Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems.” Journal of Association for Computing Machinery 22, 463–468.
[83][97] IBM Corporation. (1990). Optimization subroutine library, Guide and Reference.
[84]Ibaraki, T. and S. Isaka. (1983). ”Double Relaxation Dynamic Programming Methods for the Multi-Dimensional Knapsack Problem.” Master Thesis, Department of Applied Mathematics and Physics, Kyoto University, Japan.
[85]Johnson, E.J., G.L. Nemhauser, and M.W.P. Savelsbergh (2000). ”Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition.” INFORMS Journal on Computing 12, 2–23. · Zbl 1052.90048 · doi:10.1287/ijoc.
[86]Karwan, M.H. and R.L. Rardin. (1979). ”Some Relationships Between Lagrangian and Surrogate Duality in Integer Programming.” Mathematical Programming 17, 320–334. · Zbl 0421.90056 · doi:10.1007/BF01588253
[87]Karwan, M.H. and R.L. Rardin. (1980). ”Searchability of the Composite and Multiple Surrogate Dual Functions.” Operations Research 28, 1251–1257. · Zbl 0449.90068 · doi:10.1287/opre.28.5.1251
[88]Karwan, M.H. and R.L. Rardin. (1984). ”Surrogate Dual Multiplier Search Procedures in Integer Programming.” Operations Research 32, 52–69. · Zbl 0538.90060 · doi:10.1287/opre.32.1.52
[89]Karwan, M.H. R.L. Rardin, and S. Sarin. (1987). ”A New Surrogate Dual Multiplier Search Procedure.” Naval Research Logistics 34, 431–450. · doi:10.1002/1520-6750(198706)34:3<431::AID-NAV3220340309>3.0.CO;2-P
[90]Khuri, S., T. Back, and J. Heitkotter. (1994). ”The Zero/One Multiple Knapsack Problem and Genetic Algorithms.” Proceedings of the 1994 ACM Symposium on Applied Computing (SAC’99), ACM Press, pp. 188–193.
[91]Kianfar, F. (1971). ”Stronger Inequalities for 0-1 Integer Programming Using Knapsack Constraints.” Operations Research 19, 1374–1392. · Zbl 0236.90056 · doi:10.1287/opre.19.6.1374
[92]Kleinmuntz, D.N. and C.E. Kleinmuntz. (2001). ”Multiobjective Capital Budgeting in Not-for-Profit Hospitals and Healthcare Systems.” Working paper, University of Illinois, Urbana-Champaign, USA, October 2001.
[93]Kochenberger, G., G. McCarl, and F. Wyman. (1974). ”A Heuristic for General Integer Programming.” Decision Sciences 5, 36–44. · doi:10.1111/j.1540-5915.1974.tb00593.x
[94]Korte, B. and R. Schnader. (1980). ”On the Existence of Fast Approximate Schemes.” In O.L. Mangasarian, R.R. Meyer, S.M. Robinson (eds.), Nonlinear Programming Academic Press, pp. 415–437.
[95]Korutcheva, E., M. Opper, and B. Lopez. (1994). ”Statistical Mechanics of the Knapsack Problem.” Journal of Physics A: Mathematics and General 27, L645–L650. · Zbl 0843.90100 · doi:10.1088/0305-4470/27/18/001
[96]Kwak, W., Y. Shi, H. Lee, and C.F. Lee. (1996). ”Capital Budgeting with Multiple Criteria and Multiple Decision Makers.” Review of Quantitative Finance and Accounting 7, 97–112. · doi:10.1007/BF00246001
[97]Laguna, M., J.P. Kelly, J.L. Gonzalez Velarde, and F. Glover. (1995). ”Tabu Search for the Multilevel Generalized Assignment Problem.” European Journal of Operational Research 82, 176–189. · Zbl 0905.90122 · doi:10.1016/0377-2217(93)E0174-V
[98]Lawler, E.L. (1979). ”Fast Approximation Algorithms for Knapsack Problems.” Mathematics of Operations Research 4, 339–356. · Zbl 0425.90064 · doi:10.1287/moor.4.4.339
[99]Lemke, C.E. and K. Spielberg. (1967). ”Direct Search Algorithms for Zero-One and Mixed-Integer Programming.” Operations Research 15, 892–914. · Zbl 0168.18201 · doi:10.1287/opre.15.5.892
[100]Lokketangen, A. and F. Glover. (1996). ”Probabilistic Move Selection in Tabu Search for Zero-One Mixed Integer Programming Problems.” In I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics: Theory & Applications Kluwer Academic Publishers, pp. 467–487.
[101]Lokketangen, A. and F. Glover. (1998). ”Solving Zero-One Mixed Integer Programming Problems Using Tabu Search.” Special Issue on Tabu Search, European journal of Operational Research 106, 624– 658.
[102]Lokketangen, A. K. Jornsten, and S. Storoy. (1994), ”Tabu Search Within a Pivot and Complement Framework.” International transactions of Operations Research 1, 305–316. · Zbl 0854.90102 · doi:10.1016/0969-6016(94)90031-0
[103]Lorie, J. and L.J. Savage. (1955). ”Three Problems in Capital Rationing.” Journal of Business 28, 229– 239. · doi:10.1086/294081
[104]Magazine, M.J. and M.S. Chern. (1984). ”A Note on Approximation Schemes for Multidimensional Knapsack Problems.” Mathematics on Operations Research 9, 244–247. · Zbl 0589.90059 · doi:10.1287/moor.9.2.244
[105]Magazine, M.J. and O. Oguz. (1981). ”A Fully Polynomial Approximation Algorithm for the 0-1 Knapsack Problem.” European Journal of Operational Research 8, 270–273. · Zbl 0473.90056 · doi:10.1016/0377-2217(81)90175-2
[106]Magazine, M.J. and O. Oguz. (1984). ”A Heuristic Algorithm for the Multidimensional Zero-One Knapsack Problem”. European Journal of Operational Research 16, 319–326. · Zbl 0532.90070 · doi:10.1016/0377-2217(84)90286-8
[107]Mamer, J.W. and K.E. Schilling. (1990). ”On the Growth of Random Knapsacks.” Discrete Applied Mathematics 28, 223–230. · Zbl 0703.90065 · doi:10.1016/0166-218X(90)90004-V
[108]Manne, A.S. and H.M. Markowitz. (1957). ”On the Solution of Discrete Programming Problems.” Econometrica 25, 84–110. · Zbl 0078.34005 · doi:10.2307/1907744
[109]Marsten, R.E. and T.L. Morin. (1976). ”MMPD, a Computer Code for Solving Multiconstraint Knapsack Problems in Integer Variables.” Working paper, Operations Research Center, MIT, Cambridge, USA.
[110]Marsten, R.E. and T.L. Morin. (1977). ”Optimal Solutions Found for Senju and Toyoda’0/1 Integer Programming Problems.” Management Sciences 23, 1364–1365. · doi:10.1287/mnsc.23.12.1364
[111]Marsten, R.E. and T.L. Morin. (1978). ”A Hybrid Approach to Discrete Mathematical Programming.” Mathematical Programming 14, 21–40. · Zbl 0388.90055 · doi:10.1007/BF01588949
[112]Martello, S. and P. Toth. (1988). ”A New Algorithm for the 0-1 Knapsack Problem.” Management Sciences 34, 633–644. · Zbl 0645.90054 · doi:10.1287/mnsc.34.5.633
[113]Martello, S. and P. Toth. (1990). ”Knapsack Problems: Algorithms and Computer implementations.” In Series in Discrete Mathematics and Optimization, New York. Wiley InterSciences.
[114]Martello, S. and P. Toth. (1997). ”Upper Bounds and Algorithms for Hard 0-1 Knapsack Problems.” Operations Research 45, 768–778. · Zbl 0902.90125 · doi:10.1287/opre.45.5.768
[115]Martello, S., D. Pisinger, and P. Toth. (1999). ”New Trends in Exact Algorithms for the 0-1 Knapsack Problem.” European Journal of Operational Research 123, 325–336. · Zbl 0961.90090 · doi:10.1016/S0377-2217(99)00260-X
[116]Meanti, M., A.H.G. Rinnoy Kan, L. Stougie, and C. Vercellis. (1990). ”A Probabilistic Analysis of the Multiknapsack Value Function.” Mathematical Programming 46, 237–247. · Zbl 0694.90072 · doi:10.1007/BF01585741
[117]Meier, H., N. Christofides, and G. Salkin (2001). ”Capital Budgeting Under Uncertainty–an Integrated Approach Using Contingent Claims Analysis and Integer Programming.” Operations Research 49, 196–206. · Zbl 1163.90665 · doi:10.1287/opre.
[118]Nediak, M. and J. Eckstein (2001). ”Pivot, Cut and Dive: A Heuristic for 0-1 Mixed Integer Programming.” Rutcor research report, Rutgers University, USA, October 2001.
[119]Nemhauser, G.L., M.W.P. Savelsbergh, and G.C. Sigismondi. (1993). ”MINTO, a Mixed INTeger Optimizer.” Operations Research Letters 15, 47–58. · Zbl 0806.90095 · doi:10.1016/0167-6377(94)90013-2
[120]Nemhauser, G.L. and L.A. Wolsey. (1988). ”Integer and Combinatorial Optimization.” John Wiley and Sons.
[121]Niar, S. and A. Fréville. (1997). ”A Parallel Tabu Search Algorithm for the 0-1 Multidimensional Knapsack Problem.” International Parallel Processing Symposium’97, IEEE Computer Society Press, pp. 512–516, Suisse.
[122]Ohlssen, M., C. Peterson, and B. Soderberg. (1993). ”Neural Networks for Optimization Problems with Inequality Constraints: The Knapsack Problem.” Neural Computation 5, 331–339. · doi:10.1162/neco.1993.5.2.331
[123]Osorio, M.A., F. Glover, and P. Hammer (2002). ”Cutting and Surrogate Constraint Analysis for Improved Multidimensional Knapsack Solutions.” Annals of Operations Research 117, 71–93. · Zbl 1028.90042 · doi:10.1023/A:1021513321301
[124]Pirkul, H. (1987). ”A Heuristic Solution Procedure for the Multiconstraint Zero-One Knapsack Problem.” Naval Research Logistics 34, 161–172. · doi:10.1002/1520-6750(198704)34:2<161::AID-NAV3220340203>3.0.CO;2-A
[125]Pisinger, D. (1995). ”An Expanding-Core Algorithm for the Exact 0-1 Knapsack Problem.” European Journal of Operational Research 87, 175–187. · Zbl 0914.90199 · doi:10.1016/0377-2217(94)00013-3
[126]Pisinger, D. (2000). ”A Minimal Algorithm for the Bounded Knapsack Problem.” ORSA Journal on Computing 12, 75–84.
[127]Plateau, A., D. Tachat, and P. Tolla (2001). ”A Hybrid Search Combining Interior Point Methods and Metaheuristics for 0-1 Programming.” in Investigacion Operativa forth coming.
[128]Plateau, G. (1976). ”Réduction de la Taille Des Problèmes Linéaires en Variables 0-1.” Working paper, ANO-71, Université de Lille 1, France.
[129]Plateau, G. and M. Elkihel. (1985). ”A Hybrid Method for the 0-1 Knapsack Problem.” Methods of Operations Research 49, 277–293.
[130]Plateau, G. and C. Roucairol. (1989). ”A Supercomputer Algorithm for the 0-1 Multiknapsack Problem.” In R. Sharda, B. Golden, E. Wasil, O. Balei and W. Stewart, (eds.), Impacts of Recent Computer Advances on Operations Research, Operations Research Series pp. 144–157.
[131]Raidl G.R. (1998). ”An Improved Genetic Algorithm for the Multiconstraint Knapsack Problem.” in Proceedings of the 5thIEEE International Conference on Evolutionary Computation pp. 207–211.
[132]Reilly, C.H. (1991). ”Optimization Test Problems with Uniformly Distributed Coefficients.” Proceedings of the 1991 Winter Simulation Conference, (eds.), B.L. Nelson, W.D. Kelton and G.M. Clark, Institute of Electrical and Electronics Engineers, Phoenix, USA, 866–874.
[133]Rinnoy, Kan A.H.G., L. Stougie, and C. Vercellis. (1993). ”A Class of Generalized Greedy Algorithms for the Multi-Knapsack Problem.” Discrete applied Mathematics 42, 279–290. · Zbl 0785.90072 · doi:10.1016/0166-218X(93)90051-O
[134]Savelsbergh, M.W.P. (1994). ”Preprocessing and Probing Techniques for Mixed Integer Programming Problems.” ORSA Journal of Computing 6, 445–454.
[135]Schilling, K.E. (1990). ”The Growth of m-Constraint Random Knapsacks.” European Journal of Operational Research 46, 109–112. · Zbl 0708.90057 · doi:10.1016/0377-2217(90)90303-S
[136]Schilling, K.E. (1994). ”Random Knapsacks with Many Constraints.” Discrete Applied Mathematics 48, 163–174. · Zbl 0791.90038 · doi:10.1016/0166-218X(92)00125-6
[137]Senju, S. and Y. Toyada. (1968). ”An Approach to Linear Programming Problems with 0-1 Variables.” Management Sciences 15, 196–207. · doi:10.1287/mnsc.15.4.B196
[138]Shani, S. (1975). ”Approximate Algorithms for the 0-1 Knapsack Problem.” Journal of Association for Computing Machinery 22, 115–124.
[139]Shih, W. (1979). ”A Branch and Bound Method for the Multiconstraint Zero-One Knapsack Problem.” Journal of Operations Research Society 30, 369–378.
[140]Soyster, A.L., B. Lev and W. Slivka. (1978). ”Zero-One Programming with Many Variables and Few Constraints.” European Journal of Operational Research 2, 195–201. · Zbl 0381.90076 · doi:10.1016/0377-2217(78)90093-0
[141]Szkatula, K. (1994). ”The Growth of Multi-Constraint Random Knapsacks with Various Right-Hand Sides of the Constraints.” European Journal of Operational Research 73, 199–204. · Zbl 0806.90096 · doi:10.1016/0377-2217(94)90164-3
[142]Szkatula, K. (1997). ”The Growth of Multi-Constraint Random Knapsacks with Large Right-Hand Sides of the Constraints.” Operations Research Letters 21, 25–30. · Zbl 0885.90084 · doi:10.1016/S0167-6377(97)00024-2
[143]Szkatula, K. (2000). ”How Fast the Random Knapsacks with Many Constraints Grow.” Working paper presented at ECCO XIII conference, Capri, Italy.
[144]Thesen, A. (1975). ”A Recursive Branch and Bound Algorithm for the Multidimensional Knapsack Problem.” Naval Research Quaterly 22, 341–353. · Zbl 0307.90054 · doi:10.1002/nav.3800220210
[145]Thiel, J. and S. Voss. (1994). ”Some Experiences on Solving Multiconstraint Zero-One Knapsack Problems with Genetic Algorithms.” INFOR 32, 226–242.
[146]Toulouse, M., T.G. Crainic, and M. Gendreau. (1996). ”Communication Issues in Designing Cooperative Multithread Parallel Searches.” In I.H. Osman and J.P. Kelly (eds.), Meta-Heuristics : Theory and Applications Kluwer Academic Publishers, pp. 503–522.
[147][177] Toyoda, Y. (1975). ”A Simplified Algorithm for Obtaining Approximate Solutions to Zero-One Programming Problems.” Management Sciences 21, 1417–1427.
[148]Vasquez, M. and J.K. Hao (2001a). ”A Logic-Constrained Knapsack Formulation and a Tabu Algorithm for the Daily Photograph Scheduling of an Earth Observation Satellite.” Journal of Computational Optimization and Applications forth coming.
[149]Vasquez, M. and J.K. Hao (2001b). ”Une Approche Hybride Pour le Sac à dos Multidimensionnel en Variables 0-1.” in RAIRO Operations Research forthcoming.
[150]Voss, S. (1993). ”Tabu Search: Applications and Prospects.” In: D.Z. Du and P.M. Pardalos, (eds.), Network Optimization Problems pp. 333–353.
[151]Weingartner, H.M. and D.N. Ness. (1967). ”Method for the Solution for the Multidimensional 0-1 Knapsack Problem.” Operations Research 15, 83–103. · doi:10.1287/opre.15.1.83
[152]Wolsey, L.A. (1980). ”Heuristic Analysis, Linear Programming and Branch and Bound.” Mathematical Programming Study 13, 121–134.
[153]Yang, J. (1994). ”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.