(271e) Branch-and-Price for a Class of Mixed-Integer Nonlinear Programs

Mixed-integer nonlinear programming (MINLP) has proven to be a powerful modeling paradigm and has received increased attention in the last three decades, particularly from the process systems engineering community. Tremendous advances have been made in the theoretical and algorithmic treatment of MINLPs, many of which were led by Prof. Grossmann and a number of his academic descendants. However, MINLPs are still significantly less scalable than their linear counterparts such that solving MINLPs of industrially relevant sizes remains a challenge.

We consider a class of (generally nonconvex) MINLPs whose structure makes them amenable to Dantzig-Wolfe reformulation and branch-and-price. We are particularly interested in the case where the pricing problem decomposes into smaller independent subproblems that can be efficiently solved using state-of-the-art global MINLP solvers. The feasibility of this idea has been indicated in the literature but has barely found any application. In this work, we show that many relevant problems directly fall or can be reformulated into this class of MINLPs. We present the branch-and-price algorithm, which converges to the global optimum, and comment on implementation considerations. The effectiveness of the algorithm is demonstrated in an extensive computational study considering various large-scale problems of practical relevance.