An efficient preprocessing procedure for the multidimensional 0-1 knapsack problem. (English) Zbl 0802.90077

Summary: The multidimensional 0-1 knapsack problem, defined as a knapsack with multiple resource constraints, is well known to be much more difficult than the single constraint version. This paper deals with the design of an efficient preprocessing procedure for large-scale instances. The algorithm provides sharp lower and upper bounds on the optimal value, and also a tighter equivalent representation by reducing the continuous feasible set and by eliminating constraints and variables. This scheme is shown to be very effective through a lot of computational experiments with test problems of the literature and large-scale randomly generated instances.


90C09 Boolean programming
Full Text: DOI


[1] Balas, E.; Martin, G. H., Pivot and complement - a heuristic for 0-1 programming, Management Sci., 26, 86-96 (1980) · Zbl 0442.90060
[2] Balas, E.; Zemel, E., An algorithm for large zero-one knapsack problems, Oper. Res., 28, 1130-1145 (1980) · Zbl 0449.90064
[3] Bellman, R., Dynamic Programming (1957), Princeton Univ. Press: Princeton Univ. Press Princeton · Zbl 0077.13605
[4] Bourgeois, P.; Plateau, G., BPK90: a revisited hybrid algorithm for the 0-1 knapsack problem, (Research Report LIPN no. 91-2 (1991), University of Paris-Nord)
[5] Bradley, G. H.; Hammer, P. L.; Wolsey, L., Coefficient reduction for inequalities in 0-1 variables, Math. Programming, 7, 263-282 (1974) · Zbl 0292.90038
[6] Camerini, P. M.; Fratta, L.; Maffioli, F., On improving relaxation methods by modified gradient techniques, Math. Programming Stud., 3, 26-34 (1975) · Zbl 0357.90031
[7] Chvatal, V., Hard knapsack problems, Oper. Res., 28, 1402-1411 (1980) · Zbl 0447.90063
[8] Crowder, H.; Johnson, E. L.; Padberg, M. W., Solving large scale zero-one linear programming problems, Oper. Res., 31, 803-834 (1983) · Zbl 0576.90065
[9] Dyer, M. F., Calculating surrogate constraints, Math. Programming, 19, 255-278 (1980) · Zbl 0464.90067
[10] Elkihel, M., Programmation dynamique et rotation de contraintes pour les problèmes d’optimisation entière, (Thèse 3ème cycle, 1 (1984), Université de Lille)
[11] Fayard, D.; Plateau, G., Reduction algorithms for single and multiple constraints 0-1 linear programming problems, Proceedings Congress Methods of Math. Programming Zakopane (1977)
[12] Fayard, D.; Plateau, G., An algorithm for the solution of the 0-1 knapsack problem, Computing, 28, 269-287 (1982) · Zbl 0468.90045
[13] Fleisher, J., Sigmap Newslett., 20 (1976)
[14] Fréville, A., Heuristiques et réduction pour les programmes mathématiques en variables 0-1, (Thèse 3ème cycle, 1 (1983), Université de Lille)
[15] Fréville, A., Contribution à l’optimisation en nombres entiers, (Habilitation à diriger des recherches (1991), Université de Paris-Nord)
[16] Fréville, A.; Lorena, L. A.N.; Plateau, G., Efficient subgradient algorithms for the 0-1 multiknapsack Lagrangean and surrogate duals, (Research Report L.I.P.N. no. 90-13 (1990), University of Paris-Nord)
[17] Fréville, A.; Plateau, G., Méthodes heuristiques performantes pour les problèmes en variables 0-1 à plusieurs contraintes en inégalité, (Research Report ANO-91 (1982), University of Lille)
[18] Fréville, A.; Plateau, G., Heuristics and reduction methods for multiple constraints 0-1 linear programming problems, European J. Oper. Res., 24, 206-215 (1986) · Zbl 0579.90066
[19] Fréville, A.; Plateau, G., Hard 0-1 multiknapsack test problems for size reduction methods, Invest. Oper., 1, 3, 251-270 (1990)
[20] Fréville, A.; Plateau, G., An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem, European J. Oper. Res., 68, 413-421 (1993) · Zbl 0782.90069
[21] Frieze, A. M.; Clarke, M. R., Approximation algorithms for the \(m\)-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European J. Oper. Res., 15, 100-109 (1984) · Zbl 0532.90075
[22] Fukushima, M., A descent algorithm for nonsmooth convex optimization, Math. Programming, 30, 163-175 (1984) · Zbl 0545.90082
[23] Garfinkel, R. S.; Nemhauser, G. L., Integer Programming (1972), Wiley: Wiley New York · Zbl 0271.90028
[24] Gavish, B.; Pirkul, H., Allocation of data bases and processors in a distributed computing system, (Akoka, J., Management of Distributed Data Processing (1982), North-Holland: North-Holland Amsterdam), 215-231
[25] Gavish, B.; Pirkul, H., Models for computer and file allocation in distributed computer networks, (Working paper (1983), The graduate school of management, University of Rochester: The graduate school of management, University of Rochester Rochester)
[26] Gavish, B.; Pirkul, H., Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Math. Programming, 31, 78-105 (1985) · Zbl 0571.90065
[27] Geoffrion, A. M., An improved implicit enumeration approach for integer programming, Oper. Res., 17, 437-454 (1969) · Zbl 0174.20801
[28] Geoffrion, A. M., Lagrangean relaxation for integer programming, Math. Programming Stud., 2, 82-114 (1974) · Zbl 0395.90056
[29] Gilmore, P. C.; Gomory, R. E., The theory and computation of knapsack functions, Oper. Res., 14, 1045-1074 (1966) · Zbl 0173.21502
[30] Glover, F., A multiphase-dual algorithm for the zero-one integer programming problem, Oper. Res., 13, 879-919 (1965) · Zbl 0163.41301
[31] Glover, F., Neglected heuristics in integer programming, Workshop on integer programming, Bonn (1975), Research Report
[32] Glover, F., Heuristics for integer programming using surrogate constraints, Decision Sci., 8, 156-166 (1977)
[33] Greenberg, H. J.; Pierskalla, W. P., Surrogate mathematical programming, Oper. Res., 18, 924-939 (1970) · Zbl 0232.90059
[34] Hammer, P. L.; Padberg, M. W.; Peled, U. N., Constraint pairing in integer programming, INFOR-Canadian J. Oper. Res. Inform. Process., 13, 68-81 (1975) · Zbl 0303.90041
[35] Held, M.; Wolfe, P.; Crowder, H. P., Validation of subgradient optimization, Math. Programming, 6, 62-88 (1974) · Zbl 0284.90057
[36] Hoffman, K. L.; Padberg, M. W., Techniques for improving the LP-representation of zero-one linear programming problems, Ecole polytechnique (1989), working paper no. 320
[37] Ibarra, O. H.; Kim, C. E., Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM, 22, 463-468 (1975) · Zbl 0345.90049
[38] Ingiargiola, G. P.; Korsh, J. F., A reduction algorithm for zero-one single knapsack problems, Management Sci., 20, 460-463 (1973) · Zbl 0304.90082
[39] Jaumard, B., Extraction et utilisation de relations booléennes pour la résolution des programmes linéaires en variables 0-1, (Thèse de doctorat (1986), E.N.S.E.T)
[40] Johnson, E. L.; Kostreva, M.; Suhl, U. H., Solving 0-1 integer programming problems arising from large scale planning models, Oper. Res., 33, 803-819 (1985) · Zbl 0569.90056
[41] Kiwiel, K. C., An aggregate subgradient method for nonsmooth convex minimization, Math. Programming, 27, 320-341 (1983) · Zbl 0525.90074
[42] Kiwiel, K. C., Methods of Descent for Nondifferentiable Optimization (1985), Springer: Springer Berlin · Zbl 0602.90122
[43] Korte, B.; Schnader, R., On the existence of fast approximation schemes, (Mangasarian, O. L.; Meyer, R. R.; Robinson, S. M., Nonlinear Programming, 4 (1980), Academic Press: Academic Press New York), 415-437
[44] Lawler, E. L., Fast approximation algorithms for knapsack problems, Math. Oper. Res., 4, 339-356 (1979) · Zbl 0425.90064
[45] Lemaréchal, C., Nonsmooth optimization and descent methods, (Research Report 778-4 (1979), International Institute for Applied Systems Analysis: International Institute for Applied Systems Analysis Laxenburg) · Zbl 0398.90088
[46] Lemaréchal, C., Extensions diverses des méthodes de gradient et applications, (Thèse doctorat es-Sciences, IX (1980), Université Paris)
[47] Magazine, M. J.; Chern, M. S., A note on approximation schemes for multidimensional knapsack problem, Math. Oper. Res., 9, 244-247 (1984) · Zbl 0589.90059
[48] Magazine, M. J.; Oguz, O., A fully polynomial approximation algorithm for the 0-1 knapsack problem, European J. Oper. Res., 8, 270-273 (1981) · Zbl 0473.90056
[49] Manne, A. S.; Markowitz, H. M., On the solution of discrete programming problems, Econometrica, 25, 84-110 (1957) · Zbl 0078.34005
[50] Martello, S.; Toth, P., A new algorithm for the 0-1 knapsack problem, Management Sci., 34, 633-644 (1988) · Zbl 0645.90054
[51] Martello, S.; Toth, P., Knapsack problems: algorithms and computer implementations, (Series in Discrete Mathematics and Optimization (1990), Wiley Interscience: Wiley Interscience New York) · Zbl 0452.90047
[52] Oguz, O.; Magazine, M. J.M., A polynomial time algorithm for the multidimensional 0-1 knapsack problem, (Working Paper (1980), University of Waterloo: University of Waterloo Waterloo, Ont)
[53] Patrizi, G.; Spera, C., Solving in polynomial time some hard combinatorial problems, Communication, International Conference on Operations Research, Vienna (1990)
[54] Petersen, C. C., Computational experience with variants of the Balas algorithm applied to the selection of R&D projects, Management Sci., 13, 736-750 (1967)
[55] Pirkul, H., A heuristic solution procedure for the multiconstraint zero-one knapsack problem, Naval Res. Logist., 34, 161-172 (1987) · Zbl 0609.90092
[56] Plateau, G., Réduction de la taille des problèmes linéaires en variables 0-1, (Research Report 71, 1 (1976), Université des Sciences et Techniques de Lille)
[57] Plateau, G.; Elkihel, M., A hybrid method for the 0-1 knapsack problem, Methods Oper. Res., 49, 227-233 (1985)
[58] Plateau, G.; Roucairol, C., A supercomputer algorithm for the 0-1 multiknapsack problem, (Sharda, R.; Golden, B.; Wasil, E.; Balei, O.; Stewart, W., Impacts of Recent Computer Advances on Operations Research. Impacts of Recent Computer Advances on Operations Research, Operations Research Series (1989)), 144-157
[59] Plateau, G.; Roucairol, C., Impact of parallel computation on the resolution of the multiknapsack problem, Research Report INRIA (1991)
[60] Ribeiro, C., Algorithmes de recherche des plus courts chemins avec contraintes. Etude théorique, implémentation et parallélisme, (thèse de doctorat, VI (1983), Université Paris)
[61] Sarin, S.; Karwan, M. H.; Rardin, R. L., Surrogate duality in a Branch-and-Bound procedure for integer programming, European J. Oper. Res., 33, 326-333 (1988) · Zbl 0638.90072
[62] Senju, S.; Toyoda, Y., An approach to linear programming problems with 0-1 variables, Management Sci., 15, 196-207 (1968)
[63] Shih, W., A branch and bound method for the multiconstraint zero-one knapsack problem, J. Oper. Res. Soc., 30, 369-378 (1979) · Zbl 0411.90050
[64] Shor, N. Z., Minimization Methods for Non-Differentiable Functions (1985), Springer: Springer Berlin · Zbl 0561.90058
[65] Soyster, A. L.; Lev, B.; Slivka, W., Zero-one programming with many variables and few constraints, European J. Oper. Res., 2, 195-201 (1978) · Zbl 0381.90076
[66] Toth, P., Dynamic programming algorithms for the zero-one knapsack problem, Computing, 25, 29-45 (1980) · Zbl 0431.90076
[67] Weingartner, H. M., Mathematical Programming and the Analysis of Capital Budgeting Problems (1963), Prentice Hall: Prentice Hall Englewood cliffs, NJ
[68] Weingartner, H. M.; Ness, D. N., Method for the solution of the multidimensional 0-1 knapsack problem, Oper. Res., 15, 83-103 (1967)
[69] Zanakis, S. T.; Evans, J. R.; Vazacopoulos, A. A., Heuristic methods and applications: A categorized survey, European J. Oper. Res., 43, 88-110 (1989) · Zbl 0681.90090
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.