Pith. sign in

REVIEW 4 major objections 6 minor 30 references

A Distance Metric for Mixed Integer Programming Instances

T0 review · 4 major / 6 minor · reviewed 2026-08-06 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read This paper introduces a distance metric for mixed-integer linear programs, computed directly from the formulation with no training, and shows it groups same-class instances about as well as a supervised graph neural network.

desk verdict A clean, training-free MILP distance metric with solid metric proofs and useful empirical results, but the coarse normalized representation makes it a metric on a quotient space, and the 'first' claim is overstated. read the letter →

arxiv 2507.11063 v1 pith:665RTU5A submitted 2025-07-15 cs.LG math.OC

Gwen Maudet , Grégoire Danoy This is my paper
classification cs.LGmath.OC
keywords mixed-integerlinearprogrammingdistancemetricEarthmover'sinstancesimilarityunsupervisedlearningStrIPLIBconstraintclassificationoptimaltransport
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper seeks to make the space of mixed-integer linear programs measurable: it defines a distance between two MILP instances that is computed from the instances' mathematical formulations alone, with no training and no class labels. Variables are bucketed into binary/integer/continuous, weights into $\{-1,1,\text{other}\}$, and right-hand sides into $\{0,1,\text{other}\}$; each constraint becomes a distribution over weight-variable pair classes, and each instance becomes a distribution over its distinct constraint types. The distance between two instances is then the Earth mover's distance between those distributions, plus a weighted penalty for objective-function differences, and the paper proves this satisfies the axioms of a mathematical distance. On the StrIPLIB benchmark, the metric groups same-class instances about as well as a supervised graph neural network (mean top-40 accuracy 73% versus 83% on classes, 77% versus 76% on subclasses) while outperforming feature-based and image-based baselines. A greedy approximation is nearly 200 times faster than the exact Earth mover's computation and matches its accuracy on 17 of 19 classes.

What carries the argument

The load-bearing object is the normalized instance representation: variables are classified as binary, integer, or continuous; weights as $-1$, $1$, or a residual class; and right-hand sides as $0$, $1$, or a residual class, giving at most nine weight-variable pair types per constraint. A constraint is a vector of proportions over these pair types, and an instance is a vector of proportions over its distinct constraint types plus an objective-function constraint. The argument works by showing that comparing such proportion vectors via Earth mover's distance (Wasserstein distance), which minimizes the product of proportions transferred times a discrete cost $d_{w,v}$, obeys the metric axioms, with parameters $\alpha,\beta,\gamma,\zeta$ weighting weight, variable, right-hand-side, and objective mismatches. The greedy variant replaces exact optimal transport by iteratively matching the closest remaining pairs, which preserves near-identical accuracy at roughly a 200x speedup.

What would settle it

Compute exact values of $d_P$ on a large sample of triples from StrIPLIB and check whether the triangle inequality ever fails; one violation would disprove Theorem 3. Alternatively, build two instances whose only difference is a uniform scaling of all coefficients by a large factor, which falls inside the residual classes and therefore yields $d_P = 0$ despite different feasible regions, showing the metric cannot separate some structurally different instances.

Watch

Extended reading notes

Core claim

The central claim is that a MILP instance can be represented without its size: repeat weight-variable pairs inside a constraint are replaced by their proportions, and repeated identical constraints are replaced by their proportions in the instance. With that normalized representation, the paper defines a distance between weight-variable pairs, a distance between constraints as the minimal transport of pair-proportions under that pair metric, and a distance between instances as the minimal transport of constraint-proportions under the constraint metric, each with additive penalties for mismatched right-hand sides and, at instance level, for objective functions. Theorems 1, 2, and 3 establish respectively that the pair distance $d_{w,v}$, the constraint distance $d_c$, and the instance distance $d_P$ are genuine mathematical distances. Empirically, each removed component degrades class identification, and the full greedy metric achieves top-40 accuracy comparable to a supervised graph neural network across 19 StrIPLIB classes and 11 subclasses.

Load-bearing premise

The metric's discriminative power rests on the coarse buckets: any weight other than $-1$ or $1$ and any right-hand side other than $0$ or $1$ is treated as a single residual class, so the metric assumes those values are structurally interchangeable and cannot detect differences of orders of magnitude between them.

Editorial extensions

If this is right

  • Benchmark compilers can select instance sets with a specified level of heterogeneity by computing pairwise $d_P$ directly from formulations, without needing labels or trained embeddings.
  • Machine-learning pipelines for MILP can build training pools as distance-based neighborhoods of a target instance, and because the metric is training-free the pool can be recomputed for each new instance.
  • Unlabeled or sparsely labeled instances can be assigned to known problem classes by nearest-neighbor under $d_P$, since the distance uses only the formulation.
  • The greedy algorithm's speed brings distance-based clustering within reach for libraries of tens of thousands of instances, of the scale of StrIPLIB.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The authors do not test whether the metric's geometry aligns with solver behavior; a natural check is whether runtime differences, branching difficulty, or cut selection difficulty are monotone in $d_P$, which would turn the metric into a practical transfer-learning tool.
  • Because the weight and right-hand-side buckets are fitted to coefficient frequencies in MIPLIB 2017, an untested consequence is that the residual classes may hide meaningful differences on instance sets with wide dynamic ranges; finer buckets or scaled features could change the learned geometry.
  • The authors stop at validating the distance, not at partitioning the MILP space; clustering all of StrIPLIB with this metric and comparing the clusters to the library's own hierarchy would test how much of the known structure the formulation-only distance rediscovers.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

4 major / 6 minor

Summary. The paper proposes a training-free distance metric for mixed-integer linear programming (MILP) instances, built from a normalized representation that discretizes variables, weights, and right-hand sides into coarse classes. The metric compares constraints and whole instances via Earth Mover's Distance, with additional penalty terms for objective-function differences. The authors prove that the construction satisfies the axioms of a metric on the normalized representation (Theorems 1–3) and evaluate both an exact and a greedy variant on the StrIPLIB benchmark, reporting that the unsupervised method outperforms feature- and image-based baselines and rivals a supervised GNN on class and subclass grouping tasks.

Significance. If the proposed distance is accepted as a meaningful structural similarity measure, it would provide a principled, training-free tool for quantifying heterogeneity in MILP instance sets and for guiding ML-MILP generalization. The paper's strengths include a clear EMD-based formulation, public code, a sensitivity analysis of each metric component, and a substantial experimental comparison. However, the central claim of a metric 'derived directly from their mathematical formulations' is weakened by the coarse discretization, which collapses coefficient magnitudes and constraint arity; the empirical results therefore validate a distance on a normalized quotient rather than on the original MILP space. The paper also contains a factual misreporting of one of its main experimental results and omits proofs for its central theorems. These issues are consequential but addressable.

major comments (4)
  1. [§3.2, §3.4, Eq. (2)–(5)] The discretization in Section 3.2 collapses all weights outside {-1,1} into a single residual class and all RHS values outside {0,1} into another, and Section 3.3 normalizes each constraint by its number of variables. Consequently, constraints such as x ≤ 1 and Σ_{j=1}^{1000} x_j ≤ 1 have identical normalized representations, and instances differing only in coefficient magnitudes can receive zero distance. The paper acknowledges this in Section 3.4, but the abstract and introduction claim a distance 'derived directly from their mathematical formulations' that identifies structurally similar instances. As stated, the distance is a metric on a coarse quotient of the MILP space, not on the original instances. Please either provide evidence that the metric is robust to these collapses (e.g., synthetic instances with scaled coefficients or varied arity) or revise the claims to make explicit that the distance operates on a normalized, discretized representation.
  2. [§4.1, Table 2] The text states that 'Comparing the greedy version (∅) to the exact formulation (∅E), results are identical in 17 out of 19 classes.' This is contradicted by Table 2, which shows differences in at least seven classes (clp, cpm, cut, cwl, lot, map, pcp). This misreporting directly affects the paper's claim that the greedy variant achieves nearly identical accuracy to the exact formulation; please correct the text or the table.
  3. [§3.2, §4] The class definitions for weights and right-hand sides are derived from MIPLIB 2017 and then applied to StrIPLIB without quantitative evidence of distributional similarity. The paper states that 'Similar patterns are observed in the strIPLIB instances used for evaluation' but provides no data. This is a potential dataset-specific fitting issue: if StrIPLIB has a different frequency of singleton values, the chosen classes may not be appropriate. Please report the class frequencies in StrIPLIB and discuss the robustness of the chosen singletons.
  4. [§3.4, Theorems 1–3] Theorems 1–3 are stated without proofs. While the metric properties of EMD are standard, the specific combinations in Eq. (4) and Eq. (5) — in particular the addition of the γ and ζ terms and the nested EMD structure — require a rigorous demonstration, especially of the triangle inequality for dP. Please include full proofs or provide a reference to a complete derivation.
minor comments (6)
  1. [§2.2] The word 'appraoch' should be 'approach' in the phrase 'classification appraoch'.
  2. [§3.4] The word 'simiarity' should be 'similarity'.
  3. [Throughout] The capitalization of the dataset name is inconsistent: 'StrIPLIB', 'strIPLIB', and 'strIPlib' all appear; please standardize.
  4. [Table 1 caption] The notation 'denoted as ex = 10x' is unclear; please clarify how the proportional occurrences are represented.
  5. [§3.5] The greedy heuristic is described as iteratively matching the closest pairs, but no approximation guarantee is given. A brief comment on why this greedy approach is empirically acceptable would strengthen the presentation.
  6. [Abstract, §1] The claim of being 'the first mathematical distance metric for MILP instances' is strong; prior feature-based methods (e.g., MIPLIB 2017) also define a distance on a feature space. Please qualify the claim to focus on distances derived directly from the mathematical formulation.

Circularity Check

0 steps flagged · score 1.0 of 10

No meaningful circularity: the metric is defined axiomatically, its parameters are fixed (not fitted), and the only self-citation is contextual and non-load-bearing.

full rationale

The paper's central derivation is self-contained. The distance functions in Eqs. (3), (4), and (5) are defined directly from a normalized representation, and Theorems 1-3 are proven by standard metric arguments (discrete metric plus Wasserstein/EMD combination). The parameters alpha, beta, gamma, and zeta are not fitted to data; the default configuration sets them all to 1, and the reported ablations merely disable components. The only data-derived design choice is the empirical singleton classification of weights and right-hand sides, taken from MIPLIB 2017 and disclosed in Section 3.2 and again in Section 4 ('some modeling choices in our distance formulation—such as the categorization of weights and right-hand sides—are derived from empirical observations on MIPLIB instances'). This is an input to the metric, not a quantity predicted or fitted by it; the evaluation on StrIPLIB uses external class labels as ground truth, so the empirical claim does not reduce to the construction. The acknowledged limitation in Section 3.4 (a single-variable constraint can be at zero distance from a repeated-variable constraint) concerns the metric's discriminative power on coarse discretization, which is a correctness/quality concern, not circularity. The sole self-citation, [11] (Maudet and Danoy, 2024), is cited only as an example of ML-MILP evaluation practice and does not support any theorem or design choice; it is not load-bearing. Therefore the paper contains no self-justifying reduction, no fitted parameter renamed as a prediction, and no imported uniqueness argument from the authors' prior work.

Assumptions & free parameters 4 free parameters · 4 assumptions · 0 invented entities

The central claim rests on a small set of hand-set or data-derived parameters: the singleton classes for weights and RHS, the four metric weights, and the choice of three classes per feature. No new physical or mathematical entities are introduced. The main domain assumption is that the normalized histogram representation captures the structural essence of an instance, which the paper itself admits is lossy.

free parameters (4)
  • weight singleton classes {-1, 1} = -1 and 1
    Chosen from empirical frequency in MIPLIB 2017 (Section 3.2); all other weights collapsed to residual class.
  • RHS singleton classes {0, 1} = 0 and 1
    Chosen from empirical frequency in MIPLIB 2017 (Section 3.2).
  • alpha, beta, gamma, zeta = 1, 1, 1, 1
    Hand-set to 1 in the baseline (Section 4); sensitivity analysis toggles them but does not tune them.
  • number of classes per feature = 3
    Design choice to balance informativeness vs. comparability (Section 3.2).
assumptions (4)
  • domain assumption The normalized representation (proportions of weight-variable pairs and constraint proportions) is a sufficient structural summary of a MILP instance.
    Section 3.3 defines the representation; the lossiness is acknowledged in Section 3.4.
  • standard math The ground distance dw,v is a metric on C(w) x C(v).
    It is a weighted Hamming distance; used in Theorem 1.
  • standard math The Earth Mover's Distance on probability distributions over a metric space is a metric.
    Invoked via Villani [25] and Rubner et al. [16]; standard result.
  • domain assumption StrIPLIB class labels are a meaningful ground truth for structural similarity.
    Evaluation relies on these labels; the paper itself notes classes are not mutually exclusive (Section 2.2).

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Distance Metric for Mixed Integer Programming Instances." pith.science (2026). https://pith.science/paper/665RTU5A

@misc{pith2026250711063,
  author       = {Pith},
  title        = {Pith review of: A Distance Metric for Mixed Integer Programming Instances},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/665RTU5A}},
  note         = {Machine review of arXiv:2507.11063}
}
read the original abstract

Mixed-integer linear programming (MILP) is a powerful tool for addressing a wide range of real-world problems, but it lacks a clear structure for comparing instances. A reliable similarity metric could establish meaningful relationships between instances, enabling more effective evaluation of instance set heterogeneity and providing better guidance to solvers, particularly when machine learning is involved. Existing similarity metrics often lack precision in identifying instance classes or rely heavily on labeled data, which limits their applicability and generalization. To bridge this gap, this paper introduces the first mathematical distance metric for MILP instances, derived directly from their mathematical formulations. By discretizing right-hand sides, weights, and variables into classes, the proposed metric draws inspiration from the Earth mover's distance to quantify mismatches in weight-variable distributions for constraint comparisons. This approach naturally extends to enable instance-level comparisons. We evaluate both an exact and a greedy variant of our metric under various parameter settings, using the StrIPLIB dataset. Results show that all components of the metric contribute to class identification, and that the greedy version achieves accuracy nearly identical to the exact formulation while being nearly 200 times faster. Compared to state-of-the-art baselines, including feature-based, image-based, and neural network models, our unsupervised method consistently outperforms all non-learned approaches and rivals the performance of a supervised classifier on class and subclass grouping tasks.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

30 extracted references · 18 canonical work pages

  1. [1]

    Archetti, L

    C. Archetti, L. Peirano, and M. G. Speranza. Optimization in multi- modal freight transportation problems: A Survey. European Journal of Operational Research , 299(1):1–20, May 2022. ISSN 0377-2217. doi: 10.1016/j.ejor.2021.07.031. URL https://www.sciencedirect.com/ science/article/pii/S0377221721006263

    doi:10.1016/j.ejor.2021.07.031 2022

  2. [2]

    Ausiello, A

    G. Ausiello, A. D’Atri, and M. Protasi. On the structure of combinato- rial problems and structure preserving reductions. In A. Salomaa and M. Steinby, editors,Automata, Languages and Programming, pages 45– 60, Berlin, Heidelberg, 1977. Springer. ISBN 978-3-540-37305-6. doi: 10.1007/3-540-08342-1_4

    work page doi:10.1007/3-540-08342-1_4 1977

  3. [3]

    Bastubbe, A

    M. Bastubbe, A. Helber, L. Kirchhart, M. L{\"u}bbecke, N. Rieken, and J. Witt. strIPlib: Structured Integer Programming Library, 2025. URL https://striplib.or.rwth-aachen.de

    work page 2025

  4. [4]

    Bengio, A

    Y . Bengio, A. Lodi, and A. Prouvost. Machine Learning for Combinato- rial Optimization: a Methodological Tour d’Horizon.European Journal of Operational Research, 2021. URL http://arxiv.org/abs/1811.06128. arXiv:1811.06128 [cs, stat]

    arXiv 2021

  5. [5]

    Cappart, D

    Q. Cappart, D. Chételat, E. Khalil, A. Lodi, C. Morris, and P. Veliˇckovi´c. Combinatorial optimization and reasoning with graph neural networks. Journal of machine learning research , 2023. URL http://arxiv.org/abs/2102.09544. arXiv:2102.09544 [cs, math, stat]

    arXiv 2023

  6. [6]

    Gasse, D

    M. Gasse, D. Chetelat, N. Ferroni, L. Charlin, and A. Lodi. Exact Com- binatorial Optimization with Graph Convolutional Neural Networks. In NeurIPS, 2019

    work page 2019

  7. [7]

    Gleixner, G

    A. Gleixner, G. Hendel, G. Gamrath, T. Achterberg, M. Bas- tubbe, T. Berthold, P. Christophel, K. Jarck, T. Koch, J. Linderoth, M. Lübbecke, H. D. Mittelmann, D. Ozyurt, T. K. Ralphs, D. Sal- vagnin, and Y . Shinano. MIPLIB 2017: data-driven compilation of the 6th mixed-integer programming library. Mathematical Pro- gramming Computation , 13(3):443–490, S...

    work page 2017

  8. [8]

    H. He, H. Daume III, and J. M. Eisner. Learning to Search in Branch and Bound Algorithms. In Advances in Neural In- formation Processing Systems , volume 27. Curran Associates, Inc.,

    work page

Show all 30 references
  1. [9]

    A. G. Labassi, D. Chételat, and A. Lodi. Learning to Compare Nodes in Branch and Bound with Graph Neural Networks. NeurIPS, 2022

    2022

  2. [10]

    Lodi and G

    A. Lodi and G. Zarpellon. On learning and branching: a survey. TOP, 25(2):207–236, July 2017. ISSN 1863-8279. doi: 10.1007/s11750-017-0451-6. URL https://doi.org/10.1007/ s11750-017-0451-6

    2017 doi

  3. [11]

    Maudet and G

    G. Maudet and G. Danoy. Search Strategy Generation for Branch and Bound Using Genetic Programming, Dec. 2024. URL http://arxiv.org/ abs/2412.09444. arXiv:2412.09444 [cs]

    2024 arXiv

  4. [12]

    V . Nair, K. Dvijotham, I. Dunning, and O. Vinyals. Learning Fast Opti- mizers for Contextual Stochastic Integer Programs. In AAAI, 2018

    2018

  5. [13]

    J. Orlin. A faster strongly polynomial minimum cost flow algorithm. In Proceedings of the twentieth annual ACM symposium on Theory of com- puting, STOC ’88, pages 377–387, New York, NY , USA, Jan. 1988. As- sociation for Computing Machinery. ISBN 978-0-89791-264-8. doi: 10. 11...

    1988

  6. [14]

    Papadimitriou and M

    C. Papadimitriou and M. Yannakakis. Optimization, approximation, and complexity classes. In Proceedings of the twentieth annual ACM symposium on Theory of computing , STOC ’88, pages 229–234, New York, NY , USA, Jan. 1988. Association for Computing Machinery. ISBN 978-0-89791-...

    1988

  7. [15]

    Paulus and A

    M. Paulus and A. Krause. Learning To Dive In Branch And Bound. Advances in Neural Information Processing Systems, 36:34260–34277, Dec. 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/ hash/6bbda0824bcc20749f21510fd8b28de5-Abstract-Conference. html

    2023

  8. [16]

    Rubner, C

    Y . Rubner, C. Tomasi, and L. J. Guibas. The Earth Mover’s Distance as a Metric for Image Retrieval. International Journal of Computer Vision, 40(2):99–121, Nov. 2000. ISSN 1573-1405. doi: 10.1023/A: 1026543900054. URL https://doi.org/10.1023/A:1026543900054

    doi

  9. [17]

    Scavuzzo, K

    L. Scavuzzo, K. Aardal, A. Lodi, and N. Yorke-Smith. Machine learn- ing augmented branch and bound for mixed integer linear programming. Mathematical Programming, Aug. 2024. ISSN 0025-5610, 1436-4646. doi: 10.1007/s10107-024-02130-y. URL https://link.springer.com/10. 1007/s101...

    2024 doi

  10. [18]

    Shafaghsorkh and A

    O. Shafaghsorkh and A. Ayough. Application of soft operations re- search methods in healthcare: A systematic review. Journal of Indus- trial Engineering and Management Studies , 9(1):136–147, July 2022. ISSN 2476-308X. doi: 10.22116/jiems.2022.335541.1483. URL https: //jiems.i...

    2022

  11. [19]

    Steever, C

    Z. Steever, C. Murray, J. Yuan, M. Karwan, and M. Lübbecke. An Image-Based Approach to Detecting Structural Similarity Among Mixed Integer Programs. INFORMS Journal on Computing, Mar. 2022. doi: 10.1287/ijoc.2021.1117. URL https://pubsonline.informs.org/doi/ abs/10.1287/ijoc.2...

    2022

  12. [21]

    Y . Tang, S. Agrawal, and Y . Faenza. Reinforcement Learning for Integer Programming: Learning to Cut. In nternational Conference on Machine Learning, 2020

    2020

  13. [22]

    Thuerck, B

    D. Thuerck, B. Sofranac, M. E. Pfetsch, and S. Pokutta. Learn- ing Cuts via Enumeration Oracles. Advances in Neural In- formation Processing Systems , 36:79108–79123, Dec. 2023. URL https://proceedings.neurips.cc/paper_files/paper/2023/hash/ fa0126bb7ebad258bf4ffdbbac2dd787-Ab...

    2023

  14. [23]

    Tiwari, P

    A. Tiwari, P. N. Hoyos, W. Hutabarat, C. Turner, N. Ince, X.-P. Gan, and N. Prajapat. Survey on the use of computational optimisation in UK engineering companies. CIRP Journal of Manufacturing Science and Technology, 9:57–68, May 2015. ISSN 1755-5817. doi: 10.1016/j. cirpj.201...

    2015 doi

  15. [24]

    Turner, T

    M. Turner, T. Koch, F. Serrano, and M. Winkler. Adaptive Cut Selection in Mixed-Integer Linear Programming. Open Journal of Mathematical Optimization, 4:1–28, 2023. ISSN 2777-5860. doi: 10.5802/ojmo.25. URL https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.25/

    2023 doi

  16. [25]

    C. Villani. The Wasserstein distances. In M. Berger, B. Eckmann, P. De La Harpe, F. Hirzebruch, N. Hitchin, L. Hörmander, A. Kupi- ainen, G. Lebeau, M. Ratner, D. Serre, Y . G. Sinai, N. J. A. Sloane, A. M. Vershik, and M. Waldschmidt, editors, Optimal Transport, vol- ume 338,...

    2009

  17. [26]

    I. H. Witten, E. Frank, and M. A. Hall. Data mining: practical machine learning tools and techniques . Morgan Kaufmann series in data man- agement systems. Morgan Kaufmann, Burlington, MA, 3rd ed edition,

  18. [27]

    Zhang, C

    J. Zhang, C. Liu, X. Li, H.-L. Zhen, M. Yuan, Y . Li, and J. Yan. A survey for solving mixed integer programming via machine learning. Neurocomputing, 519:205–217, Jan. 2023. ISSN 0925-2312. doi: 10.1016/j.neucom.2022.11.024. URL https://www.sciencedirect.com/ science/article/...

    2023 doi

  19. [2011]

    ISBN 978-0-12-374856-0

  20. [2014]

    URL https://proceedings.neurips.cc/paper_files/paper/2014/hash/ 757f843a169cc678064d9530d12a1881-Abstract.html

    2014

  21. [2957]

    URL https://doi.org/10.1007/ s12532-020-00194-3

    doi: 10.1007/s12532-020-00194-3. URL https://doi.org/10.1007/ s12532-020-00194-3

    doi

  22. [5528]

    URL https://pubsonline.informs

    doi: 10.1287/ijoc.2023.0255. URL https://pubsonline.informs. org/doi/10.1287/ijoc.2023.0255

    2023

Pith tools

Reviewed August 6, 2026 · model on record in the stance chip above.