Heuristics and reduction methods for multiple constraints 0-1 linear programming problems. (English) Zbl 0579.90066

Summary: This work extends the efficient results relative to the 0-1 knapsack problem to the multiple inequality constraints 0-1 linear programming problems. The two crucial phases for the solution of this type of problems are presented: (i) Two linear expected time complexity greedy algorithms are proposed for the determination of a lower bound on the optimal value by using a cascade of surrogate relaxations of the original problem whose sizes are decreasing step by step. A comparative study with the best known heuristic methods is reported; it concerned the accuracy of the approximate solutions and the practical computational times. (ii) This greedy algorithm is inserted in an efficient reduction framework. Variables and constraints are eliminated by the conjunction of tests applied to Lagrangean and surrogate relaxations of the original problem. A lot of computational results are summarized by considering test problems of the literature.


90C09 Boolean programming
65K05 Numerical mathematical programming methods
90C05 Linear programming
Full Text: DOI


[1] Balas, E.; Martin, C.M., Pivot and complement—a heuristic for 0-1 programming, Management science research, 26, 1, 86-96, (1980) · Zbl 0442.90060
[2] Camerini, P.M.; Fratta, L.; Maffioli, F., On improving relaxation methods by modified gradient techniques, Mathematical programming study, 3, 26-34, (1975) · Zbl 0357.90031
[3] Dyer, M.E., Calculating surrogate constraints, Mathematical programming, 19, 255-278, (1980) · Zbl 0464.90067
[4] Fayard, D.; Plateau, G., An algorithm for the solution of the 0-1 knapsack problem, Computing, 28, 269-287, (1982) · Zbl 0468.90045
[5] Fayard, D.; Plateau, G., Contribution à la résolution des programmes mathématiques en nombres entiers, Dissertation, (1979)
[6] Fleisher, J., Sigmap newsletter, 20, (February 1976)
[7] Fréville, A., Heuristiques et réduction pour LES programmes mathématiques en variables 0-1 à contraintes d’inégalite, Thèse 3ème cycle, (October 1983)
[8] Fréville, A.; Plateau, G., Méthodes heuristiques performances pour LES problèmes en variables 0-1 à plusieurs contraintes en inégalité, (December 1982), Publication ANO-91
[9] Glover, F., A multiphase dual algorithm for the 0-1 integer programming problem, Operations research, 13, 879-919, (1965) · Zbl 0163.41301
[10] Glover, F., Heuristics for integer programming using surrogate constraints, Decision sciences, 8, 156-166, (1977)
[11] Guignard, M., Methods heuristiques de résolution d’un système d’inégalités linéaires en variables entières ou bivalentes, ()
[12] Held, M.; Karp, R.M., The travelling-salesman problem and minimum spanning trees: part II, Mathematical programming, 1, 6-25, (1971) · Zbl 0232.90038
[13] Hillier, F.S., Efficient heuristics procedures for integer linear programming with an interior path, Operations research, 17, 600-636, (1969) · Zbl 0176.49902
[14] Kochenberger, G.A.; Mc. Karl, B.A.; Wyman, F.P., A heuristic for general integer programming, Decision sciences, 5, 1, 36-44, (1974)
[15] Loulou, R.; Michaelides, E., New greedy-like heuristics for the multidimensional 0-1 knapsack problem, Operations research, 27, 6, 1101-1114, (1979) · Zbl 0442.90058
[16] Petersen, C.C., Computational experience with variants of the balas algorithm applied to the selection of R and D projects, Management science, 13, 9, 736-750, (1967)
[17] Plateau, G., Reduction de la taille des problèmes linéaires en variables 0-1, (1976), Publication 71 du Laboratoire de Calcu de l’Université des Sciences et Techniques de Lille 1
[18] Pursglove, C.J.; Boffey, T.B., Heuristic improvement methods: how should starting solutions be chosen, Mathematical programming study, 13, 135-142, (1980) · Zbl 0442.90057
[19] Reiter, S.; Rice, D., Discrete optimizing solution procedures for linear and non-linear integer programming problems, Management science, 12, 829-850, (1966)
[20] Roth, H.R., An approach to solving linear discrete optimization problems, Journal of the association for computing machinery, 17, 300-313, (1970)
[21] Senju, S.; Toyoda, Y., An approach to linear programming with 0-1 variables, Management science, Vol 15, 4, 196-207, (1968)
[22] Shih, W., A branch and bound method for the multiconstraint 0-1 knapsack problem, Journal of the operational research society, 30, 4, 369-378, (1979) · Zbl 0411.90050
[23] Spielberg, K., Enumerative methods in integer programming, Anals of discrete mathematics, 5, 139-183, (1979) · Zbl 0407.90059
[24] Toyoda, Y., A simplified algorithm for obtaining approximate solutions to 0-1 programming problems, Management science, 21, 12, 1417-1427, (1975) · Zbl 0307.90056
[25] Weingartner, H.M.; Ness, D.N., Methods for the solution of the multidimensional 0-1 knapsack problem, Operations research, 15, 1, 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.