|
Contact: Daniel Fylstra |
News Release |
Psi Technology Replaces Core of Excel,
Powers New Premium Solver Platform
Psi is an acronym for Frontline's Polymorphic Spreadsheet Interpreter, the underlying technology that powers its optimization software for Excel. The word "polymorphic" has roughly the same meaning as it does in C++, Java, and similar object-oriented languages. Frontline's Polymorphic Interpreter replaces the core interpreter -- or recalculator -- in Microsoft Excel. Like Excel, it reads or "parses" spreadsheet formulas, but it is capable of interpreting these formulas in many different ways -- effectively "overloading," or assigning new and more powerful "meanings" to all the operators and functions in spreadsheet formulas.
For years, the Premium Solver products 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 relied on Microsoft Excel to evaluate the formulas in the spreadsheet model. This changed in the Premium Solver Platform Version 5.
- The Microsoft Excel Recalculator
- The Polymorphic Spreadsheet Interpreter
- Impact on Building Models
- Impact on Solver Performance
- Impact on Large-Scale Models
- The Interval Global Solver
- About Excel Built-in Functions
The Microsoft Excel Recalculator
When the Solver runs, the formulas in the 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 spreadsheet formulas. But Solvers frequently need to compute both values and derivatives of 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 the Solver, 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 -- the model appears as a "black box" to the Solver.
The Polymorphic Spreadsheet Interpreter
In the Premium Solver Platform Version 5, the user's model can be evaluated by Frontline's Polymorphic Spreadsheet Interpreter. (The Premium Solver Platform can also use the Excel recalculator, in the same way as previous versions of the Solver.) The Interpreter can analyze the model in many ways not possible with the Excel recalculator:
- The Psi technology can diagnose the model as a linear programming, quadratic programming, smooth nonlinear, or non-smooth optimization model, and automatically select Solver engines suitable for the model. It can even pinpoint formulas that make the model nonlinear or non-smooth.
- The Psi technology can compute derivatives of the problem functions directly, using the methods of automatic differentiation. This is much faster and more accurate than the method of formula recalculation and "finite differencing" used by the Excel Solver and Premium Solver.
- The Psi technology can compute interval values for Excel formulas in the model, in addition to simple numeric values. This capability is used by the new Interval Global Solver to find globally optimal solutions to optimization problems.
The Polymorphic Spreadsheet Interpreter is capable of doing much more -- it can realize performance breakthroughs for analytic methods beyond optimization. Future Frontline products will further leverage the Psi technology.
Impact on Building Models
Users spend far more time designing, building and testing their models than solving them -- and people time is far more expensive than computer time. Tools that can save users time in building their models can be worth a lot. The Psi technology is just such a tool. 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 Psi Technology, this process is completely automated. Using the new Solver Model dialog, the user simply selects the type of model he or she 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 the model. This can save hours of time.
Impact on Solver Performance
The Psi Technology 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 Psi Technology 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 Psi Technology 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 Version 3.5, the Premium Solver Platform Version 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 Psi technology is even greater for large-scale Solver models that may consist of many thousands of variables and constraints. The Polymorphic Spreadsheet Interpreter will determine, not just whether a 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 Psi Technology -- 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 new Interpreter.
For example, the Large-Scale SQP Solver will automatically break down a model into linear and nonlinear parts, and solve each part using the best algorithms from both linear programming and nonlinear optimization. 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 Version 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 Psi Technology to evaluate Excel formulas over intervals, and to compute interval gradients. The result is a fundamental new capability in the Premium Solver Platform Version 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 Psi Technology supports almost all of these functions. But how confident can users 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.
In summary, the Psi Technology radically improves almost every aspect of spreadsheet optimization, by replacing the core of Microsoft Excel -- the formula recalculator -- with a far more powerful alternative for Solver engines of every type and size. But this is only the beginning of the story of the Psi Technology -- it promises further radical improvements to other kinds of analytical software in the future.
