{"id":"61bffb62-6740-4f59-9ea0-271a823e0391","arxiv_id":"2507.11063","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A new training-free distance metric compares MILP instances by matching the proportions of variable-weight pairs in their constraints, and it groups problems by class almost as well as a supervised graph neural network.","lead":"This paper introduces a distance metric that measures how similar two mixed-integer linear programming (MILP) problem instances are, using only the structure of their equations. If it works, it could help machine learning systems pick the right solver or training data for a given optimization problem.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The metric collapses constraints of different arity and coefficient magnitudes into identical normalized representations (Section 3.4 admits this), so dP can be zero between structurally very different instances, threatening the claim of a meaningful structural similarity measure.","rationale":"The reader's conditional verdict is well-founded. I focused on whether the metric's utility claim survives the lossy representation. The mathematical metric properties are likely sound: EMD with a metric ground distance yields a metric, and adding the objective term preserves this. The real question is what the metric is a distance on. Because weights and right-hand sides are discretized into three classes and constraints are normalized by arity, the distance is defined on a coarse quotient of the MILP space. The paper itself acknowledges the arity collapse in Section 3.4. This is potentially load-bearing because the headline claim promises a metric that can characterize structural similarity and heterogeneity. A concrete augmented-distance experiment on StrIPLIB would determine whether restoring the discarded information changes the empirical grouping. If it does not, the conditional acceptance is appropriate; if it does, the metric's practical claims are overstated. This is not an objection to the mathematical validity, only to the semantic faithfulness of the representation. The 'first mathematical distance' framing is also questionable since Euclidean distances in feature or embedding spaces are already metrics, but this is a novelty phrasing issue rather than a correctness risk. Overall, the central claim holds conditionally, and the proposed check would settle whether the acknowledged limitation actually undermines the claimed practical value.","tokens_in":14993,"tokens_out":10400,"duration_ms":131164,"concrete_test":"Repeat the StrIPLIB class-identification experiment from Section 4.1 with a modified distance dP'(P,Q) = dP(P,Q) + λ·|log(mean_arity(P)/mean_arity(Q))|, sweeping λ over {0, 0.1, 1, 10} (λ=0 reproduces Table 2). If any λ yields a mean top-40 accuracy improvement of more than 5 points, the current metric's insensitivity to constraint arity is empirically load-bearing; if not, the concern is real but does not hurt the claimed grouping performance. Additionally, construct a synthetic twin P' of a StrIPLIB instance by expanding every constraint's variables into 100 copies with the same weight and variable classes, and verify that dP(P,P') = 0, confirming the mechanism of the collapse.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theoretical claim (Theorem 3) is likely correct: dP is a metric on the normalized representation (2). The load-bearing question is whether that representation preserves enough structure for the metric to be a meaningful MILP similarity measure. Section 3.2 discretizes weights to {-1,1,R\\{-1,1}} and right-hand sides to {0,1,R\\{0,1}}, placing all other values in a residual class, so coefficients differing by orders of magnitude are treated as identical. Section 3.3 normalizes each constraint by its number of variables n_i, so constraint arity is discarded entirely. Consequently, the constraint x ≤ 1 and the cardinality constraint Σ_{j=1}^{1000} x_j ≤ 1 have the same normalized representation, and dP between instances differing only in such constraints is zero. The authors explicitly acknowledge this in Section 3.4: 'a constraint involving a single variable can have zero distance from one in which that variable appears multiple times, even though their semantics may differ significantly.' Since the paper's headline claim is that dP is a mathematical distance 'derived directly from their mathematical formulations' that identifies structurally similar instances, this lossiness is not a side detail: it means the distance is a metric on a coarse quotient of the MILP space. The empirical top-40 accuracy on StrIPLIB demonstrates that the quotient still correlates with the given class labels, but that correlation may be driven by features that survive the normalization (e.g., variable-type distributions), and the metric may silently equate genuinely different formulations. The concern is therefore that the central utility claim is conditional on the lossy representation being sufficient for the intended downstream uses (benchmark heterogeneity, ML-MILP training-set selection).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":15278,"tokens_out":4301,"duration_ms":51140,"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":[{"comment":"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.","section":"§3.2, §3.4, Eq. (2)–(5)"},{"comment":"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.","section":"§4.1, Table 2"},{"comment":"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.","section":"§3.2, §4"},{"comment":"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.","section":"§3.4, Theorems 1–3"}],"minor_comments":[{"comment":"The word 'appraoch' should be 'approach' in the phrase 'classification appraoch'.","section":"§2.2"},{"comment":"The word 'simiarity' should be 'similarity'.","section":"§3.4"},{"comment":"The capitalization of the dataset name is inconsistent: 'StrIPLIB', 'strIPLIB', and 'strIPlib' all appear; please standardize.","section":"Throughout"},{"comment":"The notation 'denoted as ex = 10x' is unclear; please clarify how the proportional occurrences are represented.","section":"Table 1 caption"},{"comment":"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.","section":"§3.5"},{"comment":"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.","section":"Abstract, §1"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of a journal on optimization and machine learning, and the empirical study is fairly extensive. However, the central overclaim about working directly on the mathematical formulation, the factual error regarding the greedy/exact comparison, and the absence of proofs for the main theorems need to be addressed before the paper can be recommended for acceptance. The comparison with the GNN baseline is somewhat favorable to the proposed method because the GNN was trained on the same classes, but the authors are transparent about this limitation."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know about arXiv:2507.11063. First, the construction is genuinely new and clean: discretize weights, right-hand sides, and variable types into a few classes, represent each constraint as a normalized distribution over weight-variable pairs, and compare instances via Earth Mover's Distance. Second, the paper's own Section 3.4 admits that this representation is lossy enough for a single-variable constraint and a repeated-variable constraint to be at zero distance. That limitation is more load-bearing than the authors suggest, but it is not fatal.\n\nWhat the paper does well: Theorems 1–3 are standard EMD metric properties, and they appear correct on the normalized representation (2). The greedy heuristic is a real practical contribution, giving nearly identical accuracy with a 200× speedup. The experimental comparison is honest in scope: the unsupervised method outperforms the feature-based and image-based baselines and roughly matches a supervised GNN on class and subclass grouping. Code and data are publicly available, which makes the work reproducible.\n\nThe soft spots are proportionate. The discretization collapses all weights except -1 and 1 into a residual class, and likewise for right-hand sides; constraint arity is normalized away entirely. So dP can be zero between instances that differ by orders of magnitude in coefficients or in constraint length. The authors acknowledge this in Section 3.4 but frame it as a minor flexibility; in fact, it means the metric is defined on a coarse quotient of the MILP space, not on the full space. The headline claim of being \"the first mathematical distance metric for MILP instances\" is overstated—feature-based Euclidean distances with proper normalization also satisfy metric axioms. The experimental comparison relies on reported GNN and ISS numbers rather than re-implementations, and there are no error bars or significance tests. The class boundaries for weights and RHS are derived from MIPLIB 2017 and applied to StrIPLIB; the paper notes similar patterns but does not test for distribution shift.\n\nNone of these are deal-breakers. The formal part holds up, the empirical evidence supports the grouping claim, and the limitations are stated rather than hidden. The paper would be stronger with a toned-down novelty claim, explicit discussion of the quotient issue, and some statistical grounding for the accuracy numbers.\n\nMy take: this deserves a serious referee. It is a useful, citable tool for the ML-MILP community—benchmark heterogeneity and training-set selection are real applications. I would send it to peer review with a request for revisions, and I would bring it to a reading group to argue about how much structure the normalization throws away.","headline":"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.","tokens_in":15893,"tokens_out":2047,"would_cite":true,"duration_ms":27044,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["mixed-integer linear programming","distance metric","Earth mover's distance","instance similarity","unsupervised learning","StrIPLIB","constraint classification","optimal transport"],"falsifier":"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.","tokens_in":14748,"feed_emoji":"📐","tokens_out":11328,"duration_ms":117154,"temperature":0.7,"pith_summary":"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.","feed_headline":"Groups integer-programming instances with no training","feed_subtitle":"A formulation-only distance beats feature- and image-based baselines, nearly matching a supervised GNN.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the Earth mover's distance formalism on which the constraint-level and instance-level distances are built.","marker":"[16]"},{"why":"Sources the empirical singleton frequencies that define the weight and right-hand-side classes, and provides the feature-based baseline.","marker":"[7]"},{"why":"Provides the StrIPLIB dataset and its hierarchical class and subclass labels used in evaluation.","marker":"[3]"},{"why":"Defines the supervised GNN baseline and the test/reference protocol with top-40 accuracy.","marker":"[20]"},{"why":"Introduces the image-based baseline and the class-selection criterion used in the first experiment.","marker":"[19]"},{"why":"Motivates the entropy-based discretization principle behind the classification scheme.","marker":"[26]"},{"why":"Supplies the complexity bound for exact Earth mover's computation that motivates the greedy heuristic.","marker":"[13]"}],"fun_headline_variants":["No-training distance metric for MILP instances","Formulation-only distance rivals supervised learning","Earth mover's distance adapted for MILP instances","Unsupervised metric nearly matches GNN on MILP"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["No-training distance metric for MILP instances","Formulation-only distance rivals supervised learning","Earth mover's distance adapted for MILP instances","Unsupervised metric nearly matches GNN on MILP"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000508,"raw_usage":{"total_tokens":2488,"prompt_tokens":973,"completion_tokens":1515,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":589,"completion_tokens_details":{"reasoning_tokens":1457}},"tokens_in":589,"tokens_out":1515,"duration_ms":13542,"temperature":1.0,"reasoning_tokens":1457,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:17:01.797484+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Gleixner, G","cited_arxiv_id":null,"evidence_quote":"Sources the empirical singleton frequencies that define the weight and right-hand-side classes, and provides the feature-based baseline."},{"cited_title":"Bastubbe, A","cited_arxiv_id":null,"evidence_quote":"Provides the StrIPLIB dataset and its hierarchical class and subclass labels used in evaluation."},{"cited_title":"Steever, C","cited_arxiv_id":null,"evidence_quote":"Introduces the image-based baseline and the class-selection criterion used in the first experiment."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Motivates the entropy-based discretization principle behind the classification scheme."}],"review_version":1}