   Optimize    IP Tour
 Download  Optimize   Many Excel models depend on a few design variables. Formulas on a worksheet compute one or more evaluation measures for specific values of the variables and the modeler experiments with the design variables in a "what-if" fashion. One goal of the modeler might be to find the optimum values of the design variables. This add-in helps in the optimization process. The Optimize add-in addresses combinatorial optimization problems in a generic fashion. The Combinatorics add-in addresses specific problem types and in some cases, such as the minimal spanning tree, shortest path tree, and traveling salesman problem provide more efficient algorithms. That add-in also addresses problems with specific data structures, such as the quadratic assignment, job sequencing and vehicle routing problems. We have also added optimization options to the Queue add-in and Layout add-in that call this Optimize add-in to provide the search processes. The Sequence Optimize add-in uses a variant of the methods of this Optimize add-in specialized for sequencing adapted to the vehicle routing problem.

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.

The commands shown under the Optimize menu item are discussed on the following pages.

• Add Form: This command is used to place a combinatorial form on a worksheet that contains the variables to be optimized. A form must be present before initiating a search process.
• Math Program: The Math Programming add-in provides a convenient representation for optimization problems with constraints. This command creates a form on a math programming page that represents the combinatorial part of the model. Forms can be created for mixed-integer programming, network flow programming and transportation models. An option of this menu item is to provide multiple starts for nonlinear programming models solved with the Excel Solver.
• Search: This command selects and initiates a search process. Several kinds of search are provided that promise varying degrees of solution quality and effort. Exhaustive enumeration yields the optimum and requires the greatest computational effort. Fibonacci enumeration requires less effort, but does not guarantee optimality. Random search randomly generates a fixed number of solutions and shows the best of the feasible solutions generated. The greedy method finds a solution quickly. An improvement method attempts to improve a solution with changes of the decision variables within a prescribed neighborhood.  Operations Research Models and Methods
Internet
by Paul A. Jensen
Copyright 2004 - All rights reserved   