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 provide a theoretical framework and associated explicit proposals for generating general purpose IP heuristics. Our development, 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.
Similar content being viewed by others
References
Balas, E. (1972). “Ranking the Facets of the Octahedron.” Discrete Mathematics 2(2), 1–15.
Balas, E., F. Glover, and D. Sommer. (1971). “An Intersection Cut for the Dual of the Unit Hypercube.” Operations Research 19, 40–44.
Balas, E., S. Ceria, M. Dawande, F. Margot, and G. Pataki. (1996). “OCTANE: A New Heuristic for Pure 0-1 Programs.” Working paper, Carnegie Mellon University.
Dantzig, G.B. (1963). Linear Programming and Extensions. Princeton University Press.
Glover, F. (1972). “Cut Search Methods in Integer Programming.” Mathematical Programming. 3(1), 86–100.
Glover, F. (1977). “Heuristics for Integer Programming Using Surrogate Constraints.” Decision Sciences 8, 156–166.
Glover, F. (1995). “Scatter Search and Star-Paths: Beyond and Genetic Metaphor.” OR Spectrum 17, 125–137.
Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers (forthcoming).
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 II. Journal of Heuristics 3, 161–179 (1997). https://doi.org/10.1023/A:1009631530787
Issue Date:
DOI: https://doi.org/10.1023/A:1009631530787