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
addins. The Optimize addin is the most general and
provides solutions for several classes of problems. The Combinatorics
addin takes advantage of features of special case problems
to provide faster solutions. Several application addins 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.
