Researchers from Argonne National Laboratory, IIT Bombay, and the University of Wisconsin – Madison have received the Mathematical Programming Computation “Best Paper of the Year” award for 2021.
The award-winning paper describes Minotaur, a general framework for solving mixed-integer nonlinear programs (MINLPs), a type of numerical optimization problem that includes discrete choices and a nonlinear objective and constraints. Such problems, which commonly arise in science, engineering and financial applications, pose several challenges to algorithm developers. In particular, MINLP algorithms must be able to handle nonlinear functions; and a single MINLP solver may require several classes of relaxations, or approximations, to be solved as subproblems.
Key to Minotaur’s success is its ability to take advantage of the problem structure, properties of the constraints and variables that can – and sometimes must – be exploited to solve the problem. While other algorithms have made use of special problem structure, Minotaur provides a general, more flexible software framework that is not associated with a particular problem type or solver.
“This flexibility is critical,” said Sven Leyffer, a senior computational mathematician at Argonne’s Mathematics and Computer Science division and a principal investigator of the MACSER (Multifaceted Mathematics for Rare, High Impact Events in Complex Energy and Environment Systems) project. “Without it, finding global solutions to difficult nonconvex MINLP problems is simply out of reach for many applications. Moreover, the flexibility is achieved without introducing additional computational overhead.”
Extensibility is also important. Minotaur uses a modular approach that allows developers to easily implement new functionality, customizing only a few selected components and using the other remaining components to produce new solvers.
The approach also makes it easy to develop extensions to solvers. The paper presents several structure-exploiting extensions to the basic algorithms implemented in Minotaur. In each case, the authors detail the main algorithmic idea, show how it is implemented in Minotaur, and give numerical results from experiments. including a nonlinear presolve technique that was able to solve 10% more instances than the standard solver does.
By providing a flexible, extensible framework for exploring new algorithms and exploiting problem structure, the developers of Minotaur hope that the new framework will be used to advance the state of the art in nonconvex MINLP problem solving.
The full paper is available at https://link.springer.com/article/10.1007/s12532-020-00196-1. The citation is Ashutosh Mahajan, Sven Leyffer, Jeff Linderoth, James Luedtke, and Todd Munson, “Minotaur: a mixed-integer nonlinear optimization toolkit,” Mathematical Programming Computation 13, 301-338, 2021.