An exact algorithm for the 0-1 collapsing knapsack problem. (English) Zbl 0806.90089

Summary: An exact algorithm is proposed for the 0-1 collapsing knapsack problem as defined by M. Guignard and M. Posner [Math. Program. 15, 155- 161 (1978; Zbl 0393.90060)]. Bounding of the number of variables equal to 1 in an optimal solution is extensively used, as well as inner- and outer-linearization of the nonlinear right-hand side of the constraint. This allows generally a drastic reduction of the feasible domain. An implicit enumeration scheme solves the problem reduced by the preprocessing phase. Computational experiments are reported on.


90C09 Boolean programming


Zbl 0393.90060
Full Text: DOI


[1] Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Oper. Res., 28, 1130-1154 (1980) · Zbl 0449.90064
[2] Fayard, D.; Plateau, G., Reduction algorithm for single and multiple constraints 0-1 linear programming problems, Conference Methods of Mathematical Programming, Zakopane (Poland) (1977)
[3] Fayard, D.; Plateau, G., Un problème du knapsack non linéaire en variables 0-1, Bulletin de la Direction des Etudes et Recherches E.D.F. C, 2, 51-79 (1979)
[4] Fayard, D.; Plateau, G., Un algorithme de résolution du problème du knapsack “baudruche” en variables 0-1, Actes du colloque Les Mathématiques de l’Informatique, 397-406 (1982), Paris · Zbl 0514.90061
[5] Fayard, D.; Plateau, G., An algorithm for the solution of the 0-1 knapsack problem, Computing, 28, 269-287 (1982) · Zbl 0468.90045
[6] Glover, F., A multiphase-dual algorithm for the zero-one integer programming problem, Oper. Res., 13, 879-919 (1965) · Zbl 0163.41301
[7] Lawler, E. L., Fast approximation algorithms for knapsack problems, Math. Oper. Res., 4, 339-356 (1979) · Zbl 0425.90064
[8] Martello, S.; Toth, P., A new algorithm for the 0-1 knapsack problem, Management. Sci., 34, 633-644 (1988) · Zbl 0645.90054
[9] Posner, M.; Guignard, M., The collapsing 0-1 knapsack problem, Math. Programming, 15, 155-161 (1978) · Zbl 0393.90060
[10] Posner, M.; Guignard, M., The integer collapsing knapsack problem, (Working Paper 80/101 (1980), University of Wisconsin-Milwaukee: University of Wisconsin-Milwaukee WI) · Zbl 0393.90060
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.