We use the general
model given below for the combinatorial optimization problem.
The problem can be expressed as either maximum or minimum. This
model structure is implemented in the Optimize add-in.
We illustrate the model below using linear-integer
programming (IP). We also refer to other combinatorial
problems that are described in detail on the following pages.
Combinatorial Optimization Problem: COP
|
This model places very few limitations on the the model components.
Since the principal methods of solution involve enumeration
there is no need to restrict the functions involved. Special
cases of the model will add restrictions, and the solution methods
for the special cases depend on these restrictions.
A solution x is a vector of integers. For
a spreadsheet application, the individual solution components
may be cells anywhere on the worksheet, usually arranged for
convenience related to the application. A solution is a member
of the solution space X. The discrete solution
space X is defined using mathematical relations
that members of the set must satisfy. The number of solutions
in the solution space is finite. An example is below where the
solution vectors are restricted to integers between lower and
upper limits. This is the restriction for IP.
The definition of X is very important for
our models, because it will be different for different classes
of problems. For a permutation problem, X is
the set of all permutations of n integers. For the
traveling salesman problem it is the set of all tours through
n cities. The definition of X might
also include combinatorial constraints that limit individual
components of x or combinations of components.
The delineation of the set X determines the
number of solutions that must be enumerated or partially enumerated
in the search for the optimum.
The objective function, f(x), is
a single real number and the measure by which alternative solutions
are compared.
This function will be evaluated in a single worksheet cell,
but it may be the result of computations performed in many cells
and even on several worksheets in a workbook. For the general
model, no specific form is specified for f(x),
but it is important that its value be unique for a given x.
The function must also be computable for all x
in the solution space. By computable we mean that it contains
no errors such as dividing by zero, taking the square root of
a negative number, or using circular cell references. These
errors are easy to make on a spreadsheet.
For the IP, the objective function is a linear function.
G is the set of solutions that are feasible.
Many applications have several separate logical relations that
must all be satisfied (logically TRUE) if the solution is feasible.
Logical relations are easy to express on a spreadsheet. The
expressions involved in G must be computable
for all solutions in X.
Considering again an IP, the components of G
come from linear constraints. The following shows the development
for "less than or equal to" constraints. A similar
development follows for "equality" and "greater
than or equal to" constraints.
The optimum solution is the feasible solution that minimizes
(or maximizes) the objective over all feasible solutions in
the solution space.
Although X and G both limit
the set over which the optimum is to be found, in our solution
methods X is the most important. We will search
the solutions delimited by X, but only consider
for optimality those solutions that are feasible, members of
G. The process of generating solutions from
the set X is embodied in the solution algorithm
for each special type of problem, so only members of X
are generated. |