If the Solution Process Takes a Long Time

[Dividing Line Image]

Most Solver problems are computationally intensive -- and the time the Solver takes to solve a problem rises rapidly as the size of your spreadsheet and the number of decision variables and constraints increases. This page discusses methods you can use to reduce the time taken by the Solver. Frontline's enhanced solvers can usually solve problems much faster than the standard Microsoft Excel Solver -- up to 100 times faster in some cases. Even so, the methods discussed here will help reduce the time taken by the enhanced solvers even more. The earlier in your model design process that you consider these factors, the better off you'll be when the model becomes larger (as it seemingly always does).

The bottleneck in the solution process is nearly always recalculation time. While the Solver employs sophisticated, computationally intensive numerical methods internally, it still spends as much as 90% of its time waiting for Microsoft Excel to recalculate the worksheet. Therefore, any steps you can take to reduce recalculation time will favorably impact the Solver's solution time.

Linear Versus Nonlinear Models

If you have a linear problem, make sure that you've checked the Assume Linear Model box in the Solver Options dialog. If you haven't checked this box, the Solver assumes that the problem is nonlinear. The Solver is many times faster on linear than on nonlinear problems, and this speed difference rises very rapidly with an increased number of decision variables.

When the problem is linear, the Solver will recalculate the model approximately N times, where N is the number of decision variables (or changing cells). This happens once, during the phase when "Setting Up Problem..." appears on the Excel message bar. When the problem is nonlinear, the Solver must recalculate the model N times on every major iteration, in order to update its estimate of how the objective function and constraints are changing. For this reason, you'll see the Solver spending much more time on each "Trial Solution" reported on the Excel message bar for a nonlinear problem. Further, on linear problems the Solver is able use faster and more reliable methods to choose the decision variable values for the next trial solution.

We often see Solver models from users who are convinced that their problems are intrinsically nonlinear, yet we find that with a modest effort (sometimes no effort) these models can be set up as linear problems. If solution time is an issue, it is worth your while to consider whether the model really could be formulated as a linear problem. For more information on this topic, consult Linear and Nonlinear Functions.

Eliminating Non-Essential Calculations

During the solution process, the Solver adjusts only the values of the decision variables (changing cells). Any calculated cell values which do not depend on the decision variables will remain constant in the Solver problem. Microsoft Excel uses "smart" recalculation methods to determine which cells may have changed their values and therefore need to be recalculated. However, some time is expended in checking which cells have changed -- and this time can add up if you have hundreds or thousands of cells which must be checked.

It is a good idea to design your application so that the changeable elements of a Solver model are kept by themselves on one worksheet. You may have many other calculations in cells on other worksheets, whose values must be referenced in the Solver model. Although you can refer to these values through linking formulas such as =Sheet1!A1, such references are relatively expensive in recalculation time. To achieve the greatest savings in solution time, you'll need to copy only the values (not the formulas) from the other worksheets to your Solver model worksheet, prior to running the Solver. You can automate this process with a short macro in either VBA or the macro language.

Adding or Tightening Constraints

Bear in mind that the Solver searches for an optimal solution within an N-dimensional "feasible space" whose boundaries are determined by the constraints. If you can tighten the constraints -- by increasing lower bounds in >= constraints and decreasing upper bounds in <= constraints, you will give the Solver a smaller area to search, which will usually take less time.

It often pays to add constraints, as long as they are not redundant -- i.e. if they do indeed reduce the size of the feasible region. Although the Solver must do more work on every iteration to process the extra constraints, often the result is that the solution process takes fewer iterations, for an overall time savings.

Methods for Nonlinear Problems

Starting Values. The nonlinear Solver uses the starting values of the decision variables to determine where to search for feasible, and later optimal trial solutions. The closer the starting values are to the actual solution, the less time the Solver will require in most cases. The Solver Results dialog, which appears when the Solver stops (even if the time or iteration limit was reached or you pressed ESC), allows you to save or discard the latest values of the decision variables. It usually pays to save these values so that they become the starting values the next time you choose Solve. For some problems, you may want to save several sets of variable values; you can do this with the Save Scenario button in the Solver Results and Show Trial Solutions dialogs.

Forward vs. Central Differencing. The Solver Options dialog includes a Derivatives option box, where you can choose Forward or Central (see Estimates, Derivatives and Search for details). Forward is the default choice. The Central option causes the Solver to perform twice as many recalculations in computing the partial derivatives at each major iteration. This will usually take more time on each iteration than the time saved from fewer iterations. You should choose the Central option only if the Solver is having difficulty reaching the optimal solution, and if the constraints are changing rapidly close to their bounds.

Frontline's enhanced solvers often can do little to speed up the solution process for a nonlinear problem. Most of the methods they employ are effective only for linear and integer problems. We are working on advanced algorithmic methods for use in future products, which we believe will significantly speed up the solution process for nonlinear models in Microsoft Excel.

Methods for Integer Problems

Problems with integer constraints can be extremely difficult and time-consuming to solve. There are problems with only a few hundred integer constraints which have never been solved, even with custom programs running on the fastest parallel supercomputers -- let alone in Microsoft Excel! Unfortunately it is difficult to know in advance whether a given problem will be solved easily, or will take a great deal of time. A different formulation of the same underlying problem may require 100 to 1000 times more or less solution time in some cases.

Bear in mind that the Branch and Bound method solves a large number of subproblems, each one an instance of the problem on your worksheet without the integer constraints. Thus, efforts to reduce solution time on the subproblems, through the measures described above, will pay off many times over in an integer problem. If the problem involves many variables and constraints, the subproblems must for practical purposes be linear if you are to have a realistic chance of finding an optimal or near-optimal solution. Adding or tightening constraints can be quite effective in reducing solution time on integer problems. And of course, it pays to eliminate non-essential calculations from the worksheet containing the Solver model.

The Tolerance option in the Solver Options dialog allows you to specify a tolerance within which an integer solution (one where the variables with integer constraints do have integer values) will be considered "good enough," allowing the Solver to stop and report its best solution so far. The default value for this Tolerance is 0.05, which will allow the Solver to stop when the objective function value is within 5% of the true integer optimal objective. Since the Branch and Bound process can take a great deal of time try to "close the gap" represented by the Tolerance setting, it is often a good idea to increase this value for a difficult integer problem.

Fast Problem Setup

If you have a linear or quadratic problem (possibly with integer constraints) where you can see that much of the total solution time is spent with "Setting Up Problem..." on the Excel message bar, there is a good chance that Frontline's enhanced solvers can be used to greatly reduce your solution time. To gain this benefit, you'll need to write your objective and constraint formulas using certain functions such as SUM, SUMPRODUCT, and Frontline's add-in DOTPRODUCT and QUADPRODUCT functions. For problems with hundreds of decision variables or more, fast problem setup can be 10 times or even 100 times faster. For more information on fast problem setup, follow the hyperlinks in this paragraph.