An exact search for the solution of the surrogate dual of the 0-1 bidimensional knapsack problem. (English) Zbl 0782.90069

Summary: The surrogate dual of the \(0-1\) bidimensional knapsack problem is exactly solved by an algorithm with a modified dichotomic search. The primal (or dual) optimality is proved with a finite number of iterations. A lot of numerical experiments show the efficiency of our method: its reduced number of iterations is revealed to be independent of the size of the instances.


90C09 Boolean programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming
Full Text: DOI


[1] Bourgeois, P.; Plateau, G., BPK90: A revisited hybrid algorithm for the 0-1 knapsack problem, Research report LIPN 91.2 (1991)
[2] Dyer, M. F., Calculating surrogate contstraints, Mathematical Programming, 19, 255-278 (1980) · Zbl 0464.90067
[3] Fayard, D.; Plateau, G., An algorithm for the solution of the 0-1 knapsack problem, Computing, 28, 269-287 (1982) · Zbl 0468.90045
[4] Fischer, M. L.; Shapiro, J. F., Constructive duality in integer programming, SIAM Journal on Applied Mathematics, 27/1, 31-52 (1974) · Zbl 0299.90010
[5] Fréville, A.; Plateau, G., Sac à dos multidimensionel en variables 0-1: Encadrement de la somme des variables à l’optimum, (Research Report LIPN 91-1 (1991), University of Paris-Nord: University of Paris-Nord France), to appear in RAIRO · Zbl 0777.90032
[6] Fréville, A.; Plateau, G., FPBK92: An implicit enumeration code for the solution of the 0-1 bidimensional knapsack problem based on surrogate duality, (Graphs and Optimization Colloquium (1992), Grimentz: Grimentz Switzerland)
[7] Garfinkel, R. S.; Nemhauser, G. L., Integer programming (1972), Wiley: Wiley New York · Zbl 0271.90028
[8] Gavish, B.; Pirkul, H., Efficient algorithms for solving multiconstraint zero-one knapsack problems to optimality, Mathematical Programming, 31, 78-105 (1985) · Zbl 0571.90065
[9] Geoffrion, A. M., Lagrangean relaxation for integer programming, Mathematical Programming Study, 2, 82-114 (1974) · Zbl 0395.90056
[10] Glover, F., A multiphase dual algorithm for the zero-one integer programming problem, Operations Research, 18, 924-939 (1965)
[11] Greenberg, H. J.; Pierskalla, W. P., Surrogate mathematical programming, Operations Research, 18, 924-939 (1970) · Zbl 0232.90059
[12] Guignard, M.; Kim, S., Lagrangean decomposition: A model yielding stronger Lagrangean bounds, Mathematical Programming, 39, 215-228 (1987) · Zbl 0638.90074
[13] Guignard, M.; Kim, S., Lagrangean decomposition for integer programming: Theory and applications, RAIRO Recherche Opérationelle, 21, 307-323 (1987) · Zbl 0638.90075
[14] Martello, S.; Toth, P., Knapsack Problems: Algorithms and Computer Implementations (1990), Wiley: Wiley New York · Zbl 0708.68002
[15] Plateau, G.; Elkihel, M., A hybrid method for the 0-1 knapsack problem, Methods of Operations Research, 49, 227-233 (1985)
[16] Weingartner, H. M.; Ness, D. N., Method for the solution of the multidimensional 0-1 knapsack problem, Operations Research, 15/11, 83-103 (1967)
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.