Separation, Constraint Qualifications, and Cycling in Outer Approximation

The outer approximation algorithm is a widely used method for solving convex mixed-integer nonlinear programs.

While the algorithm is well established in theory and practice, certain assumptions underlying its convergence are rarely discussed in the literature.

In this paper, we examine two such assumptions: that a constraint qualification holds at the optimal solution of each nonlinear programming subproblem, and that these subproblems can be solved exactly.

We argue that both assumptions are connected to the issue of cycling, by which we mean that the same integer assignment reappears in successive iterations of the algorithm.

When a constraint qualification fails, separation of the current iterate from the feasible set is not guaranteed, which can cause the algorithm to stall.

When the nonlinear programming subproblem is solved only approximately, separation may likewise fail, and we show that high precision can be required in certain cases.

To formalize the connection between these issues, we prove that when Slater's condition is nearly violated, a point close to the exact solution can be found at which separation fails.

Furthermore, within the outer approximation algorithm, we propose to use extended cutting planes as a fallback strategy when cycling is detected.

We prove that this approach yields a finitely convergent algorithm under relaxed assumptions regarding constraint qualifications, thereby generalizing the convergence theory of the outer approximation algorithm.