×

zbMATH — the first resource for mathematics

General purpose heuristics for integer programming. I. (English) Zbl 0887.90123
Summary: 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.

MSC:
90C10 Integer programming
Software:
Tabu search
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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. · Zbl 0798.90105
[2] Balas, E. (1971). ?The Intersection Cut?A New Cutting Plane for Integer Programming,? Operations Research 19, 19-39. · Zbl 0219.90035 · doi:10.1287/opre.19.1.19
[3] Beasley, J.E. (1996). Advances in Linear and Integer Programming. Oxford Science Publications. · Zbl 0869.00020
[4] Glover, F. (1964). ?A Bound Escalation Method for the Solution of Integer Linear Programs,? Cahiers de Recherche Opérationelle 6(3), 131-168. · Zbl 0207.50502
[5] Glover, F. (1972). ?Cut Search Methods in Integer Programming,? Mathematical Programming 3(1), 86-100. · Zbl 0247.90042 · doi:10.1007/BF01584977
[6] 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). · Zbl 0877.90058
[7] Glover, F. and M. Laguna. (1997). Tabu Search. Kluwer Academic Publishers (forthcoming). · Zbl 0930.90083
[8] 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. · Zbl 0132.13702 · doi:10.1073/pnas.53.2.260
[9] Gomory, R.E. (1967). ?Faces of an Integer Polyhedron.? Proceedings of the National Academy of Science, vol. 57, pp. 16-18. · Zbl 0208.21606 · doi:10.1073/pnas.57.1.16
[10] Gomory, R.E. (1996). ?An Algorithm for the Mixed Integer Problems,? Research Memorandum RM-2597, Rand Corporation, Santa Monica.
[11] Gomory, R.E. and E.L.Johnson. (1972). ?Some Continuous Functions Related to Corner Polyhedra,? Mathematical Programming 3, 23-85. · Zbl 0246.90029 · doi:10.1007/BF01584976
[12] 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. · Zbl 0937.90507
[13] Nemhauser, G.L. and L.A.Wolsey. (1988). Integer and Combinatorial Optimization. New York: John Wiley & Sons. · Zbl 0652.90067
[14] Parker, G. and R.Rardin. (1988). Discrete Optimization. New York: Academic Press. · Zbl 0652.90068
[15] Sharda, R. (1995). ?Linear Programming Solver Software for Personal Computers: 1995 report,? OR/MS Today 22(5), 49-51.
[16] 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. · Zbl 0436.90079 · doi:10.1007/BF01581626
[17] Tuy, H. (1964). ?Concave Programming Under Linear Constraints,? Soviet Mathematics, pp. 1437-1440. · Zbl 0132.40103
[18] Young, R.D. (1971). ?Hypercylindrically Deduced Cuts in Zero-One Integer Programming,? Operations Research 19, 1393-1405. · Zbl 0232.90041 · doi:10.1287/opre.19.6.1393
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.