Combinatorial Optimization Problems

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.