Progress in MINLP Solver Technology

The field of mathematical solvers has seen tremendous improvements in the last decades. LP / MIP solvers, in particular, are now heavily dominated by companies that specialize in the continuous improvement of the algorithms. These commercially driven improvements are important for customers, who in return enjoy ever increasing performance. In the age of big data this is vital for many industries, where millions of dollars can be saved by using performant solver technology.

In contrast to the industry-dominated LP / MIP field, MINLP solver technology is much more attractive to academic researchers who can still build successful university careers around this field. The competition between different groups is friendly, and many of the advances are published in the academic literature, driving the whole field forward.

GAMS has also had an interest in MINLP technology early on. In fact, GAMS / DICOPT was the very first modeling-language / solver-combination able to solve MINLPs. Our team also established a comprehensive library of MINLP models¹, ranging from simple text-book examples all the way to large industry models with many thousands of variables. Along with this, we released a conversion tool, which enabled researchers to convert library models from GAMS to other languages such as AMPL, LINGO, LGO and MINOPT. The library used to be part of “GAMS-World”, but has now taken on a life of its own at https://minlplib.org/ and continues to be a valuable resource to people in the field.

This fall we have the opportunity to celebrate two occasions related to some of the most well known MINLP solvers coming out of the academic arena: BARON (now maintained by The Optimization Firm ), and SCIP . The contributions of BARON’s inventor Nick Sahinidis to advancements in the field have been recognized this October by his induction to the National Academy of Engineering Class of 2022, an honor he shares with 132 awardees from other fields important to society, such as vaccine development, renewable energy technologies, or space flight. The SCIP team on the other hand celebrated the solver’s 20th anniversary with the “Let’s SCIP it!” workshop in early November. With the event they have changed the SCIP license terms to the Apache 2.0 license, which makes the solver fully open source.

MINLP Solver Performance Gains

As anyone who works in the field would know, benchmarks are a great way to demonstrate the progress you have made. Since MINLP is a very general problem class, finding a test set that properly reflects the majority of actual problems in the wild is very challenging. Therefore, results of any benchmark need to be taken with a grain of salt. Nevertheless, benchmark sets are often well suited to track performance progress of solvers over time.

BARON performance development over time

BARON started out with a couple of thousand lines of GAMS code in the early 1990s, to 250,000 lines of high performance C and Fortran code. Over the last approximately 20 years, BARON’s performance on a set of 87 MINLPLib instances has improved by about 10x in speed, and 3x in the number of problems solvable. The figure below by Nick Sahinidis summarizes the improvements over time.

SCIP performance development over time

Similarly to the BARON team, the SCIP people established a performance timeline for their code. For this, the code was recompiled for all SCIP versions able to solve MINLPs, from v3.0.2 (Oct 2013) to v8.0.1 (Jun 2022), using the same versions of CPLEX and IPOPT as LP and NLP subsolvers, respectively. This allows isolating the development of the SCIP code from the subsolver code (which of course has also been improved in those years).

The results of benchmarking runs were presented by Marc Pfetsch, TU Darmstadt, in the presentation “SCIP: Past, Present, Future” during the anniversary meeting (see also https://scipopt.org/20years/ ). 183 MINLP model instances from a benchmark set from MINLPLib were tested. On the same hardware, the number of solvable models increased from 54 with SCIP 3.0.2, to 108 with SCIP 8.0.1, and at the same time the mean solve time was reduced 3.1-fold.

Implications for algebraic modeling languages - or why solver independence is so valuable

Apart from the fact that algebraic modeling languages (AMLs) such as GAMS enable domain experts to formulate their problems in a straightforward manner and pass them to a solver, the performance gains of both BARON and SCIP are additional, important reasons for why AMLs are so valuable for organizations that stay in the optimization business for a long time. The solver independence allows them to take advantage of all the performance gains made over the years, without having to change their model code. Also, when older solvers are not maintained by their developers any longer, and new solvers arrive on the scene (e.g. Octeract ), modelers can easily switch between those solvers, and the time invested in model development is protected. With ANTIGONE, BARON, Lindo, Octeract, and SCIP, five global MINLP solvers are currently distributed with GAMS, and we hope to see FICO Xpress joining the gang next year.

Here at GAMS we thoroughly enjoy being affiliated with the friendly community around MINLP solvers, and welcome the open competition typical for academia, which ultimately leads to better algorithms and more solvable problems.