XL: Solver Uses Generalized Reduced Gradient Algorithm

• Microsoft Excel for Windows, versions 3.0, 4.0, 4.0a, 5.0, 5.0c
• Microsoft Excel for Windows 95, versions 7.0, 7.0a
• Microsoft Excel 97 for Windows
• Microsoft Excel for the Macintosh, versions 3.0, 4.0, 5.0, 5.0a
• Microsoft Excel 98 Macintosh Edition

SUMMARY

Microsoft Excel Solver uses the Generalized Reduced Gradient (GRG2) Algorithm for optimizing nonlinear problems. This algorithm was developed by Leon Lasdon, of the University of Texas at Austin, and Allan Waren, of Cleveland State University.

Linear and integer problems use the simplex method with bounds on the variables and the branch and bound method, implemented by John Watson and Dan Fylstra, of Frontline Systems, Inc.

MORE INFORMATION

Microsoft Excel Solver uses iterative numerical methods that involve "plugging in" trial values for the adjustable cells and observing the results calculated by the constraint cells and the optimum cell. Each trial is called an "iteration." Because a pure "trial and error" approach would an extremely long time (especially for problems involving many adjustable cells and constraints), Microsoft Excel Solver performs extensive analyses of the observed outputs and their rates of change as the inputs are varied, to guide the selection of new trial values.

In a typical problem, the constraints and the optimum cell are functions of (that is, they depend on) the adjustable cells. The (first derivative of a function measures its rate of change as the input is varied. When there are several values entered, the function has several partial derivatives measuring its rate of change with respect to each of the input values; together, the partial derivatives form a vector called the gradient of the function.

Derivatives (and gradients) play a crucial role in iterative methods in Microsoft Excel Solver. They provide clues as to how the adjustable cells should be varied. For example, if the optimum cell is being maximized and its partial derivative with respect to one adjustable cell is a large positive number, while another partial derivative is near zero, Microsoft Excel Solver will probably increase the first adjustable cell's value on the next iteration. A negative partial derivative suggests that the related adjustable cell's value should be varied in the opposite direction.

Forward and Central Differencing

Microsoft Excel Solver approximates the derivatives numerically by moving each adjustable cell value slightly and observing the rate of change of each constraint cell and the optimum cell. This process is called a finite difference estimate of the derivative. Microsoft Excel Solver can use either forward differencing or central differencing, as controlled by the Derivatives choice on the Solver Options dialog box.

Forward differencing uses a single point (that is, set of adjustable cell values) that is slightly different from the current point to compute the derivative, while central differencing uses two points in opposite directions. Central differencing is more accurate if the derivative is changing rapidly at the current point, but requires more recalculations. The default choice is forward differencing, which is fine in most situations.

Linear problems can be solved with far less work than nonlinear problems; Microsoft Excel Solver does not need to recompute changing derivatives, and it can extrapolate along straight lines instead of recalculating the worksheet. These time savings are brought into play when you select the Assume Linear Model check box in the Solver Options dialog box. If you don't select this box, Microsoft Excel Solver can still solve the problem, but it will spend extra time doing so.

When you know that a problem is completely linear, choosing the Assume Linear Model option will speed up the solution process by a factor of two to twenty times (depending on the size of the worksheet). The downside is that, if the real worksheet formulas are nonlinear and this option is selected, you solve the wrong problem.

Although Microsoft Excel Solver does check the final solution when Assume Linear Model is checked using a full worksheet recalculation, this is not an absolute guarantee that the problem is truly linear. You can always recheck the solution by running the same problem with the check box cleared.

Many business worksheets contain mostly linear formulas plus a few key nonlinear relationships, such as the Revenue equals Price times Unit Volume example cited earlier. These problems are not amenable to the methods of linear programming or the Assume Linear Model option. They require the full power of nonlinear programming. The Generalized Reduced Gradient method used by Microsoft Excel Solver is quite efficient for problems of this type because it uses linear approximations to the problem functions at a number of stages in the solution process; when the actual functions are linear, these approximations are exact.

Optimality Conditions

Because the first derivative (or gradient) of the optimum cell measures its rate of change with respect to (each of) the adjustable cells, when all of the partial derivatives of the optimum cell are zero (that is, the gradient is the zero vector), the first-order conditions for optimality have been satisfied (some additional second order conditions must be checked as well) having found the highest (or lowest) possible value for the optimum cell.

Multiple Locally Optimum Points

Some problems have many locally optimum points where the partial derivatives of the optimum cell are zero. A graph of the optimum cell function in such cases would show many hills and valleys of varying heights and depths. When started at a given set of adjustable cell values, the methods used by Microsoft Excel Solver will tend to converge on a single hilltop or valley floor close to the starting point. But Microsoft Excel Solver has no sure way of knowing whether there is a taller hilltop, for example, some distance away.

The only way to find the global optimum is to apply external knowledge of the problem. Either through common sense reasoning about the problem or through experimentation, you must determine the general region in which the global optimum lies and start Microsoft Excel Solver with adjustable cell values that are within that region. Alternatively, you can start Microsoft Excel Solver from several different, widely separated points and see which solution is best.

For more information about Solver's internal solution process, contact:

   Frontline Systems
   P.O. Box 4288
   Incline Village, Nevada  89450-4288
   (702) 831-0300

The third-party contact information included in this article is provided to help you find the technical support you need. This contact information is subject to change without notice. Microsoft in no way guarantees the accuracy of this third-party contact information.

The Microsoft Excel Solver program code is copyright 1990, 1991, 1992 by Frontline Systems, Inc. Portions copyright 1989 by Optimal Methods, Inc.

REFERENCES

"Microsoft Excel Solver User's Guide" for the Macintosh, version 3.0, page 2 "Microsoft Excel Solver User's Guide" for Windows, version 3.0, page 2