Return to Index
Operations Research Models and Methods
Computation Section
Subunit Nonlinear Programming
 - Solving the Problem

Given a starting vector for the decision variables, the Excel Solver program uses a search procedure to move to a local optimum. That is, a point in the feasible region such that no improvement can be made by small perturbations from the point. It is a known result that when maximizing a concave objective function with linear constraints every local optimum is a global optimum, the solution that is the best of all feasible solutions. Since the objective function terms for this example are concave, when the Solver program terminates at a point with an indication of optimality, the point should be the global optimum.

In general, we cannot be sure that the Excel Solver or any nonlinear programming algorithm will terminate at an optimal point unless some rather stringent conditions are satisfied. These conditions are the subject of nonlinear programming textbooks. For example if the objective function terms were convex, rather than concave, the algorithm will always terminate at an extreme point of the feasible region (when the region is defined by linear constraints). In many cases the extreme points will not be globally optimum solutions. The situation is even further complicated for integer-nonlinear models. An extensive coverage of these features would take many pages, but the user should beware of the problem of assuring optimality for nonlinear models.

There are limitations on the functions that can appear in nonlinear terms. The functions should be defined, continuous and differentiable in and near the feasible region. This eliminates the use of IF, integer, and absolute value functions in the model. Ratios with denominators that might go to zero or square root terms that have negative arguments are similarly not allowed. These restrictions must be obeyed at every point that the Solver program might try to evaluate. Even if the initial solution is feasible, the Solver program might make small incursions outside the feasible region during the search process. If the program encounters a point for which a function cannot be evaluated it stops with an error message.

The problem of finding the global optimum from perhaps a large set of local optima is been the subject of much theoretical as well as practical effort. This field of research and practice is called Global Optimization. Frontline Systems, the distributor of the Excel Solver has premium systems that implement highly advanced methods for finding global optimum solutions.


Return to Top

tree roots

Operations Research Models and Methods
by Paul A. Jensen
Copyright 2004 - All rights reserved

Next Page