×

zbMATH — the first resource for mathematics

The knapsack problem: A survey. (English) Zbl 0305.90038

MSC:
90C10 Integer programming
90-02 Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming
49L99 Hamilton-Jacobi theories
65K05 Numerical mathematical programming methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] ”A Note on Reducing a System to a Single Equation,” Stichting Mathematisch Centrum, BN 1/70, Amsterdam (Dec. 1970).
[2] Balas, Comptes Rendus de l’Academic des Sciences, Paris 258 pp 3817– (1964)
[3] ”Duality in Discrete Programming,” Department of Operations Research Technical Report No. 67-5, Stanford University (July 1967).
[4] Balas, Management Science 16 pp 14– (1969)
[5] ”Duality in Discrete Programming III; Nonlinear Objective Function and Constraints,” Management Science Research Report No. 145, Carnegie-Mellon University (Feb. 1968). · Zbl 0157.50102
[6] Baumol, The Economic Journal 75 pp 317– (1965)
[7] Bellman, Operations Research 2 pp 275– (1954)
[8] Bellman, Nav. Res. Log. Quart. 3 pp 67– (1956)
[9] Dynamic Programming (Princeton University Press, 1957). · Zbl 0077.13605
[10] Bellman, Operations Research 5 pp 723– (1957)
[11] and , Applied Dynamic Programming (Princeton University Press, 1962). · Zbl 0106.34901 · doi:10.1515/9781400874651
[12] Benders, Numeristic Mathematik 4 pp 238– (1962)
[13] ”Transformation of Integer Programs to Knapsack Problems,” Yale Report No. 37 (Nov. 1970).
[14] ”Heuristic Solution Methods and Transformed Integer Linear Programming Problems,” Yale Report No. 43 (Mar. 1971).
[15] ”Equivalent Integer Programs,” Proceedings of the 5th International O. R. Conference, Y. R. Lawrence (ed.), (Travistock Publications, Ltd., London, 1970).
[16] ”Equivalent Integer Programs and Canonical Problems,” Yale Report No. 26 (Aug. 1969), 42 pages. Management Science (Jan. 1971).
[17] Brooks, Operations Research 14 pp 1149– (1966)
[18] Byrne, Journal of Financial and Quantitative Analysis 11 pp 339– (1967)
[19] and , ”The Application of an Approach to Zero-One Programming to Knapsack Problems,” presented at the joint ORSA/TIMS Meeting in San Francisco (1968).
[20] Cabot, Operations Research 18 pp 306– (1970)
[21] Cord, Management Science 10 pp 335– (1964)
[22] Dantzig, Operations Research 5 pp 266– (1957)
[23] Dreyfus, Operations Research 17 (1969)
[24] and , ”Improved Algorithms for Knapsack Problems,” Operations Research Center Report ORC 70–30, University of California-Berkeley (1970).
[25] and , ”On the Treatment of Stock Cutting Problems as Diophantine Programs,” Operations Research Report No. 61, North Carolina State University at Raleigh (May 11, 1970).
[26] Everett, Operations Research 11 pp 399– (1963)
[27] Fox, Operations Research 18 pp 253– (1970)
[28] and , ”A Survey of Integer Programming Emphasizing Computation and Relations Among Models,” Technical Report No. 156, Dept. of Operations Research, Cornell University, presented at the advanced seminar on Math. Programming, September 1972, Madison, Wisconsin.
[29] Gilmore, Operations Research 9 pp 849– (1961)
[30] Gilmore, Operations Research 11 pp 863– (1963)
[31] Gilmore, Operations Research 13 pp 94– (1965)
[32] Gilmore, Operations Research 14 pp 1045– (1966)
[33] and , ”Aggregating Diophantine Equations,” Management Science Report Series, Report No. 70-4 (Oct. 1970), Business Research Division, Graduate School of Business Administration, University of Colorado, Boulder, Colorado.
[34] Glover, Siam O. Control 7 pp 213– (1969)
[35] ”New Results for Reducing Integer Linear Programs to Knapsack Problems,” Management Science Research Report No. 72–7, Business Research Division, Graduate School of Business Administration, University of Colorado, Boulder, Colorado.
[36] and , ”Mathematical Programming Models and Methods for the Journal Selection Problem,” Management Science Report Series Report No. 71–10, Business Research Division, Graduate School of Business Administration, University of Colorado (Dec. 1971).
[37] Glover, Operations Research 16 pp 741– (1968)
[38] Gomory, Proceedings of the National Academy of Sciences 53 pp 260– (1965)
[39] Gomory, Proceedings of the National Academy of Sciences 53 pp 260– (1965)
[40] and , ”Some Continuous Function Related to Corner Polyhedra,” IBM Research Report RC3311 (Feb. 23, (1971).
[41] Greenberg, Journal of Math. Anal. and Applic. 26 pp 159– (1969)
[42] Greenberg, Management Science 16 pp 327– (1970)
[43] , and , ”On Not Searching for the Multipliers in Knapsack Problems,” can be obtained from R. E. D. Woolsey, Colorado School of Mines, Golden, Colorado.
[44] Guignard, IBM Journal of Research and Development 16 pp 424– (1972)
[45] and , ”Search Techniques with Adaptive Features for Certain Integer and Mixed Integer Programming Problems,” Proc. IFIPS Congress (1968).
[46] and , ”The State Enumeration Method for Mixed Zero-One Programming,” IBM Technical Report No. 320–3000, Philadelphia Scientific Center (Feb. 1971).
[47] Hammer, Stud. Cerc. Mat. 14 pp 359– (1963)
[48] and , Boolean Methods in Operations Research and Related Areas (Springer Verlag, New York, 1968). · Zbl 0155.28001 · doi:10.1007/978-3-642-85823-9
[49] Integer Programming and Network Flows Addison-Wesley, Inc., 1969). · Zbl 0197.45701
[50] Kaplan, Operations Research 14 (1966)
[51] and , ”Solving Integer Programming Problems by Aggregating Constraints,” presented at the Joint National Meeting of AIIE, ORSA, and TIMS, Atlantic City, N. J. (Nov. 1972).
[52] Kianfar, Operations Research 19 pp 1374– (1971)
[53] and , ”The Journal Selection Problem in a University Library System,” Research Memorandum Series, Technical Report, School of Industrial Engineering, Purdue University. · Zbl 0254.90060
[54] and , ”A Lagrangian Formulation of the Journal Selection Model,” Technical Report, School of Industrial Engineering, Purdue University (1971).
[55] Kolesar, Management Science 13 (1967)
[56] Lawler, Operations Research 14 pp 699– (1966)
[57] Land, Econometrica 28 pp 497– (1960)
[58] Lemke, Operations Research 15 pp 892– (1967)
[59] Little, Operations Research 11 pp 972– (1963)
[60] and , ”Three Problems in Capital Rationing,” Journal of Business (Oct. 1955).
[61] Mao, Management Science 15 pp 51– (1968)
[62] Mathews, Proceedings of the London Mathematical Society 28 pp 486– (1897)
[63] Nemhauser, Operations Research 16 pp 450– (1968)
[64] ”A Model of Capital Budgeting under Risk,” The Journal of Business (Apr. 1966).
[65] Nemhauser, Management Science 15 pp 494– (1969)
[66] ”Equivalent Knapsack Type Formulations of Bounded Integer Linear Programs,” Management Sciences Research Report No. 227, Carnegie-Mellon University (Sept. 1970).
[67] ”Capital Budgeting and Mixed Zero-One Integer Quadratic Programming,” Division of Systems and Computer Services, Technical Report, Medical College of Georgia at Augusta (Nov. 1972).
[68] Integer Programming, a forthcoming book, to be published by Addison-Wesley Publishing Company (1973).
[69] Shapiro, Operations Research 14 (1966)
[70] Shapiro, SIAM Journal of Appl. Math. 16 (1968)
[71] Shapiro, Operations Research 16 (1968)
[72] Shapiro, Operations Research 19 pp 68– (1971)
[73] ”A Multi-Compartment Knapsack Problem,” presented at the Joint National Meeting of AIIE, ORSA, and TIMS, Atlantic City, N. J. (Nov. 1972).
[74] Unger, AIIE Transactions 11 pp 28– (1970) · doi:10.1080/05695557008974727
[75] Principles of Operations Research (Prentice Hall, Inc., 1969).
[76] and , ”Methods for the Solution of 0-1 Knapsack Problems,” presented at the 29th Meeting of ORSA, Santa Monica, California (1966).
[77] Weingartner, Management Science 12 pp 485– (1968)
[78] Mathematical Programming and the Analysis of Capital Budgeting Problems (Prentice Hall, Inc., 1963).
[79] ”Quick and Dirty Methods in Time Shared Capital Budgeting,” Department of Combinatorics and Optimization Research Report CORR 72–8, University of Waterloo (Canada) (Aug. 1971)
[80] ”Accellerating Greenberg’s Method for the Computation of Knapsack Functions,” presented at the Joint National Meeting of AIIE, ORSA, and TIMS, Atlantic City, N. J. (Nov. 1972).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.