×

zbMATH — the first resource for mathematics

Exact methods for the knapsack problem and its generalizations. (English) Zbl 0603.90097
A unified approach and a summary of the most important results concerned with exact methods for solving the (binary) knapsack problem and its generalizations are given. We stress the importance of dual methods for solving linear programming relaxations of the considered problems. Two ways of generalization of the knapsack problem are described. If the special ordered sets are added, then the multiple-choice knapsack problem is obtained. If the constraints have the nested structure, then we get the nested knapsack problem. Also the multiple-choice nested knapsack problem is discussed.

MSC:
90C10 Integer programming
90C05 Linear programming
65K05 Numerical mathematical programming methods
Software:
Algorithm 37
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aho, A.V.; Hopcroft, J.E.; Ullman, J.D., The design and analysis of computer algorithms, (1974), Addison-Wesley Reading, MA · Zbl 0286.68029
[2] Armstrong, R.D.; Sinha, P.; Zoltners, A.A., The multiple-choice nested knapsack model, Management science, 28, 34-43, (1982) · Zbl 0493.90061
[3] Armstrong, R.D.; Kung, D.S.; Sinha, P.; Zoltners, A.A., A computational study of a multiple-choice knapsack algorithm, ACM transactions on mathematical software, 2, 184-198, (1983) · Zbl 0512.68029
[4] Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Operations research, 28, 1130-1154, (1980) · Zbl 0449.90064
[5] Brucker, P., An O(n) algorithm for LP-knapsacks with a fixed number of GUB constraints, Zeitschrift fur operations research, 28, 29-40, (1984) · Zbl 0529.90072
[6] Chvatal, V., Hard knapsack problem, Operations research, 28, 1402-1411, (1980) · Zbl 0447.90063
[7] Crowder, H.; Hohnson, E.L.; Padberg, M.W., Solving large-scale zero-one linear programming problems, Operations research, 31, 801-834, (1983)
[8] Dantzig, G.B., Linear programming and extensions, (1963), Princeton University Press Princeton, NJ · Zbl 0108.33103
[9] Dembo, R.S.; Hammer, P.L., A reduction algorithm for knapsack problems, Methods of operations research, 36, 49-60, (1980) · Zbl 0439.90060
[10] Dudziński, K., A dynamic programming approach for solving the multiple choice knapsack problem, Bulletin of the Polish Academy of science, technical science, 32, 325-332, (1984) · Zbl 0555.90075
[11] Dudziński, K., Solving large multiple-choice knapsack problems, Report MPD-6-49/84 systems research institute, (1984), Warsaw, Poland · Zbl 0557.90070
[12] Dudziński, K., The multiple-choice multiperiod knapsack problem, Report MPD0-9-49/84 systems research institute, (1984), Warsaw, Poland · Zbl 0557.90070
[13] Dudziński, K.; Walukiewicz, S., A fast algorithm for solving linear multiple-choice knapsack problem, Operations research letters, 3, 205-209, (1984) · Zbl 0549.90069
[14] Dudziński, K.; Walukiewicz, S., On the multiperiod binary knapsack problem, Methods of operations research, 49, 223-232, (1985) · Zbl 0564.90036
[15] Dudziński, K.; Walukiewicz, S., A knapsack approach to sequencing jobs with deadlines, () · Zbl 0557.90070
[16] Dudziński, K.; Walukiewicz, S., Upper bounds for the 0-1 knapsack problem, (), (submitted to Mathematical Programming) · Zbl 0557.90070
[17] Dyer, M.E., An O(n) algorithm for the multiple-choice knapsack linear program, Mathematical programming, 29, 57-63, (1984) · Zbl 0532.90068
[18] Faaland, B.H., The multiperiod knapsack problem, Operations research, 29, 612-616, (1981) · Zbl 0455.90059
[19] Fayard, D.; Plateau, G., An algorithm for the solution of the 0-1 knapsack problem, Computing, 28, 269-287, (1982) · Zbl 0468.90045
[20] Fisher, M.L., Worst-case analysis of heuristic algorithm, Management science, 26, 1-17, (1980) · Zbl 0448.90041
[21] Frederickson, G.N.; Johnson, D.B., The complexity of selection and ranking in X + Y and matrices with sorted columns, Journal of computer and system sciences, 24, 197-208, (1982) · Zbl 0478.68062
[22] Garey, M.R.; Johnson, D.S., ()
[23] Geoffrion, A.M.; Marsten, R.E., Integer programming algorithms: A framework an state-of-the-art-survey, Management science, 18, 465-491, (1972) · Zbl 0238.90043
[24] Gilmore, P.C.; Gomory, R.E., The theory of computation of knapsack functions, Operations research, 14, 1045-1074, (1966) · Zbl 0173.21502
[25] Ibaraki, T.; Hasegawa, T.; Teranaka, K.; Iwase, J., The multiple choice knapsack problem, Journal of the operations research society of Japan, 21, 59-94, (1978) · Zbl 0379.90076
[26] Ingargiola, G.P.; Korsh, J.F., Reduction algorithm for zero-one single knapsack problems, Management science, 20, 460-463, (1973) · Zbl 0304.90082
[27] Johnson, E.L.; Padberg, M.W., A note on the knapsack problem with special ordered sets, Operations research letters, 1, 18-22, (1981) · Zbl 0493.90062
[28] Martello, S.; Toth, P., An upper bound for the zero-one knapsack problem and a branch and bound algorithm, European journal of operational research, 1, 169-173, (1978) · Zbl 0374.90050
[29] Martello, S.; Toth, S., The 0-1 knapsack problem, () · Zbl 0389.90070
[30] Morin, T.L.; Marsten, R.E., Branch and bound strategies for dynamic programming, Operations research, 24, 611-627, (1976) · Zbl 0352.90075
[31] Muller-Merbach, H., Improved upper bound for the zero-one knapsack problem. A note on the paper by martello and toth, European journal of operational research, 2, 212-213, (1979) · Zbl 0379.90077
[32] Nauss, R.M., An efficient algorithm for the 0-1 knapsack problem, Management science, 23, 27-31, (1976) · Zbl 0337.90042
[33] Nauss, R.M., The 0-1 knapsack problem with multiple choice constraints, European journal of operational research, 2, 125-131, (1979) · Zbl 0383.90078
[34] Nikitin, A.I.; Nuriev, U.G., On the method for solving the knapsack problem, Kibernetika, 2, 108-109, (1983), (in Russian) · Zbl 0536.90062
[35] Padberg, M.W., Covering, packing and knapsack problems, Annals of discrete mathematics, 4, 265-287, (1979) · Zbl 0407.90056
[36] Rockafellar, R.T., Convex analysis, (1970), Princeton University Press Princeton, NJ · Zbl 0229.90020
[37] Sahni, S., General techniques for combinatorial approximation, Operations research, 25, 920-936, (1977) · Zbl 0386.90048
[38] Sinha, P.; Zoltners, A.A., The multiple choice knapsack problem, Operations research, 27, 503-515, (1979) · Zbl 0406.90052
[39] Toth, P., Dynamic programming algorithms for the zero-one knapsack problem, Computing, 25, 29-45, (1980) · Zbl 0431.90076
[40] Walukiewicz, S., Almost linear integer programming problems, Prace IOK z., 23, (1975), (in Polish)
[41] Zemel, E., The linear multiple choice knapsack problem, Operations research, 28, 1412-1423, (1980) · Zbl 0447.90064
[42] Zemel, E., An O(n) algorithm for the linear multiple-choice knapsack problem and related problems, Information processing letters, 18, 132-138, (1984)
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.