arxiv: 2605.02305 · v1 · submitted 2026-05-04 · 🧮 math.OC

Recognition: 3 theorem links

· Lean Theorem

A computational comparison of handling distance constraints in MINLP

Christopher Hojny , Leo Liberti

Authors on Pith no claims yet

Pith reviewed 2026-05-08 18:40 UTC · model grok-4.3

classification 🧮 math.OC

keywords minimum distance constraintsMINLPbound tighteningrotation symmetryGivens rotationslexicographic constraintscomputational comparisonreverse convexity

0 comments

The pith

New bound-tightening algorithms and Givens-based symmetry separation improve MINLP performance on minimum distance constraints.

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

The paper develops new algorithms to tighten variable bounds in mixed-integer nonlinear programs containing minimum distance constraints, which are reverse-convex and therefore hard for standard solvers. It additionally introduces a practical technique for breaking rotational symmetries by separating lexicographic ordering constraints that arise from Givens rotations. A computational study then compares these new procedures against existing methods to identify the problem classes where each performs best. This work targets geometric optimization problems in which minimum distance constraints and symmetries commonly appear and slow down solution times.

Core claim

We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further introduce a practical approach for handling rotation symmetries via separation of lexicographic constraints induced by Givens rotations. In a computational study, we examine the performance of the various methods and determine the scenarios in which each approach demonstrates superiority.

What carries the argument

Bound-tightening procedures for reverse-convex minimum distance constraints combined with separation of lexicographic constraints generated by Givens rotations to break rotational symmetries.

Load-bearing premise

The test instances chosen for the computational study are representative of the broader class of minimum distance constraint problems and the new procedures produce measurable improvements over baselines.

What would settle it

Executing the computational experiments on the paper's test set and observing no scenario in which the new bound-tightening or Givens-based symmetry methods outperform existing approaches would falsify the reported superiority claims.

Figures

Figures reproduced from arXiv: 2605.02305 by Christopher Hojny, Leo Liberti.

**Figure 1.** Figure 1: Illustration of the method by Locatelli and Raber to generate convex domains view at source ↗

**Figure 2.** Figure 2: Illustration of the three different cases of Proposition view at source ↗

**Figure 3.** Figure 3: Illustration of domain reductions derived via cutting planes and two minDCs. view at source ↗

**Figure 4.** Figure 4: Performance profiles for the MINLP test set. view at source ↗

**Figure 5.** Figure 5: Performance profiles for OFL test set. Results for GEOM. The GEOM test set consists of 2- and 3-dimensional versions of the following problems. Finding the maximum radius such that n identical spheres fit into a sphere of radius 1, and finding the maximum radius such that the kissing number problem for n spheres has a solution. For the former, we adapt the MINLP model (1) from [10] for packing spheres int… view at source ↗

**Figure 6.** Figure 6: Performance profiles for GEOM test set. the solution process. For the more difficult instances, however, heur 0 pair 0 performs worse than heur 1 pair 0. In this regime, a larger branch-and-bound tree must be explored, and it becomes more important to use an inexpensive domain reduction algorithm. Since the performance profiles do not allow to assess the overall running time, we also present some numbers t… view at source ↗

read the original abstract

Minimum distance constraints (minDCs) appear in many geometric optimization problems. They pose major challenges for mixed-integer nonlinear programming (MINLP) due to their reverse-convexity. We develop new algorithms for tightening variable bounds in general MINLPs with minDCs. Because many such problems exhibit substantial symmetry, we further introduce a practical approach for handling rotation symmetries via separation of lexicographic constraints induced by Givens rotations. In a computational study, we examine the performance of the various methods and determine the scenarios in which each approach demonstrates superiority.

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.

Desk Editor's Note private letter to a colleague

The paper adds targeted bound tightening for minDC MINLPs and a Givens-rotation method for rotational symmetry, but the computational claims rest on unexamined instance selection.

read the letter

The two things to take away are the bound-tightening procedures built specifically for minimum distance constraints and the use of Givens rotations to produce separable lexicographic symmetry breakers. Both target real pain points in geometric MINLPs where reverse-convexity and continuous symmetries slow solvers down. The paper frames these as new and shows how they fit into standard MINLP preprocessing pipelines. That is the concrete engineering contribution. The computational study then compares the new routines against baselines and tries to identify which approach wins in which settings. That kind of head-to-head testing is what practitioners need when they decide whether to add a new preprocessor step. The work stays grounded in the structure of the constraints rather than offering another generic solver tweak. The main soft spot is the test set. The abstract claims the study reveals clear superiority scenarios, yet nothing is said about how the instances were chosen or how well they sample varying numbers of distance constraints, different symmetry group sizes, or different MINLP structures. If the problems cluster in one application domain or share similar scales, the observed performance differences could be tied to that slice rather than general properties of the methods. A referee would need to see the instance generation details and some sensitivity checks before the superiority claims can be taken as reliable guidance. This paper is for people who solve geometric MINLPs and want better preprocessing tools. A reader already working on distance-constrained problems will find usable algorithmic ideas and a comparison to benchmark against. It is not a broad theoretical advance, but the ideas are specific enough and the claims are falsifiable enough that it deserves a serious referee rather than a desk reject. I would send it to review and ask the authors to document the test-set construction and run a few additional instances that stress different symmetry and scale regimes.

Referee Report

1 major / 1 minor

Summary. The manuscript develops new algorithms for tightening variable bounds in general MINLPs subject to minimum distance constraints (minDCs), which are reverse-convex. It further proposes a symmetry-breaking technique that separates lexicographic constraints induced by Givens rotations to handle rotational symmetries. The central contribution is a computational study that compares the new methods against existing approaches and identifies the scenarios in which each demonstrates superiority.

Significance. If the computational results hold and the test instances are representative, the work would supply practical, general-purpose tools for improving bound quality and symmetry handling in geometrically constrained MINLPs. Such techniques could accelerate solution of packing, embedding, and configuration problems that arise across applications. The paper's focus on algorithmic generality rather than a single application domain is a positive feature.

major comments (1)

[Section 5 (Computational Study)] Section 5 (Computational Study): The claim that the study determines the scenarios in which each approach demonstrates superiority is load-bearing for the paper's conclusions. This requires the test set to adequately sample variation in the number of minDCs, geometric embeddings, symmetry group sizes, and MINLP structures. The manuscript does not provide sufficient detail on instance generation or diversity metrics to establish that the observed performance differences are not artifacts of a narrow slice of the problem class.

minor comments (1)

[Abstract] Abstract: A brief indication of the number of instances, the MINLP solver employed, and the range of problem sizes would help readers immediately gauge the scope of the empirical evaluation.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thorough review and constructive feedback on our manuscript. We are pleased that the referee recognizes the potential practical value of our algorithms for bound tightening and symmetry handling in MINLPs with minimum distance constraints. Below, we address the major comment point by point.

read point-by-point responses

Referee: Section 5 (Computational Study): The claim that the study determines the scenarios in which each approach demonstrates superiority is load-bearing for the paper's conclusions. This requires the test set to adequately sample variation in the number of minDCs, geometric embeddings, symmetry group sizes, and MINLP structures. The manuscript does not provide sufficient detail on instance generation or diversity metrics to establish that the observed performance differences are not artifacts of a narrow slice of the problem class.

Authors: We agree that additional details on instance generation and diversity are needed to fully substantiate the claim that our computational study identifies the scenarios of superiority for each method. In the revised manuscript, we will expand Section 5 with a dedicated subsection on test-set construction. This will explicitly describe the generation procedure, including the ranges and sampling strategy for the number of minDCs, the variety of geometric embeddings considered (e.g., different dimensions and object shapes), the sizes of the rotational symmetry groups, and the range of MINLP structures (objectives and auxiliary constraints). We will also include quantitative diversity metrics such as distributions of problem size, constraint density, and symmetry order. These additions will demonstrate that the test set spans a representative portion of the problem class and thereby support the observed performance distinctions. revision: yes

Circularity Check

0 steps flagged

No circularity: algorithmic construction plus empirical comparison on test instances

full rationale

The paper develops new bound-tightening algorithms for general MINLPs containing minimum-distance constraints and introduces a Givens-rotation-based lexicographic symmetry-separation method, then evaluates them via computational experiments. No equations, fitted parameters, or predictions are presented that reduce by construction to the inputs (no self-definitional relations, no fitted-input-called-prediction pattern). The central claims rest on explicit algorithmic descriptions and observed performance differences on the chosen instances rather than on any self-citation chain or uniqueness theorem imported from prior work by the same authors. The derivation chain is therefore self-contained.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract-only review; no free parameters, axioms, or invented entities are stated. The work relies on standard MINLP modeling assumptions that are not enumerated.

pith-pipeline@v0.9.0 · 5373 in / 1087 out tokens · 58649 ms · 2026-05-08T18:40:09.701392+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

Foundation/AlexanderDuality.lean (alexander_duality_circle_linking) SphereAdmitsCircleLinking D ↔ D = 3 unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

sphere packing problem, kissing number problem, obnoxious facility location problem ... d∈{1,...,5} for MINLP, d=2 for OFL, d∈{2,3} for GEOM

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

24 extracted references · 2 canonical work pages

[1]

Anders, P

M. Anders, P. Schweitzer, and J. Stieß. Engineering a Preprocessor for Symmetry Detection. In L. Georgiadis, editor,21st International Symposium on Experimental Algorithms (SEA 2023), volume 265 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 1:1– 1:21, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum f¨ ur Informatik. 10

2023
[2]

Bussieck, A

M. Bussieck, A. Drud, and A. Meeraus. MINLPLib — A collection of test models for mixed- integer nonlinear programming.INFORMS Journal on Computing, 15(1), 2003

2003
[3]

A. Costa. Valid constraints for the point packing in a square problem.Discrete Applied Mathematics, 161(18):2901–2909, 2013

2013
[4]

Costa, P

A. Costa, P. Hansen, and L. Liberti. On the impact of symmetry-breaking constraints on spatial branch-and-bound for circle packing in a square.Discrete Applied Mathematics, 161:96– 106, 2013

2013
[5]

E. D. Dolan and J. J. Mor´ e. Benchmarking optimization software with performance profiles. Mathematical Programming, 91:201–213, 2002

2002
[6]

C. Hojny. Detecting and handling reflection symmetries in mixed-integer (nonlinear) pro- gramming and beyond.Mathematical Programming Computation, 18:31–78, 2025

2025
[7]

The SCIP optimization suite 10.0.arXiv preprint arXiv:2511.18580, 2025

C. Hojny, M. Besan¸ con, K. Bestuzheva, S. Borst, J. Dion´ ısio, J. Ehls, L. Eifler, M. Ghannam, A. Gleixner, A. G¨ oß, A. Hoen, J. von Holly-Ponientzietz, R. van der Hulst, D. Kamp, T. Koch, K. Kofler, J. Lentz, M. L¨ ubbecke, S. J. Maher, P. M. Meinhold, G. Mexi, T. Mohr, E. M¨ uhmer, K. K. Patel, M. E. Pfetsch, S. Pokutta, C. R. Groba, F. Serrano, Y. S...

work page arXiv 2025
[8]

A computational comparison of handling distance constraints in MINLP

C. Hojny and L. Liberti. Online supplement for “A computational comparison of handling distance constraints in MINLP”. https://www.doi.org/10.5281/zenodo.20019823

work page doi:10.5281/zenodo.20019823
[9]

Kaibel and M

V. Kaibel and M. E. Pfetsch. Packing and partitioning orbitopes.Mathematical Programming, 114(1):1–36, 2008

2008
[10]

Khajavirad

A. Khajavirad. The circle packing problem: A theoretical comparison of various convexifica- tion techniques.Operations Research Letters, 57:107197, 2024

2024
[11]

Kucherenko, P

S. Kucherenko, P. Belotti, L. Liberti, and N. Maculan. New formulations for the kissing number problem.Discrete Applied Mathematics, 155(14):1837–1841, 2007

2007
[12]

Kusnetsov and N

A. Kusnetsov and N. V. Sahinidis. Simultaneous convexification for the planar obnoxious facility location problem.Journal of Global Optimization, 92:1–20, 2025

2025
[13]

Lai, J.-K

X. Lai, J.-K. Hao, D. Yue, Z. L¨ u, and Z.-H. Fu. Iterated dynamic thresholding search for packing equal circles into a circular container.European Journal of Operational Research, 299(1):137–153, 2022

2022
[14]

L. Liberti. Symmetry in mathematical programming. In J. Lee and S. Leyffer, editors,Mixed Integer Nonlinear Programming, volume 154 ofIMA Series, pages 263–286. Springer, New York, 2012

2012
[15]

Locatelli and U

M. Locatelli and U. Raber. Packing equal circles in a square: a deterministic global optimiza- tion approach.Discrete Applied Mathematics, 122(1):139–166, 2002

2002
[16]

F. Margot. Pruning by isomorphism in branch-and-cut.Mathematical Programming, 94(1):71– 90, 2002

2002
[17]

F. Margot. Symmetry in integer linear programming. In M. J¨ unger, T. M. Liebling, D. Naddef, G. L. Nemhauser, W. R. Pulleyblank, G. Reinelt, G. Rinaldi, and L. A. Wolsey, editors,50 Years of Integer Programming, pages 647–686. Springer, 2010

2010
[18]

M. C. Mark´ ot and T. A. Csendes. A reliable area reduction technique for solving circle packing problems.Computing, 77:147–162, 2006

2006
[19]

B. D. McKay and A. Piperno. Practical graph isomorphism, II.Journal of Symbolic Compu- tation, 60:94–112, 2014. 11

2014
[20]

Ostrowski, J

J. Ostrowski, J. Linderoth, F. Rossi, and S. Smriglio. Orbital branching.Mathematical Programming, 126(1):147–178, 2011

2011
[21]

M. E. Pfetsch and T. Rehn. A computational comparison of symmetry handling methods for mixed integer programs.Mathematical Programming Computation, 11(1):37–93, 2019

2019
[22]

van Doornmalen and C

J. van Doornmalen and C. Hojny. A unified framework for symmetry handling.Mathematical Programming, 212:217–271, 2025

2025
[23]

W¨ achter and L

A. W¨ achter and L. T. Biegler. On the implementation of an interior-point filter line-search al- gorithm for large-scale nonlinear programming.Mathematical Programming, 106:25–57, 2006

2006
[24]

Wang and C

A. Wang and C. E. Gounaris. On tackling reverse convex constraints for non-overlapping of unequal circles.Journal of Global Optimization, 80:357–385, 2021. 12

2021