Relaxation and decomposition methods for mixed integer nonlinear programming

Más información sobre el libro

Nonlinear optimization problems that include both continuous and discrete variables are known as mixed integer nonlinear programs (MINLP). These problems are prevalent in various fields such as process industry, engineering design, communications, and finance. Currently, there is a significant disparity between the capabilities of MINLP and mixed integer linear programming (MIP) solvers. While modern MIP solvers can handle models with millions of variables and constraints, the size of solvable MINLPs is often limited by three to four orders of magnitude. Although it is theoretically feasible to approximate a general MINLP with a MIP, effective MIP approximations tend to be much larger than the original problem, and approximating nonlinear functions with piecewise linear functions can be complex and time-consuming. This work proposes relaxation and decomposition methods for solving nonconvex structured MINLPs, introducing a generic branch-cut-and-price (BCP) framework for MINLP. BCP, a foundational concept in contemporary MIP solvers, offers a robust decomposition framework for both sequential and parallel solvers, contributing to the success of current MIP technology. While generic BCP frameworks have been established for MIP, adapting this to MINLP requires several considerations: reformulating a sparse MINLP as a block-separable program with linear coupling constraints, constructing nonlinear convex relaxations for polyhedr