Toni Lastusilta: "GAMS MINLP Solver Comparisons and Some Improvements to the AlphaECP Algorithm"
December 02, 2011 Andreas Lundell PhD theses
This PhD thesis studies the solving capability of some solvers for optimization problems, as well as presenting some improvements to one of the solvers.
The optimization problems that foremost are studied can be described by a model of Mixed Integer Non-Linear Programming (MINLP) class. The class of MINLP problems can be characterized as difficult and can be found in several industries and it is, therefore, well motivated to study which solvers effectively solve MINLP models. Only since 2003 have methods become available to solve these problems to global optimality, i.e. a guaranteed best possible solution, on optimization platforms like GAMS. Even though a method can solve a model to global optimality, it is of little use if the solution is not at hand when a decision needs to be made. Therefore, a solver which provides a good solution in reasonable time can, in some cases, be more useful. The study shows that all compared solvers have their strengths and weaknesses and that no solver is generally better than all the others.
The solver improvements are implemented in GAMS/AlphaECP, which is based on the Extended Cutting Plane (ECP) method. The improvements significantly increase solving capability and can be characterized as sensible. The enhancements include the integration of AlphaECP with another solving method, the implementation of a heuristic which can be activated when the solver cannot otherwise solve a problem and the use of existing information in an improved way.
The thesis can be downloaded here.