zbMATH — the first resource for mathematics

General purpose heuristics for integer programming. II. (English) Zbl 0898.90094
Summary: [Part I, cf. ibid. 2, 343-358 (1997; Zbl 0887.90123).]
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 acknowledgement 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.

90C10 Integer programming
Full Text: DOI