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-inhas a more extensive model for the routing
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.