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.
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.
|