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 take 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. 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
You may also find information at
http://www.frontsys.com/
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.