The *Combinatorics *add-in
builds models for specific combinatorial problems. It
is to be used with the *Optimize* add-in
that provides most of the form building and search algorithms.
An advantage of the *Combinatorics* add-in is
that it constructs graphical maps for problems defined
on the Euclidean plane.
The *Combinatorics *menu* *is shown at
the left. At this time there are six model types. QAP,
stands for the *Quadratic Assignment Problem.* This
is a well studied optimization problem. There is a nonlinear-integer
programming model for the problem, but we use a combinatorial
representation that is much easier to implement with
Excel. We solve the problem with the search methods of
the *Optimize add-in*. The exhaustive enumeration
approach will yield the optimum for small problems, but
it will be necessary to use random search and improvement
methods for larger problems. These do not guarantee optimality.
* *The *Spanning Tree*, the *Shortest
Path Tree *and the* Traveling Salesman (TSP)* problems.are
also considered by the *Optimize* add-in through
the *Add Form* command, but here we provide
search methods that are much faster, allowing the solution
of larger problems in reasonable times. A map display
is provided for problems with arc lengths determined
by the Euclidean distance measure.
The *Sequence* problem is the problem of arranging
a set of jobs into a sequence that will pass through
one or more stages of production. The model includes
setup times. A graphic display of the schedule is provided
by a Gantt chart.
The *Routing Problem* is concerned with determining
a route for a vehicle that must visit a number of sites.
There is a travel time between every pair of sites as
well as a time spent at each site. The cost of a route
depends on the departure times from the sites as well
as the transportation costs between sites. The model
allows early and late due times. Violations of the due
times are penalized in the cost function. A map display
shows the routes graphically. Two options are provided.
The first routes a single vehicle and the second routes
multiple vehicles. The *Routing
add-in*has a more extensive model for the routing
problem.
The only limits to the size of problems that can be
formulated by this add-in are the worksheet limitations
of Excel, but for large problems time and memory requirements
may be excessive. |