solver.com

For over ten years, the Premium Solver products have steadily increased the capacity and power of the optimization algorithms in the Solver.  But for all this time, the Excel Solver and Premium Solver products have relied on Microsoft Excel to evaluate the formulas in your model.  This has changed in the Premium Solver Platform V5.5.

The Microsoft Excel Recalculator

When the Solver runs, the formulas in your model are evaluated for many different values of the decision variables -- thousands, tens or hundreds of thousands, or even millions of times.  Though the actual "solving" is done by the optimization algorithms, for speed and accuracy purposes, formula evaluation forms the heart of the process.

The Microsoft Excel formula evaluator (the "recalculator") is very efficient, but it's designed to do only one thing:  Compute values for your formulas.  But optimization algorithms frequently need to compute both values and derivatives of your formulas -- and doing this with the Excel recalculator is relatively slow and inaccurate.

For the Excel recalculator, "all formulas are equal," whether the operators and functions are linear like + and -, nonlinear like SIN and COS, or non-smooth like IF and LOOKUP.  But for optimization algorithms, the types of operators and functions matter a great deal.  The Excel recalculator cannot tell the Solver whether your formulas are linear, quadratic, smooth nonlinear or non-smooth -- your model appears as a "black box" to the Solver.

The V5.5 Parser and Interpreter

In the Premium Solver Platform V5.5, your model can be evaluated by a new Parser and Interpreter for Excel formulas, developed by Frontline Systems.  (The Premium Solver Platform can also use the Excel recalculator, in the same way as previous versions of the Solver.)  The Parser and Interpreter can analyze your model in many ways not possible with the Excel recalculator:

Impact on Building Your Model

You'll probably spend far more hours designing, building and testing your model than you'll spend solving it -- and people time is far more expensive than computer time.  Tools that can save you time in building your model can be worth a lot.  In the Premium Solver Platform V5.5, the Parser and Interpreter are worth their weight in gold.

Because it's so easy to create models in Microsoft Excel, and because "all formulas are equal" to the Excel recalculator, users often create large, complex spreadsheet models, then try to optimize them.  Suddenly it matters whether the formulas are linear, quadratic, smooth nonlinear, or non-smooth -- since this affects the speed of the solution process, and even whether a solution can be found at all.

In the past, users often had to analyze their models by hand -- examining hundreds or thousands of formulas for nonlinear or non-smooth operators and functions.  With the Parser and Interpreter, this process is completely automated.  Using the new Solver Model dialog, you simply select the type of model you intended to create (e.g. LP or QP), and the Solver will find and report any nonlinear or non-smooth operators or functions in any of the formulas of your model.  This can save you hours of time.

Impact on Solver Performance

The new Interpreter computes values for Excel formulas at about the same speed as the Microsoft Excel recalculator.  But it greatly outperforms the Excel recalculator in computing derivatives of problem functions.  Using the methods of automatic differentiation, the Interpreter computes derivatives, gradients, Jacobians and Hessians (matrices of first and second order partial derivatives) with up to twice the accuracy of the Excel recalculator, at much faster speeds -- and the speed advantage grows with the size of the model.

Further, where the Excel recalculator will evaluate all formulas that depend on the decision variables, the Interpreter will evaluate only those formulas that are part of the objective and constraints.  When a Solver model is part of a larger spreadsheet that calculates many other results based on the decision variable cells, this can save a great deal of time.

What's the bottom line impact on performance?  On a sample of twenty real-world models built by users of the Premium Solver Platform V3.5, the Premium Solver Platform V5.5 was on average twice as fast on linear models, and seven times faster on nonlinear models.  These models were not exceptionally large -- the speed gains available with large-scale models may be even greater.

Impact on Large-Scale Models

The impact of the Parser and Interpreter is even greater for large-scale Solver models that may consist of many thousands of variables and constraints.  The Parser and Interpreter will determine, not just whether your overall model is linear, quadratic, nonlinear or non-smooth, but whether individual functions or even parts of functions have these properties.  For example, if A1:A5 are decision variables, the formula:

=2*A1 + 3*A2^2 + LOG(A3) + IF(A4>0,A4,0)

has a linear dependence on A1, a quadratic dependence on A2, a smooth nonlinear dependence on A3, a non-smooth dependence on A4 -- and no dependence on A5.  Solvers can take advantage of this information to improve performance.

All large-scale Solver engines take advantage of sparsity information provided by the Parser and Interpreter -- cases where functions are not dependent on all of the variables, as with A5 above.  And some Solver engines take further advantage of the properties of individual functions, or parts of functions, available from the Parser and Interpreter.

Most notably, the Large-Scale SQP Solver will automatically break down your model into linear and nonlinear parts, and solve each part using the best algorithms from both linear programming and nonlinear optimization.  For example, in the common case of a model where most of the variables occur linearly in most of the constraints, but some nonlinear operators or functions make the model nonlinear overall, the Large-Scale SQP Solver can offer breakthrough performance, that just wasn't possible with the Microsoft Excel recalculator alone.

The Interval Global Solver

The new Interval Global Solver in the Premium Solver Platform V5.5 -- which finds solutions for global optimization problems and all solutions for systems of nonlinear equations -- is based on state-of-the-art methods that evaluate problem functions over intervals rather than simple real numbers.  (An interval such as [1, 2] represents all possible values between 1 and 2 inclusive.)  The Interval Global Solver relies on the Parser and Interpreter to evaluate Excel formulas over intervals, and to compute interval gradients.  The result is a fundamental new capability in the Premium Solver Platform V5.5 that is hard to find in any other optimization software, at any price.

About Excel Built-in Functions

Microsoft Excel has over 320 built-in functions, including the financial, statistical, and engineering functions that are part of the Excel Analysis ToolPak. The Parser and Interpreter support almost all of these functions.  But how confident can you be that the values computed by the Interpreter will match the values that would have been computed by Excel?

Frontline Systems actually developed, under contract to Microsoft, implementations of most of the Excel built-in functions for use in the Internet Explorer "spreadsheet component" that is included with Microsoft Office 2000, Office XP and Office 2003. Frontline's functions were tested against the same functions in Microsoft Excel, in an extensive quality assurance process during the development of Office 2000. Because of this, Frontline Systems was uniquely qualified to develop a full-scale Interpreter for Microsoft Excel and its extensive library of built-in functions.

All things considered, Version 5.5 is indeed a "watershed" product release of the Premium Solver Platform:  It replaces the core of Microsoft Excel -- the formula recalculator -- with a far more powerful alternative for Solver engines of every type and size.