The most general type of optimization problem and one that is applicable to most spreadsheet models is the combinatorial optimization problem. Many spreadsheet models contain variables and compute measures of effectiveness. The spreadsheet user often changes the variables in an unstructured way to look for the solution that obtains the greatest or least of the measure. In the words of OR, the analyst is searching for the solution that optimizes an objective function, the measure of effectiveness. Combinatorial optimization provides tools for automating the search for good solutions and can be of great value for spreadsheet applications.

A definition of combinatorics comes from Mathworld:

Combinatorics is the branch of mathematics studying the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.

Combinatorial optimization does not only enumerate sets, but has the goal of finding the member of the set that optimizes an objective function. For OR, combinatorial optimization has come to mean methods for finding or searching for the optimum of problems with discrete solution spaces. This is in contrast to problems with continuous solution spaces, such as nonlinear programs. Continuous solution spaces allow the use of differentiation to aid in finding optimum solutions. For combinatorial optimization differentiation is not commonly used.

The next page shows a general model for the combinatorial optimization problem (COP). On the following pages we present models for several COP's that have been considered by OR researchers and practitioners including the minimal spanning tree, shortest path tree, traveling salesman, quadratic assignment, job sequencing and vehicle routing problems. Mathematical programs for integer, network flow, transportation and assignment optimization are COP's. The linear program is also a COP when it is recognized that the optimum can be discovered by searching only extreme point solutions. The nonlinear program is a COP considering the problem of finding the global optimum among multiple local optima. Every spreadsheet model with a single objective and bounded, discrete decisions can be viewed as a COP.

Models are constructed and solution methods are implemented in the Optimize and Combinatorics add-ins. The Optimize add-in is the most general and provides solutions for several classes of problems. The Combinatorics add-in takes advantage of features of special case problems to provide faster solutions. Several application add-ins on this site, such as Facility Layout, use COP solution methods to search for the best solution.

The COP is the most general of the optimization problems considered by OR and has been the subject of a great deal of research. A general reference is Combinatorial Optimization by C. H. Papadimitriou and K. Steiglitz, Prentice Hall, 1982. Network Flows by R. Ahuja, T. Magnanti, and J. Orlin, Prentice Hall, 1993, describes algorithms for many combinatorial problems related to networks. Integer and Combinatorial Optimization by G. Nemhauser and L. Wolsey, Wiley, 1998 describes methods for solving integer programming and other combinatorial problems.