Abstract.
Combinatorial optimization problems are often too complex to be solved within reasonable time limits by exact methods, in spite of the theoretical guarantee that such methods will ultimately obtain an optimal solution. Instead, heuristic methods, which do not offer a convergence guarantee, but which have greater flexibility to take advantage of special properties of the search space, are commonly a preferred alternative. The standard procedure is to craft a heuristic method to suit the particular characteristics of the problem at hand, exploiting to the extent possible the structure available. Such tailored methods, however, typically have limited usefulness in other problems domains.
An alternative to this problem specific solution approach is a more general methodology that recasts a given problem into a common modeling format, permitting solutions to be derived by a common, rather than tailor-made, heuristic method. Because such general purpose heuristic approaches forego the opportunity to capitalize on domain-specific knowledge, they are characteristically unable to provide the effectiveness or efficiency of special purpose approaches. Indeed, they are typically regarded to have little value except for dealing with small or simple problems.
This paper reports on recent work that calls this commonly held view into question. We describe how a particular unified modeling framework, coupled with latest advances in heuristic search methods, makes it possible to solve problems from a wide range of important model classes.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
Author information
Authors and Affiliations
Corresponding author
Additional information
Correspondence to: Gary A. Kochenberger.
This research was supported in part by ONR grants N000140010598 and N000140310621.
Rights and permissions
About this article
Cite this article
Kochenberger, G.A., Glover, F., Alidaee, B. et al. A unified modeling and solution framework for combinatorial optimization problems. OR Spectrum 26, 237–250 (2004). https://doi.org/10.1007/s00291-003-0153-3
Issue Date:
DOI: https://doi.org/10.1007/s00291-003-0153-3