Solver Uses Generalized Reduced Gradient Algorithm
This article was previously published under Q82890
This article has been archived. It is offered "as is" and will no longer be updated.
Microsoft Excel Solver uses the Generalized Reduced Gradient (GRG2)Algorithm for optimizing nonlinear problems. This algorithm was developedby Leon Lasdon, of the University of Texas at Austin, and Allan Waren, ofCleveland State University.
Linear and integer problems use the simplex method with bounds on thevariables and the branch and bound method, implemented by John Watson andDan Fylstra, of Frontline Systems, Inc.
Microsoft Excel Solver uses iterative numerical methods that involve"plugging in" trial values for the adjustable cells and observing theresults calculated by the constraint cells and the optimum cell. Eachtrial is called an "iteration." Because a pure "trial and error" approachwould take an extremely long time (especially for problems involving manyadjustable cells and constraints), Microsoft Excel Solver performsextensive analyses of the observed outputs and their rates of changeas the inputs are varied, to guide the selection of new trial values.
In a typical problem, the constraints and the optimum cell are functionsof (that is, they depend on) the adjustable cells. The (first derivativeof a function measures its rate of change as the input is varied. Whenthere are several values entered, the function has several partialderivatives measuring its rate of change with respect to each of theinput values; together, the partial derivatives form a vector calledthe gradient of the function.
Derivatives (and gradients) play a crucial role in iterative methods inMicrosoft Excel Solver. They provide clues as to how the adjustable cellsshould be varied. For example, if the optimum cell is being maximized andits partial derivative with respect to one adjustable cell is a largepositive number, while another partial derivative is near zero, MicrosoftExcel Solver will probably increase the first adjustable cell's value onthe next iteration. A negative partial derivative suggests that therelated adjustable cell's value should be varied in the oppositedirection.
Forward and Central DifferencingMicrosoft Excel Solver approximates the derivatives numerically by movingeach adjustable cell value slightly and observing the rate of change ofeach constraint cell and the optimum cell. This process is called a finitedifference estimate of the derivative. Microsoft Excel Solver can useeither forward differencing or central differencing, as controlled by theDerivatives choice on the Solver Options dialog box.
Forward differencing uses a single point (that is, set of adjustable cellvalues) that is slightly different from the current point to compute thederivative, while central differencing uses two points in oppositedirections. Central differencing is more accurate if the derivative ischanging rapidly at the current point, but requires more recalculations.The default choice is forward differencing, which is fine in mostsituations.
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 theworksheet. These time savings are brought into play when you select theAssume Linear Model check box in the Solver Options dialog box. If youdon'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 AssumeLinear Model option will speed up the solution process by a factor oftwo to twenty times (depending on the size of the worksheet). The downsideis that, if the real worksheet formulas are nonlinear and this option isselected, you solve the wrong problem.
Although Microsoft Excel Solver does check the final solution when AssumeLinear Model is checked using a full worksheet recalculation, this is notan absolute guarantee that the problem is truly linear. You can alwaysrecheck the solution by running the same problem with the check boxcleared.
Many business worksheets contain mostly linear formulas plus a few keynonlinear relationships. These problems are not amenable to themethods of linear programming or the Assume Linear Model option.They require the full power of nonlinear programming. The GeneralizedReduced Gradient method used by Microsoft Excel Solver is quiteefficient for problems of this type because it uses linearapproximations to the problem functions at a number of stages in thesolution process; when the actual functions are linear, theseapproximations are exact.
Optimality ConditionsBecause the first derivative (or gradient) of the optimum cell measuresits rate of change with respect to (each of) the adjustable cells, whenall of the partial derivatives of the optimum cell are zero (that is,the gradient is the zero vector), the first-order conditions foroptimality have been satisfied (some additional second order conditionsmust be checked as well) having found the highest (or lowest) possiblevalue for the optimum cell.
Multiple Locally Optimum PointsSome problems have many locally optimum points where the partialderivatives of the optimum cell are zero. A graph of the optimum cellfunction in such cases would show many hills and valleys of varyingheights and depths. When started at a given set of adjustable cellvalues, the methods used by Microsoft Excel Solver will tend toconverge on a single hilltop or valley floor close to the startingpoint. But Microsoft Excel Solver has no sure way of knowing whetherthere is a taller hilltop, for example, some distance away.
The only way to find the global optimum is to apply external knowledge ofthe problem. Either through common sense reasoning about the problem orthrough experimentation, you must determine the general region in whichthe global optimum lies and start Microsoft Excel Solver with adjustablecell values that are within that region. Alternatively, you can startMicrosoft Excel Solver from several different, widely separated pointsand 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
You may also find information at http://www.frontsys.com/
The third-party contact information included in this article is providedto help you find the technical support you need. This contact informationis subject to change without notice. Microsoft in no way guarantees theaccuracy of this third-party contact information.
The Microsoft Excel Solver program code is copyright 1990, 1991, 1992 byFrontline Systems, Inc. Portions copyright 1989 by Optimal Methods, Inc.
"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
4.00a 5.00a 5.00c 7.00a 97 98 XL98 XL97 XL7 XL5 XL4 XL3 GRG2 XL
Article ID: 82890 - Last Review: 12/04/2015 09:13:39 - Revision: 2.0
Microsoft Excel 2000 Standard Edition, Microsoft Excel 97 Standard Edition, Microsoft Excel 95 Standard Edition, Microsoft Excel 5.0 Standard Edition, Microsoft Excel 98 for Macintosh
- kbnosurvey kbarchive kbinfo KB82890