pith. sign in

arxiv: 2501.00638 · v2 · submitted 2024-12-31 · 🧮 math.OC

On the integrality gap of convex mixed-integer programs

Burak Kocuk , Diego Moran Ramirez This is my paper

Pith reviewed 2026-05-23 06:19 UTC · model grok-4.3

classification 🧮 math.OC
keywords integrality gapconvex mixed-integer programmingrecession conepolyhedral approximationDirichlet convex setsnonlinear optimizationcontinuous relaxation
0
0 comments X

The pith

Certain classes of convex sets make the integrality gap of mixed-integer programs finite, with explicit estimates supplied for two classes.

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

The paper examines when the optimal value of a convex mixed-integer program differs from the value of its continuous relaxation obtained by ignoring integrality. It identifies three classes of convex feasible regions for which this difference, called the integrality gap, remains finite: Dirichlet convex sets, sets whose recession cones are full-dimensional, and sets that admit polyhedral approximations. Explicit upper bounds on the gap are derived for the recession-cone and polyhedral-approximation cases. The paper further shows that replacing the original nonlinear set by a rational polyhedron can produce gap estimates that are arbitrarily worse than those obtained by direct analysis of the convex set.

Core claim

The paper establishes that Dirichlet convex sets, convex sets with full-dimensional recession cones, and convex sets that can be approximated by polyhedra all induce mixed-integer programs whose integrality gaps are finite. For the latter two classes, concrete estimates of the gap are provided in terms of geometric properties of the set. In addition, the paper demonstrates that any attempt to bound the gap via rational polyhedral outer approximations of the feasible region can produce arbitrarily poor results compared with bounds derived directly from the nonlinear description.

What carries the argument

The integrality gap, defined as the difference between the optimal value of the mixed-integer program and the optimal value of the continuous relaxation obtained by dropping integrality constraints on the integer variables.

If this is right

  • Mixed-integer programs whose feasible regions have full-dimensional recession cones possess finite integrality gaps whose magnitude can be estimated from the geometry of the recession cone.
  • Mixed-integer programs whose feasible regions admit polyhedral approximations possess finite integrality gaps whose magnitude can be estimated from the quality of those approximations.
  • Rational polyhedral outer approximations of a nonlinear convex set can produce integrality-gap bounds that are arbitrarily larger than the true gap.
  • Direct nonlinear analysis of the feasible region can be strictly preferable to polyhedral approximation when bounding the integrality gap.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The finite-gap results may guide the design of branch-and-bound or cutting-plane algorithms that exploit recession-cone or approximation structure to certify solution quality.
  • The observation that polyhedral approximations can degrade gap bounds suggests that nonlinear-specific techniques remain necessary even when polyhedral relaxations are computationally convenient.
  • Similar finite-gap statements might be provable for additional classes of convex sets whose recession or approximation properties lie between the three classes already treated.

Load-bearing premise

The feasible region is a convex set in Euclidean space and the continuous relaxation is formed by simply dropping the integrality restrictions on the integer variables.

What would settle it

An explicit convex set possessing a full-dimensional recession cone for which the integrality gap is infinite would falsify the finite-gap claim for that class.

read the original abstract

We study the integrality gap of convex mixed-integer programs, that is, the difference between the optimal value of such a problem and the optimal value of its continuous relaxation. We study classes of convex sets whose associated optimization problem have finite integrality gap: Dirichlet convex sets, sets with full-dimensional recession cones and sets that can be approximated by polyhedral sets. In the latter two cases, we provide estimates for the value of the integrality gap. Finally, we study the possibility of estimating the integrality gap of nonlinear convex mixed-integer programs via rational polyhedral approximations of their feasible regions and argue that, in general, such an approach may yield arbitrarily worse bounds compared to integrality gap estimations specifically derived by studying the associated nonlinear set.

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 / 2 minor

Summary. The paper studies the integrality gap of convex mixed-integer programs, defined as the difference between the optimal value of the MIP and its continuous relaxation. It identifies three classes of convex sets whose associated problems have finite integrality gaps: Dirichlet convex sets (via density arguments), sets with full-dimensional recession cones (with explicit estimates via recession-cone scaling), and sets approximable by polyhedra (with explicit estimates via uniform approximation error bounds). It further provides a counter-example family showing that Hausdorff-close rational polyhedra can produce gap estimates diverging to infinity while the true nonlinear gap remains bounded.

Significance. If the results hold, the work advances the theory of mixed-integer nonlinear optimization by supplying self-contained constructions and proofs that establish finite gaps for specific classes and demonstrate the limitations of polyhedral approximation approaches. The explicit estimates and the counter-example family constitute clear strengths.

minor comments (2)
  1. [§2] §2: The notation for the recession cone is introduced without a forward reference to the standard definition in convex analysis; a brief reminder sentence would improve readability.
  2. The statement of the main theorem on polyhedral approximability would benefit from an explicit statement of the dimension assumption used in the error-bound derivation.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their careful reading, accurate summary of the paper, and positive recommendation to accept.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The manuscript derives finite integrality gap results for three classes of convex sets via direct set-theoretic constructions and proofs (density arguments for Dirichlet sets, recession-cone scaling for full-dimensional recession cones, and uniform approximation bounds for polyhedral approximability), together with an explicit counter-example family showing divergence of polyhedral gap bounds. All steps are internal to convex geometry and do not reduce any claimed result to a fitted parameter, self-citation chain, or definitional equivalence; the central claims therefore remain independent of the paper's own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

No free parameters, invented entities, or non-standard axioms are visible in the abstract; the work relies on the standard background of convex analysis and mixed-integer programming.

axioms (1)
  • standard math Convexity of the feasible region and well-posedness of the continuous relaxation obtained by dropping integrality constraints.
    These are the background assumptions required to define the integrality gap in the abstract.

pith-pipeline@v0.9.0 · 5644 in / 1264 out tokens · 38479 ms · 2026-05-23T06:19:42.808116+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

29 extracted references · 29 canonical work pages

  1. [1]

    Aliev, M

    I. Aliev, M. Henk, and T. Oertel. Integrality gaps of integ er knapsack problems. In International Conference on Integer Programming and Combinatorial Optimization , pages 25–38. Springer, 2017

    work page 2017

  2. [2]

    Atamt¨ urk, G

    A. Atamt¨ urk, G. Berenguer, and Z. Shen. A conic integer pr ogramming approach to stochastic joint location-inventor y problems. Oper. Res., 60(2):366–381, March 2012

    work page 2012

  3. [3]

    Belotti, J

    P. Belotti, J. C. G´ oez, I. P´ olik, T. K. Ralphs, and T. Terl aky. On families of quadratic surfaces having fixed intersec tions with two hyperplanes. Discrete Applied Mathematics , 161(16-17):2778–2793, 2013

    work page 2013

  4. [4]

    Belotti, J

    P. Belotti, J. C. G´ oez, I. P´ olik, T. K. Ralphs, and T. Terl aky. A complete characterization of disjunctive conic cuts for mixed integer second order cone optimization. Discrete Optimization , 24:3–31, 2017. Conic Discrete Optimization

    work page 2017

  5. [5]

    Ben-Tal and A

    A. Ben-Tal and A. Nemirovski. Lectures on Modern Convex Optimization . Society for Industrial and Applied Mathematics, 2001

    work page 2001

  6. [6]

    Bertsimas and R

    D. Bertsimas and R. W eismantel. Optimization over integers , volume 13. Dynamic Ideas, 2005

    work page 2005

  7. [7]

    Borst, D

    S. Borst, D. Dadush, and D. Mikulincer. Integrality gaps f or random integer programs via discrepancy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms ( SODA), pages 1692–1733. SIAM, 2023

    work page 2023

  8. [8]

    Brandenberg and L

    R. Brandenberg and L. Roth. New algorithms for k-center an d extensions. In B. Yang, D. Du, and C. W ang, editors, Combinatorial Optimization and Applications , volume 5165 of Lecture Notes in Computer Science , pages 64–78. Springer Berlin Heidelberg, 2008

    work page 2008

  9. [9]

    W. Cook, A. M. H. Gerards, A. Schrijver, and ´E. Tardos. Sensitivity theorems in integer linear programm ing. Mathematical Programming, 34(3):251–264, 1986

    work page 1986

  10. [10]

    Dai and M

    R. Dai and M. Mesbahi. Optimal topology design for dynami c networks. In Decision and Control and European Control Conference (CDC-ECC), 2011 50th IEEE Conference on , pages 1280–1285, Dec 2011

    work page 2011

  11. [11]

    Del Pia and M

    A. Del Pia and M. Ma. Proximity in concave integer quadrat ic programming. Mathematical Programming, 194(1):871–900, 2022

    work page 2022

  12. [12]

    S. S. Dey and D. A. Mor´ an R. Some properties of convex hull s of integer points contained in general convex sets. Mathe- matical Programming, 141(1):507–526, Oct 2013

    work page 2013

  13. [13]

    Eisenbrand and R

    F. Eisenbrand and R. W eismantel. Proximity results and f aster algorithms for integer programming using the steinit z lemma. ACM Transactions on Algorithms (TALG) , 16(1):1–14, 2019

    work page 2019

  14. [14]

    Granot and J

    F. Granot and J. Skorin-Kapov. Some proximity and sensit ivity results in quadratic integer programming. Mathematical Programming, 47(1):259–268, 1990

    work page 1990

  15. [15]

    D. S. Hochbaum and J. G. Shanthikumar. Convex separable o ptimization is not much harder than linear optimization. Journal of the ACM (JACM) , 37(4):843–862, 1990

    work page 1990

  16. [16]

    S. E. Kayacık and B. Kocuk. An MISOCP-based solution appr oach to the reactive optimal power flow problem. IEEE Transactions on Power Systems , 36(1):529–532, 2020. 31

    work page 2020

  17. [17]

    B. Kocuk. Conic reformulations for Kullback-Leibler di vergence constrained distributionally robust optimizati on and applications. An International Journal of Optimization and Control: Theo ries & Applications , 11(2):139–151, 2021

    work page 2021

  18. [18]

    B. Kocuk. Rational polyhedral outer-approximations of the second-order cone. Discrete Optimization , 40:100643, 2021

    work page 2021

  19. [19]

    Kocuk, S

    B. Kocuk, S. S. Dey, and X. A. Sun. New formulation and stro ng MISOCP relaxations for AC optimal transmission switching problem. IEEE Transactions on Power Systems , 32(6):4161–4170, 2017

    work page 2017

  20. [20]

    Kocuk and D

    B. Kocuk and D. A. Mor´ an R. On subadditive duality for con ic mixed-integer programs. SIAM Journal on Optimization , 29(3):2320–2336, 2019

    work page 2019

  21. [21]

    J. Lee, J. Paat, I. Stallknecht, and L. Xu. Improving prox imity bounds using sparsity. In Combinatorial Optimization: 6th International Symposium, ISCO 2020, Montreal, QC, Canada, May 4–6, 2020, Revised Selected Papers 6 , pages 115–127. Springer, 2020

    work page 2020

  22. [22]

    D. A. Mor´ an R. and S. S. Dey. On maximal S-free convex sets . SIAM Journal on Discrete Mathematics , 25(1):379–393, 2011

    work page 2011

  23. [23]

    D. A. Mor´ an R., S. S. Dey, and J. P. Vielma. A strong dual fo r conic mixed-integer programs. SIAM Journal on Optimization, 22(3):1136–1150, 2012

    work page 2012

  24. [24]

    J. Paat, R. W eismantel, and S. W eltge. Distances between optimal solutions of mixed-integer programs. Mathematical Programming, 179(1):455–468, 2020

    work page 2020

  25. [25]

    M. C ¸ . Pınar. Mixed-integer second-order cone programm ing for lower hedging of American contingent claims in incom plete markets. Optimization Letters , 7(1):63–78, 2013

    work page 2013

  26. [26]

    D. A. Mor´ an R. and S. S. Dey. Closedness of integer hulls o f simple conic sets. SIAM Journal on Discrete Mathematics , 30(1):70–99, 2016

    work page 2016

  27. [27]

    Sankaranarayanan

    S. Sankaranarayanan. Best-response algorithms for int eger convex quadratic simultaneous games. arXiv preprint arXiv:2405.07119, 2024

    work page arXiv 2024

  28. [28]

    Tuncer and B

    D. Tuncer and B. Kocuk. An MISOCP-based decomposition ap proach for the unit commitment problem with AC power flows. IEEE Transactions on Power Systems , 38(4):3388–3400, 2023

    work page 2023

  29. [29]

    W erman and D

    M. W erman and D. Magagnosc. The relationship between int eger and real solutions of constrained convex programming. Mathematical Programming, 51(1):133–135, 1991. 32

    work page 1991