Advanced Methods
The research effort leading to the OptQuest Solver Engine is described in the book Tabu Search by Fred Glover and Manuel Laguna, and the book Scatter Search by Manuel Laguna and Rafael Marti. Click here to order it at our online bookstore. |
Intelligent, Population-Based Search
Where classical optimization methods keep track of a single "best solution" found so far, the OptQuest Solver maintains a population of candidate solutions. Any member of the population can give rise to a new, better solution, possibly far away from the "best solution" found so far. Because of this, the OptQuest Solver is unlikely to become "trapped" in the region of the locally optimal solution.
Tabu Search and Scatter Search
The OptQuest Solver uses metaheuristics such as tabu search and scatter search, with "memory" and "aging" of members of the population, to guide the generation of new trial solutions. Compared to a genetic or evolutionary algorithm, like the one used in the Evolutionary Solver in the Premium Solver Platform, the OptQuest Solver makes greater use of strategic choices and less use of randomization.
For example, the OptQuest Solver generates new points from linear combinations of existing points in the population, designed to lie both inside and outside the convex region spanned by the existing points -- where an evolutionary algorithm typically generates new points from random or semi-random combinations of existing points.
Automatic Handling of Linear Constraints
While it can handle any type of Excel function -- linear, nonlinear, or non-smooth -- the OptQuest Solver will automatically recognize and exploit any linear constraints in the model. It uses a variant of the Simplex method to "solve for" these constraints, thereby effectively reducing the dimensionality of the space to be explored. Models that include a significant number of linear constraints in addition to some non-smooth constraints are especially well-suited for the OptQuest Solver.
Highly Effective Handling of Integer Constraints
The OptQuest Solver is especially effective at solving non-smooth problems with integer constraints (including "alldifferent" constraints). It often outperforms all other known solution methods on these problems, including genetic and evolutionary algorithms -- even the Premium Solver Platform's hybrid Evolutionary Solver.
Population Report
The OptQuest Solver Engine can produce a Population Report in addition to the standard Answer Report. This report gives you summary information about the entire population of candidate solutions maintained by the Solver at the end of the solution process. The Population Report can give you insight into the performance of the OptQuest Solver Engine as well as the characteristics of your model, and help you decide whether additional Solver runs are likely to yield even better solutions. |