Global optimization of mixed‐integer nonlinear problems

Abstract

Two novel deterministic global optimization algorithms for nonconvex mixed‐integer problems (MINLPs) are proposed, using the advances of the αBB algorithm for nonconvex NLPs of Adjiman et al. The special structure mixed‐integer αBB algorithm (SMIN‐αBB) addresses problems with nonconvexities in the continuous variables and linear and mixed‐bilinear participation of the binary variables. The general structure mixed‐integer αBB algorithm (GMIN‐αBB) is applicable to a very general class of problems for which the continuous relaxation is twice continuously differentiable. Both algorithms are developed using the concepts of branch‐and‐bound, but they differ in their approach to each of the required steps. The SMIN‐αBB algorithm is based on the convex underestimation of the continuous functions, while the GMIN‐αBB algorithm is centered around the convex relaxation of the entire problem. Both algorithms rely on optimization or interval‐based variable‐bound updates to enhance efficiency. A series of medium‐size engineering applications demonstrates the performance of the algorithms. Finally, a comparison of the two algorithms on the same problems highlights the value of algorithms that can handle binary or integer variables without reformulation.