Global optimization of mixed‐integer nonlinear problems

TLDR

Mixed‑integer αBB algorithms address nonconvexities in continuous variables and linear/mixed‑bilinear binary participation, with SMIN‑αBB tailored to such structures and GMIN‑αBB applicable to problems whose continuous relaxation is twice continuously differentiable. The study proposes two novel deterministic global optimization algorithms for nonconvex mixed‑integer problems, building on the αBB algorithm. Both algorithms use branch‑and‑bound, with SMIN‑αBB employing convex underestimation of continuous functions and GMIN‑αBB relying on convex relaxation of the entire problem, and both enhance efficiency through optimization or interval‑based variable‑bound updates. Experiments on medium‑size engineering applications show the algorithms’ performance, and a comparison on identical problems highlights the advantage of algorithms that handle binary or integer variables without reformulation.

Abstract

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.