| |
One name for the kind
of optimization provided by Optimize is global
optimization since we make no assumptions regarding the
mathematical form of the models, and the goal is to find the
best of all solutions, the global optimum. Another name for
the subject of this add-in is combinatorial optimization.
Discrete values for the decision variables are considered and
the add-in searches the finite, but possibly very large, set
of possible values to find the one with the best objective
value. The add-in provides automated procedures for searching
over the values of the variables to find a solution that maximizes
or minimizes an objective function subject to constraints.
The methods of this add-in are very general. The procedures
evaluate a particular solution by placing the solution into
worksheet cells. The formulas and functions on the worksheet
compute the objective function and constraints. The add-in
may call subroutines from other add-ins during the evaluation
process. There are no restrictions on the formulas and functions
except they must result in numeric values. No restrictions
such as linearity or continuity are imposed. Although we can
handle a large variety of problems in this fashion, the algorithms
do not take advantage of the peculiarities of specific problems
types. There are many books and journal papers that address
specific combinatorial problems. Some problems, like the minimal
spanning tree problem, are easy in the sense that they can
be solved with computational effort that depends algebraically
on the size of the problem. Other problems, like the traveling
salesman problem, are very difficult in that the computational
effort to find an optimum grows exponentially with the size
of the problem. We do not look for special cases of problem
types or data structures. In some sense all combinatorial problems
are handled in the same way. This makes for generality, but
results in poor efficiency for solving certain well known problems.
It happens that the greedy algorithms and improvement algorithms
implemented here do result in efficient algorithms for some
problems. Those interested in the most efficient algorithms
for hard problems should look at the extensive literature that
addresses many problem types.
One problem feature that is recognized by this add-in is the
solution type. We divide problems by their solution structure.
Structures recognized are the range, traveling
salesman, permutation, spanning tree, path
tree, and flow tree structures. We gain some
efficiency by only generating solutions that satisfy the problem
structure and many problems can be placed into one of these
structures. The list is not complete, however, and other structures
may be added in the future.
The search procedures used for finding solutions include exhaustive
enumeration, Fibonacci enumeration, greedy algorithms, random
generation and improvement heuristics. At this time we have
not included heuristics such as Tabu search, simulated annealing,
and genetic algorithms. Again, these may be added in the future.
The Optimize add-in has the name Optimize in
the add-in list and is contained in the optimize.xla add-in
file. |
