Abstract
In spite of the many special purpose heuristics for specific classes of integer programming (IP) problems, there are few developments that focus on general purpose integer programming heuristics. This stems partly from the perception that general purpose methods are likely to be less effective than specialized procedures for specific problems, and partly from the perception that there is no unifying theoretical basis for creating general purpose heuristics. Still, there is a general acknowledgment that methods which are not limited to solving IP problems on a “class by class” basis, but which apply to a broader range of problems, have significant value. We show that certain ideas proposed in the 1970s, which are often overlooked, can be reformulated and linked with more recent developments to give a useful theoretical framework for generating general purpose IP heuristics. This framework, which has the appeal of being highly visual, makes use of cutting plane derivations that also give a natural basis for marrying heuristics with exact branch and cut methods for integer programming problems.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Aboudi, R. and K.Jörnsten. (1994). “Tabu Search for General Zero-One Integer Programs Using the Pivot and Complement Heuristic,” ORSA Journal on Computing 6(1), 82–93.
Balas, E. (1971). “The Intersection Cut—A New Cutting Plane for Integer Programming,” Operations Research 19, 19–39.
Beasley, J.E. (1996). Advances in Linear and Integer Programming. Oxford Science Publications.
Glover, F. (1964). “A Bound Escalation Method for the Solution of Integer Linear Programs,” Cahiers de Recherche Opérationelle 6(3), 131–168.
Glover, F. (1972). “Cut Search Methods in Integer Programming,” Mathematical Programming 3(1), 86–100.
Glover, F. and A. Løkketangen. (1996). “Solving Zero-One Mixed Integer Programming Problems Using Tabu Search,” in European Journal of Operational Research (to appear).
Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers (forthcoming).
Gomory, R.E. (1965). “On the Relation between Integer and Non-Integer Solutions to Linear Programs.” Proceedings of the National Academy of Science, vol. 53, pp. 260–265.
Gomory, R.E. (1967). “Faces of an Integer Polyhedron.” Proceedings of the National Academy of Science, vol. 57, pp. 16–18.
Gomory, R.E. (1996). “An Algorithm for the Mixed Integer Problems,” Research Memorandum RM-2597, Rand Corporation, Santa Monica.
Gomory, R.E. and E.L.Johnson. (1972). “Some Continuous Functions Related to Corner Polyhedra,” Mathematical Programming 3, 23–85.
Magee, T.M. and F.Glover. (1996). “Integer Programming.” In M.Avriel and B.Golany (eds.), Mathematical Programming for Industrial Engineers. New York: Marcel Dekker, Inc., pp. 123–270.
Nemhauser, G.L. and L.A.Wolsey. (1988). Integer and Combinatorial Optimization. New York: John Wiley & Sons.
Parker, G. and R.Rardin. (1988). Discrete Optimization. New York: Academic Press.
Sharda, R. (1995). “Linear Programming Solver Software for Personal Computers: 1995 report,” OR/MS Today 22(5), 49–51.
Sherali, H.D. and C.M.Shetty. (1980). “A Finitely Convergent Algorithm for Bilinear Programming Problems Using Polar Cuts and Disjunctive Face Cuts,” Mathematical Programming 19, 14–31.
Tuy, H. (1964). “Concave Programming Under Linear Constraints,” Soviet Mathematics, pp. 1437–1440.
Young, R.D. (1971). “Hypercylindrically Deduced Cuts in Zero-One Integer Programming,” Operations Research 19, 1393–1405.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Glover, F., Laguna, M. General purpose heuristics for integer programming—Part I. J Heuristics 2, 343–358 (1997). https://doi.org/10.1007/BF00132504
Issue date:
DOI: https://doi.org/10.1007/BF00132504
