pith. sign in

arxiv: 2606.26897 · v1 · pith:46SP755Rnew · submitted 2026-06-25 · 🧮 math.OC

Separation, Constraint Qualifications, and Cycling in Outer Approximation

Erik Tamm , Jan Kronqvist This is my paper

Pith reviewed 2026-06-26 03:11 UTC · model grok-4.3

classification 🧮 math.OC
keywords outer approximationmixed-integer nonlinear programmingconstraint qualificationscyclingextended cutting planesseparationconvergence
0
0 comments X

The pith

Extended cutting planes allow outer approximation to converge finitely even when constraint qualifications fail at subproblem solutions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The outer approximation algorithm for convex mixed-integer nonlinear programs can fail to separate the current iterate from the feasible set if a constraint qualification does not hold at the solution of a nonlinear subproblem. This failure can cause the algorithm to cycle by repeating the same integer assignment. The paper shows that detecting such cycling and falling back to extended cutting planes, which provide valid separation even without the qualification, restores finite convergence. The result generalizes existing convergence theory by relaxing the standard assumption that a constraint qualification holds at every subproblem optimum. A sympathetic reader cares because these algorithms are used in practice, and the relaxed assumptions make the method more robust when exact solves or qualifications are hard to guarantee.

Core claim

The paper proves that when Slater's condition is nearly violated, separation can fail at a point close to the exact NLP solution. It proposes using extended cutting planes as a fallback strategy when cycling is detected in the outer approximation algorithm, and proves that this yields a finitely convergent algorithm under relaxed assumptions on constraint qualifications.

What carries the argument

Extended cutting planes generated as a fallback when cycling is detected, which remain valid separators even if standard linear cuts fail due to constraint qualification violation.

Load-bearing premise

That cycling can be reliably detected and that extended cutting planes can always be generated to provide valid separation when standard cuts fail due to constraint qualification violation.

What would settle it

An instance of a convex mixed-integer nonlinear program where cycling is detected, extended cutting planes are applied, yet the algorithm still repeats the same integer assignment without terminating after finitely many steps.

Figures

Figures reproduced from arXiv: 2606.26897 by Erik Tamm, Jan Kronqvist.

Figure 1
Figure 1. Figure 1: Illustration of Example 1. The OA cut is y ≤ 1 and the ECP cut is x + y ≤ 1.5. 4. Constraint qualification Constraint qualifications are important in optimization since they exclude de￾generate and other edge cases. A classic overview of constraint qualifications by Mangasarian can be found in [18]. This section describes common constraint qual￾ification assumptions for the OA algorithm, explains why they … view at source ↗
Figure 2
Figure 2. Figure 2: Running example with r = 1. The gradient cut at the point a does not separate (1, 1) from F. −1.5 −1 −0.5 0 0.5 1 1.5 0 1 x k (1,1) a x y [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Running example with r = 1.1. The gradient cut at the point a does separate (1, 1) from F. We conclude from Example 2 that the accuracy required for separation is not constant. In the first case, a non-exact solution was acceptable in some directions but not in others, whereas in the second case any solution up to some precision was acceptable. Note that neither Slater’s condition nor the LICQ holds when r… view at source ↗
read the original abstract

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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper examines the outer approximation algorithm for convex mixed-integer nonlinear programs, focusing on the assumptions that a constraint qualification holds at each NLP subproblem optimum and that subproblems are solved exactly. It connects failures of these assumptions to cycling (reappearance of the same integer assignment), shows that near-violation of Slater's condition implies existence of a point where separation fails, and proposes extended cutting planes as a fallback when cycling is detected. The central result is a proof that this strategy yields finite convergence under relaxed constraint-qualification assumptions, generalizing existing convergence theory.

Significance. If the proofs are correct, the work strengthens the theoretical foundation of outer approximation by relaxing a commonly tacit constraint-qualification requirement and by providing a practical safeguard (extended cuts) against cycling. The explicit link between near-Slater violation and separation failure is a useful diagnostic result for implementers. No machine-checked proofs or reproducible code are mentioned, but the derivation is presented as self-contained and parameter-free.

minor comments (3)
  1. The abstract states that high precision may be required for approximate NLP solves, but the manuscript should include a concrete example (with explicit numbers) showing the precision threshold at which separation fails.
  2. Notation for the extended cutting planes is introduced without a dedicated definition block; a short subsection or displayed equation block would improve readability when the fallback strategy is first described.
  3. The cycling-detection mechanism is described at a high level; adding a short pseudocode fragment or numbered step list would clarify exactly when the algorithm switches to extended cuts.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary and recommendation of minor revision. The assessment correctly captures the paper's focus on relaxing constraint-qualification assumptions in outer approximation and the role of extended cutting planes. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper develops a theoretical framework for the outer approximation algorithm, formalizing connections between cycling, constraint qualifications (e.g., Slater's condition), and separation failures, then proving finite convergence via extended cutting planes under relaxed assumptions. The abstract and described claims contain no fitted parameters, self-definitional reductions, or load-bearing self-citations that collapse the central result to its inputs by construction. All steps appear to rely on standard convex analysis and algorithm analysis without renaming known results or smuggling ansatzes via prior self-work. The derivation is self-contained against external mathematical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper rests on standard convexity of the MINLP and the ability to generate extended cuts; no free parameters or new entities are introduced.

axioms (1)
  • domain assumption The problems considered are convex mixed-integer nonlinear programs.
    Stated as the setting for the outer approximation algorithm throughout the abstract.

pith-pipeline@v0.9.1-grok · 5747 in / 1086 out tokens · 27732 ms · 2026-06-26T03:11:52.065655+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 12 canonical work pages

  1. [1]

    Artelys,Knitro 15.1, 2025,https://www.artelys.com/app/docs/knitro/

    2025

  2. [2]

    Belotti, C

    P. Belotti, C. Kirches, S. Leyffer, J. Linderoth, J. Luedtke, and A. Mahajan,Mixed- integer nonlinear optimization, Acta Numer.22(2013), 1–131,https://doi.org/10.1017/ S0962492913000032

    2013

  3. [3]

    Bonami, L

    P. Bonami, L. T. Biegler, A. R. Conn, G. Cornu´ ejols, I. E. Grossmann, C. D. Laird, J. Lee, A. Lodi, F. Margot, N. Sawaya, and A. W¨ achter,An algorithmic framework for convex mixed integer nonlinear programs, Discrete Optim.5(2008), no. 2, 186–204,https://doi.org/10. 1016/j.disopt.2006.10.011

    2008

  4. [4]

    M. R. Bussieck, A. S. Drud, and A. Meeraus,MINLPLib—a collection of test models for mixed-integer nonlinear programming, INFORMS J. Comput.15(2003), no. 1, 114–119, https://doi.org/10.1287/ijoc.15.1.114.15159

    work page doi:10.1287/ijoc.15.1.114.15159 2003

  5. [5]

    D’Ambrosio, J

    C. D’Ambrosio, J. Lee, and A. W¨ achter,A global-optimization algorithm for mixed-integer nonlinear programs having separable non-convexity, Algorithms - ESA 2009 (Berlin, Heidel- berg) (A. Fiat and P. Sanders, eds.), Lecture Notes in Computer Science, vol. 5757, Springer, 2009,https://doi.org/10.1007/978-3-642-04128-0_10, pp. 107–118

    work page doi:10.1007/978-3-642-04128-0_10 2009

  6. [6]

    Delfino and W

    A. Delfino and W. de Oliveira,Outer-approximation algorithms for nonsmooth convex MINLP problems, Optimization67(2018), no. 6, 797–819,https://doi.org/10.1080/02331934. 2018.1434173

    work page doi:10.1080/02331934 2018

  7. [7]

    M. A. Duran and I. E. Grossmann,An outer-approximation algorithm for a class of mixed- integer nonlinear programs, Math. Program.36(1986), no. 3, 307–339,https://doi.org/10. 1007/BF02592064

    1986

  8. [8]

    Variable metric forward–backward splitting with applications to monotone inclusions in duality

    V.-P. Eronen, M. M. M¨ akel¨ a, and T. Westerlund,On the generalization of ECP and OA methods to nonsmooth convex MINLP problems, Optimization63(2014), no. 7, 1057–1073, https://doi.org/10.1080/02331934.2012.712118

    work page doi:10.1080/02331934.2012.712118 2014

  9. [9]

    Fletcher and S

    R. Fletcher and S. Leyffer,Solving mixed integer nonlinear programs by outer approximation, Math. Program.66(1994), 327–349,https://doi.org/10.1007/BF01581153

    work page doi:10.1007/bf01581153 1994

  10. [10]

    I. E. Grossmann, J. Viswanathan, A. Vecchietti, R. Raman, and E. Kalvelagen, GAMS/DICOPT: A discrete continuous optimization package, 2003,https://www. amsterdamoptimization.com/pdf/dicopt.pdf

    2003

  11. [11]

    Hunting,The AIMMS outer approximation algorithm for MINLP, 2011, AIMMS technical report

    M. Hunting,The AIMMS outer approximation algorithm for MINLP, 2011, AIMMS technical report

    2011

  12. [12]

    Kronqvist, D

    J. Kronqvist, D. E. Bernal, and I. E. Grossmann,Using regularization and second order information in outer approximation for convex MINLP, Math. Program.180(2020), no. 1, 285–310,https://doi.org/10.1007/s10107-018-1356-3

    work page doi:10.1007/s10107-018-1356-3 2020

  13. [13]

    Kronqvist, D

    J. Kronqvist, D. E. Bernal, A. Lundell, and I. E. Grossmann,A review and comparison of solvers for convex MINLP, Optim. Eng.20(2019), no. 2, 397–455,https://doi.org/10. 1007/s11081-018-9411-8

    2019

  14. [14]

    Kronqvist, D

    J. Kronqvist, D. E. Bernal Neira, and I. E. Grossmann,50 years of mixed-integer nonlinear and disjunctive programming, Eur. J. Oper. Res.331(2025), no. 3, 687–705,https://doi. org/10.1016/j.ejor.2025.07.016

    work page doi:10.1016/j.ejor.2025.07.016 2025

  15. [15]

    Kronqvist, A

    J. Kronqvist, A. Lundell, and T. Westerlund,The extended supporting hyperplane algorithm for convex mixed-integer nonlinear programming, J. Glob. Optim.64(2016), no. 2, 249–272, https://doi.org/10.1007/s10898-015-0322-3

    work page doi:10.1007/s10898-015-0322-3 2016

  16. [16]

    Lundell, J

    A. Lundell, J. Kronqvist, and T. Westerlund,The supporting hyperplane optimization toolkit for convex MINLP, J. Glob. Optim.84(2022), no. 1, 1–41,https://doi.org/10.1007/ s10898-022-01128-0

    2022

  17. [17]

    Mahajan, S

    A. Mahajan, S. Leyffer, J. Linderoth, J. Luedtke, and T. Munson,Minotaur: A mixed- integer nonlinear optimization toolkit, Math. Program. Comput.13(2021), no. 2, 301–338, https://doi.org/10.1007/s12532-020-00196-1

    work page doi:10.1007/s12532-020-00196-1 2021

  18. [18]

    O. L. Mangasarian,Nonlinear programming, McGraw-Hill, New York, 1969

    1969

  19. [19]

    D. W. Peterson,A review of constraint qualifications in finite-dimensional spaces, SIAM Rev. 15(1973), no. 3, 639–654,https://doi.org/10.1137/1015075

    work page doi:10.1137/1015075 1973

  20. [20]

    Quesada and I

    I. Quesada and I. E. Grossmann,An LP/NLP based branch and bound algorithm for convex MINLP optimization problems, Comput. Chem. Eng.16(1992), no. 10–11, 937–947,https: //doi.org/10.1016/0098-1354(92)80028-8. 14 E. TAMM AND J. KRONQVIST

    work page doi:10.1016/0098-1354(92)80028-8 1992

  21. [21]

    Westerlund and F

    T. Westerlund and F. Pettersson,An extended cutting plane method for solving convex MINLP problems, Comput. Chem. Eng.19(1995), no. Suppl. 1, S131–S136, Proceedings of ESCAPE- 5, Bled, Slovenia, 11–14 June 1995;https://doi.org/10.1016/0098-1354(95)87027-X. SEPARATION, CQ AND CYCLING IN OA 15 Appendix Appendix A Outer approximation algorithm Algorithm 1 pr...

    work page doi:10.1016/0098-1354(95)87027-x 1995