Exact and Approximation Methods for Mixed-Integer Nonlinear Programming Problem

Mixed-integer nonlinear programming problems (MINLPs) are frequently observed in the real world. These problems generally require more computational effort than their counterpart mixed-integer linear programming problems (MILPs). The solvers and solution technique improvements in the last few decades have enabled us to solve MINLPs of practical sizes. This chapter presents various techniques that can be used to solve MINLPs. We divide this chapter into approximation algorithms and exact algorithms. We discuss two approximation algorithms in detail: piece-wise linearization and linearization based on the McCormick envelope. These methods can be used to obtain feasible solutions with a guarantee on bound on a wide variety of problems, including non-convex problems, which are notoriously difficult to solve with an exact method. Next, we present the exact solution methods, which are guaranteed to give an optimal solution if the algorithms are allowed to run indefinitely. These methods, such as outer approximation and generalized Benders decomposition can be applied to problems where relaxation of integrality constraint makes the problem a convex optimization problem. Some non-convex problems can be convexified using the transformation of non-convex functions. These transformations might be computationally expensive but ensure an exact solution as a trade-off. With toy examples, we demonstrate the use of exact and approximation methods on MINLPs. We also provide a real-world case study for the location-allocation of shared wastewater treatment plants and show how different methods can be used to solve that problem.