Optimization method development and solver comparison
April 25, 2014 Post doc researchers
In research and industry the need to solve complex problems is evident and the use of optimization often provides a solution. A researcher might gain insights by solving a problem while an industry might find more efficient operational solutions. Therefore, it is important that the development in the optimization field is made accessible to its practitioners.
The advances in optimization consist of theoretical findings that improve methods and models, as well as, the increase in computing power. Optimization platforms like AIMMS, AMPL and GAMS provide the interface to the optimization methods.
The optimization problems can be divided into different classes and one of the most general classes of optimization problems is the Mixed-Integer Non-Linear Programming (MINLP) class. In this class there is no method or algorithm that would be the most suitable for all problems. Most methods do not guarantee that the global optimal or even an optimal solution can be found. Additionally, the solution time is another concern. Therefore, several different methods are usually available on an optimization platform. The Extended Cutting Plane (ECP) method (1) has proven to be efficient for many problems, for example, block layout design, quadratic assignment and chromatographic separation problems. During our research we have made the method available by implementing it in the GAMS modeling system. We have further developed the solving capability by integrating a Non-Linear Programming (NLP) solver to the solving procedure, exception handling when computational problems occur and introduced a heuristic to improve the performance (2).
To obtain an idea of how the different methods perform the solvers can be benchmarked. A comparison can indicate which method can solve many different types of problems or how the different methods solve some particular problems. Some benchmarking results of GAMS solvers can be found in (2) and (3).
(1) Westerlund T. and Pörn R., 2002, Solving Pseudo-Convex Mixed Integer Optimization Problems by Cutting Plane Techniques, Optimization and Engineering, 3, 253-280.
(2) Lastusilta T., 2011, GAMS MINLP Solver Comparisons and Some Improvements to the AlphaECP Algorithm. PhD thesis, Åbo Akademi University, Biskopsgatan 8, 20500 Åbo, Finland, ISBN 978-952-12-2653-3.
(3) Lastusilta T., Bussieck M. R. and Westerlund T., 2009, An Experimental Study of GAMS/AlphaECP MINLP Solver, Ind. Eng. Chem. Res. 48, 7337-7345.