|
Contact: Daniel Fylstra |
News Release |
INCLINE VILLAGE, NV -- November 5, 2000 -- The Premium Solver Platform, Frontline Systems' new 'flagship' spreadsheet optimization product for Microsoft Excel, includes the most extensive list of enhancements ever included in a new Solver product release from Frontline. Every aspect of the Solver has been materially enhanced, yielding benefits for users no matter what type of optimization problem they need to solve.
Hybrid Evolutionary/Classical Solver Offers New Level of Performance
Frontline's Premium Solver V3.5 and Premium Solver Plus V3.5 introduced a new Evolutionary Solver, based on genetic algorithms, that has proven very popular with users. It allowed Premium Solver users to optimize spreadsheets containing functions like IF, CHOOSE and LOOKUP that aren't handled at all by classical linear, integer and nonlinear programming methods. Its popularity grew because of its superior performance compared to competitive products whose main or only feature was their genetic or evolutionary algorithm; its ease of use and compatibility with the standard Excel Solver; and the Premium Solver's combination of classical linear, integer or nonlinear optimizers plus an evolutionary algorithm, all easily selectable from a drop-down list of choices.
But like other pure genetic and evolutionary algorithms, the Evolutionary Solver almost always took much longer than classical methods to find a solution, and it often had difficulty finding feasible solutions for highly constrained problems (typical, for example, in linear and integer programming).
Perhaps the most powerful upgrade in the Premium Solver Platform is its new Evolutionary Solver, which is actually a hybrid of genetic and evolutionary algorithms and classical optimization methods -- including gradient-free 'direct search' methods, classical gradient-based quasi-Newton methods, and even the linear programming Simplex method for linear subsets of the constraints. The classical methods are invoked automatically at appropriate times to solve for the currently binding constraints, and they can also be used as an alternative in the 'local search' step, where the Evolutionary Solver seeks improved solutions in the neighborhood of a new best solution found by the main evolutionary algorithm.
This new hybrid Evolutionary Solver can be applied to extremely challenging problems, with both non-smooth or discontinuous functions and hundreds of conventional constraints, that were formerly beyond the reach of any spreadsheet optimizer, and perhaps any standard optimization software product.
New 'Alldifferent' Constraint Introduces Constraint Programming Features
Some genetic and evolutionary algorithm-based optimizers offer the ability to operate on permutations. These are sets of integer variables, all with unique values, where the optimizer's task is to determine the best ordering of the values. In other software, so-called constraint programming methods -- growing out of logic programming and artificial intelligence research -- have been used to operate on permutations. In this software, an 'alldifferent' constraint is defined to represent the required ordering or permutation. A well-known application of ordering or permutations is the Traveling Salesman Problem: Given a set of cities that a salesperson must visit, and the distances between them, determine the order of city visits that will minimize total travel time. Problems of this type are rather difficult to define and to solve using conventional constraints, but a single 'alldifferent' constraint is enough to capture the problem statement.
The Premium Solver Platform introduces the 'alldifferent' constraint to spreadsheet optimization, for the first time. And this new constraint type is supported by both the classical and Evolutionary Solvers in the Premium Solver Platform -- giving users a choice of solution methods for such problems. What's more, the Premium Solver Platform can automatically handle 'alldifferent' constraints for field-installable Solver engines that do not include native support for such constraints.
'Multistart' Methods Allow GRG Nonlinear Solver to Handle Global Optimization
For almost ten years, the classical GRG (Generalized Reduced Gradient) Solver has been used to find optimal solutions to smooth nonlinear problems in the standard Excel Solver and the Premium Solver products. But this Solver -- like other classical gradient-based methods -- is guaranteed only to find a locally optimal solution. To find the globally optimal solution to a problem with many locally optimal solutions, users had to rely either on external knowledge of the problem, or on a manual exploratory process, where the Solver was run from various starting points to see which point led to the best of the locally optimal solutions.
In the Premium Solver Platform, the GRG Solver has been augmented with so-called 'multistart' or 'clustering' methods, specifically 'multi-level single linkage' and a so-called 'topographic' extension of this method. Multistart methods randomly sample starting points, 'cluster' them into groups that are likely to lead to the same locally optimally solution, and then run a local optimizer, such as the GRG Solver, from the best point in each cluster. A Bayesian analysis is used to determine when to stop sampling new starting points.
For some smooth nonlinear problems, multistart methods can be proven to converge in probability to the globally optimal solution. For other problems, they often yield very good solutions in an acceptable amount of time - and of course, they are far easier to use than a manual exploratory process. As with the 'alldifferent' constraint, the Premium Solver Platform can automatically provide multistart capabilities for field-installable nonlinear Solver engines that do not natively support such methods.
Dual Simplex Method Speeds Solution of Linear Integer Problems
There's also good news in the Premium Solver Platform for users with linear mixed-integer programming (MIP) problems, especially those with general integer variables (as opposed to 0-1 or binary integer variables) that were not amenable to the preprocessing and probing methods introduced in the Premium Solver Plus V3.5. Using the dual Simplex method on MIP subproblems, the Premium Solver Platform is typically much faster on all types of integer programming problems. The speedup factor may be anywhere from 2-3 times to 10 times faster or more, with greater improvements on larger size problems.
Multiple, Field-Installable Solver 'Engines' to Handle Further Problems
Just in case the cornucopia of new features in the Premium Solver Platform isn't enough -- specifically, for users who have large-scale optimization problems, or special types of problems for which other optimization algorithms or methods may be better suited, the Premium Solver Platform includes support for multiple, field-installable Solver 'engines' in addition to its built-in linear, integer, quadratic, smooth nonlinear and Evolutionary Solvers.
These field-installable Solver engines are fully integrated into the Premium Solver Platform: They are selected from the Solver drop-down list in the main Solver Parameters dialog, just like the built-in Solvers. They can be paused, stopped and restarted, and they can produce reports in spreadsheet form, just like the built-in Solvers. Pressing the Options button in the main Solver Parameters dialog yields a custom Options dialog for the selected Solver engine, just as it does for the built-in Solvers. Options and parameters set in this way will be saved with a user's Excel workbook and may be recalled later. And VBA programs written for custom applications that control the Premium Solver Platform can use field-installable Solver engines in the same way as the built-in Solvers - even to the point of arranging to have custom VBA routines called from one of these Solver engines.
The Premium Solver Platform combines across-the-board enhancements today with the promise of a stream of further enhancements delivered via field-installable Solver engines in the future. Frontline expects that it will serve as the foundation for most of its future Solver product development efforts.