A Tale of Two Problems: Integer and Nonlinear Optimization
Sven Leyffer, Argonne National Laboratory, USA
Co-author: Jeff Linderoth, University of Wisconsin, Madison

Many scientific, engineering, and public sector applications involve both discrete decisions and nonlinear system dynamics that affect the optimality of the final design.  Mixed-integer nonlinear programs (MINLPs) combine the difficulty of optimizing over discrete variable sets with the challenges of handling nonlinear functions. The discrete components of an MINLP model phenomena such as fixed charges, dichotomies, piecewise linear functions, and general logical relationships between entities in the system.  Nonlinearities often describe phenomena such as covariance, economies of scale, and queuing delays or physical properties such as pressure, stress, and equilibrium.

We present a survey of recent advances in the solution of MINLPs based on branch-and-cut that have resulted in the new solver FilMINT. Our new solver combines MINTO's branch-and-cut framework for MILP with filterSQP to solve the nonlinear programs. It updates the MILP branch-and-cut tree with new linearization cuts, and integrates modern MIP solver techniques.

An important component of mixed-integer solvers are fast heuristics for finding good incumbent solutions. We describe the extension of standard MILP heuristics such as branch-and-pump to MINLP problems, and demonstrate the effectiveness of the new heuristics on a range of challenging test problems.