{"id":"79323a78-db15-4b84-b4cd-2b0508390bb1","arxiv_id":"2411.15090","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"For MILP families with a fixed constraint matrix and lattice-valued right-hand-sides, a finite set of aggregation multipliers yields the Gomory mixed-integer cut closure for all instances, motivating a data-driven cut-reuse heuristic.","lead":"This paper proves that for families of similar mixed-integer optimization problems with right-hand-side values on a lattice, one finite list of Gomory cut multipliers can generate the full cut closure for every instance. It then reuses multipliers from historical instances on new ones and reports up to about 1.5x speedups in Gurobi's solver work on selected MIPLIB 2017 benchmark families.","discovery_kind":"first_principles","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The 1.49x work-unit speedup is reported only on 50 instances preselected for positive expert-cut performance, and wall-clock speedups exceed 1.0 only on 14 hard instances, so the practical claim of significant acceleration lacks a statistically valid evaluation.","rationale":"The reader's weakest_assumption focuses on the lattice/RHS mismatch, but I find that concern secondary: in finite precision, any collection of floating-point RHS vectors lies in a common dyadic lattice, so the experimental samples are not literally outside the theorem's scope. The more load-bearing issue is the evaluation protocol for the empirical claim. The paper is transparent that it focuses on 50 instances where the expert method helped, but the abstract and introduction make a general claim of significant acceleration of Gurobi using default settings. Averaging speedups over a set selected for expert benefit, without error bars or paired tests, does not establish that the method helps on typical instances from the distribution. The work-unit speedups exclude cut-generation overhead, and the wall-clock speedups across all 50 are near 1.0 except on the hard subset. The theoretical result itself appears structurally sound: the proof's cone decomposition, use of Carathéodory, and bounded-representative argument are consistent with prior split-closure finiteness arguments, and the duplicated theorem text in the appendix is a presentation error rather than a mathematical flaw. Because the reader already issued a CONDITIONAL verdict based on computational weaknesses, my concern reinforces the same condition rather than changing the verdict, so UNCHANGED is appropriate.","tokens_in":51453,"tokens_out":15351,"duration_ms":158523,"concrete_test":"Rerun the learning heuristic on all 135 instances that completed the expert benchmark (or on a 50-instance held-out subset chosen without reference to expert speedup), with identical preprocessing, and compute paired per-instance total-time speedups against baseline. Apply a Wilcoxon signed-rank test (two-sided, alpha=0.05) to the median speedup; also report the same analysis on the 14 hard instances. If the median time speedup is not significantly greater than 1 on the held-out set, the claim of significant acceleration is not supported.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central practical claim—that reusing historical aggregation multipliers significantly accelerates a commercial MILP solver under default settings—rests on Tables 1 and 2. But the evaluation set is the 50 MIPLIB instances (out of 135 that ran to completion) for which the expert cut method had average speedup above 1.01 (Section 5.3). The learning heuristic is then tested on that same selected set, so the reported average speedups (1.49x work, 1.03x time for ml:near:1; 1.17x time on 14 hard instances) are conditioned on the expert being useful. No confidence intervals, paired tests, or pre-registered analysis are provided, and the arithmetic-mean speedup is driven by a few large gains (e.g., exp-1-500-5-5: 10.44x, neos-5049753-cuanza: 3.58x) while many instances are slower. Since the abstract claims significant acceleration 'even when taking into account the time required to predict aggregation multipliers and compute the cut coefficients,' the only method with total-time speedup above 1 across all 50 is ml:near:1 at 1.03x, which is marginal. The theoretical lattice assumption is less damaging: any finite set of floating-point RHS vectors lies in a common lattice, so the tested samples are not outside the theorem's scope; the real gap is that Theorem 1 guarantees existence of a universal finite Lambda but no recovery guarantee from training samples.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the use of historical data to generate Gomory mixed-integer cuts (GMICs) for families of MILPs that share a constraint matrix but vary in right-hand-side and objective coefficients. The main theoretical contribution is Theorem 1, which states that when the right-hand-sides vary over a rational lattice, the GMIC closure of every instance in the family can be obtained from one finite list of aggregation multipliers. The proof, given in Appendix A, follows standard split-cut and basis-support arguments. Building on this result, the authors propose a simple learning heuristic: collect aggregation multipliers (stored as bases/tableaux) from training perturbations, then reuse them for test instances. Experiments on MIPLIB 2017-derived perturbations with Gurobi 11 report work-unit speedups up to 1.49x and total-time speedups up to 1.17x on hard instances, using default solver settings and three random seeds.","tokens_in":51733,"tokens_out":11393,"duration_ms":116307,"significance":"If the finiteness theorem is correct, it is a clean and nontrivial contribution to the theory of parametric cut closures: it shows that an infinite family of lattice-perturbed MILPs admits a finite universal set of aggregation multipliers for the GMIC closure. The proof is self-contained and appears mathematically sound. The computational study is also carefully conducted in several respects: it uses a commercial solver with default settings, reports deterministic work units alongside time, averages over multiple seeds, and releases code through the MIPLearn framework. The authors are transparent about the overhead of cut generation and about the fact that the expert method is not competitive once collection time is counted. However, the empirical significance is currently weakened by the fact that the learning heuristic is evaluated only on the 50 instances where the expert method was already positive, and by the absence of statistical inference on the speedup claims.","major_comments":[{"comment":"The evaluation set for the learning heuristic is the 50 instances for which the expert method achieved an average work-unit speedup above 1.01 (Section 5.3), and Section 5.4 states this explicitly: \"we evaluate the performance of the learning heuristic, focusing on the 50 benchmark instances in which the expert provided positive results.\" Because the learning heuristic imitates the expert cut-collection procedure, this is selection on the outcome variable. The reported average speedups (1.49x work for ml:near:50 and 1.03x total time for ml:near:1 in Table 1) are therefore conditional on the expert being useful and do not estimate the method's performance on the full set of 135 instances that completed the expert benchmark, let alone the original 186 perturbed instances. The abstract's unconditional phrasing (\"significantly accelerate the performance of Gurobi for many benchmark instances\") should be qualified, or the results should be reported on all 135 instances with a positive/neutral/negative breakdown.","section":"Section 5.4, Table 1"},{"comment":"No statistical inference is provided for the speedup claims. Per-instance speedups in Table 12 are highly dispersed (e.g., ml:near:50 ranges from 0.18 for bab6 to 10.44 for exp-1-500-5-5), and the reported arithmetic means are driven by a few large gains. The only total-time speedup above 1 across all 50 instances is ml:near:1 at 1.03x, which is within the range of typical solver noise; the 1.17x total-time speedup on the 14 hard instances is based on n=14. The authors should report confidence intervals, a paired test (e.g., Wilcoxon signed-rank) on per-instance speedups, and geometric means, and should state a pre-specified significance criterion before claiming \"significant acceleration.\"","section":"Section 5.4, Tables 1, 2, 12, 14"},{"comment":"Theorem 1 guarantees a finite multiplier list for the GMIC closure when the right-hand-side perturbations lie in a rational lattice, but the experiments in Section 5.2 generate right-hand-sides by multiplicative perturbations r ~ U[0.9,1.1], which are not explicitly constrained to any common lattice. Any finite set of rational floating-point perturbations does lie in the lattice it generates, so the theorem is not formally inapplicable to the tested samples, but the tested set is only a finite sample from an infinite family and Theorem 1 provides no recovery guarantee that a training-based list of multipliers approximates the closure. The paper should state this limitation explicitly in Section 5 rather than presenting Theorem 1 as the direct explanation for the observed speedups; the current conclusion already notes that the all-RHS case is open, but the experiments use continuous perturbations.","section":"Section 3 vs. Section 5.2"}],"minor_comments":[{"comment":"Theorems 2 and 3 are identical in statement and proof, and Corollaries 1 and 2 are identical as well. This duplication should be removed or consolidated.","section":"Appendix A"},{"comment":"The text says \"there exists a finite set of multipliers Γ\" but the displayed intersection is over Λ; this is a typo and should be fixed.","section":"Corollaries 1 and 2"},{"comment":"The sentence \"by Carathéodory's Theorem at most m+n of the ψs are positive\" should be clarified: one must choose a conic Carathéodory representation with at most m+n positive coefficients, since an arbitrary representation need not have this property.","section":"Appendix A, proof of Theorem 1"},{"comment":"Several tables contain formatting artifacts, including \"1.2 8\", \"1.3 0\", and \"77,5 00\"; the tables should be regenerated.","section":"Tables 1 and 4"},{"comment":"The relationship between the 55 generated variations (50 training, 5 test) and the 186 instances discussed in the perturbation-quality check should be stated more clearly; the text sometimes refers simply to \"the five test variations of the 186 instances.\"","section":"Section 5.2"},{"comment":"The offline training cost of cut collection is not reported. Since the intended application is recurring optimization, stating the training time per instance would help readers assess how the offline cost is amortized.","section":"Section 5.4"}],"recommendation":"major_revision","confidential_remarks":"The theoretical result is a solid contribution and the authors are honest about overhead and limitations. My main reservation is that the empirical claim in the abstract is not supported by the current evaluation design; if the authors revise the computational section to include all completed instances and proper statistical tests, I would be supportive."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Theorem 1 is the real news. For an infinite family of MILPs sharing one constraint matrix and with right-hand-sides living in a rational lattice, the paper proves there is a single finite list of aggregation multipliers whose GMIC cuts define the full GMIC closure of every member of the family. The proof is a standard split-cut domination argument built on the bounded-support lemma; I read it through and didn't find a hole. The authors also correctly distinguish it from Dash et al.'s finite split-closure results, which use a different definition. That is a genuine new structural result, and it is the part worth remembering.\n\nThe data-driven heuristic is simpler: collect aggregation multipliers from historical instances, reuse them on new ones. It is a natural idea and the implementation is honest about its simplifications. Credit also for shipping the code inside MIPLearn.\n\nThe soft spot is the computational claim. The headline '1.49x work-unit speedup' is computed on the 50 instances (out of 135) that were preselected because the expert cut method already helped. That is selection bias. The work-unit numbers ignore cut-generation overhead, and the total-time speedup for the best all-50 variant is 1.03x, which is marginal. On the 14 hard instances the time speedups are more convincing (1.08–1.17x), but still no confidence intervals or paired tests. The abstract's claim of 'significantly accelerate' overstates the evidence.\n\nTwo smaller flags. The lattice assumption in Theorem 1 is less of a problem than it looks: any finite set of floating-point RHS vectors lies in a common lattice, so the tested instances are not outside the theorem's scope. The real gap is that the theorem guarantees existence of a finite universal list but gives no recovery guarantee from training samples, so the heuristic's success is empirical. Also, the appendix contains Theorem 2 and Theorem 3 which are word-for-word identical; that is a mechanical error that should be corrected.\n\nWho is this for? People working on learning-enhanced MILP and on cut closures. The theory section alone justifies a serious referee. The computational evaluation needs major revision—proper benchmark selection, error bars, and a more careful statement about what is and isn't demonstrated.\n\nRecommendation: send it to review, with a clear request to fix the experimental protocol and the duplicated theorem before publication.","headline":"Solid finiteness theorem for GMIC closures over lattices; computational speedups are real but overstated due to benchmark preselection and marginal total-time gains.","tokens_in":52302,"tokens_out":2081,"would_cite":true,"duration_ms":20728,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C10","90C57"],"pacs":[],"model":"deepseek-v4-flash","headline":"A single finite list of aggregation multipliers reproduces the full Gomory mixed-integer cut closure of every MILP in a fixed-matrix family, and reusing such historical multipliers speeds up Gurobi's work by up to 1.49x.","keywords":["Mixed-integer linear programming","Gomory mixed-integer cuts","GMIC closure","aggregation multipliers","machine learning","cutting planes","data-driven optimization","split cuts"],"falsifier":"To check Theorem 1 itself: fix a small integral matrix $A$ and lattice $\\Gamma$, enumerate all non-dominated rank-1 split cuts for $\\gamma$ over a growing box of lattice points, and record the number of distinct aggregation multipliers required; if that number is unbounded as the box grows, the theorem is false. To check whether the theorem explains the speedups: run the reuse heuristic on two families with the same constraint matrix, one with right-hand-sides perturbed on a lattice and one perturbed continuously; the theorem guarantees the finite-list property only in the lattice case, so similar gains in both regimes would show the practical success rests on a different mechanism.","tokens_in":51223,"feed_emoji":"⚙️","tokens_out":18189,"duration_ms":163348,"temperature":0.7,"pith_summary":"This paper claims that cut-generating effort for recurring mixed-integer linear programs can be spent once, offline, and reused on every future instance. It proves that for any family of MILPs sharing one constraint matrix, if the right-hand-sides lie on a rational lattice $\\Gamma$, a single finite list of aggregation multipliers $\\Lambda$ reproduces the complete Gomory mixed-integer cut (GMIC) closure of every instance in the family. This theorem motivates a simple heuristic: collect the aggregation multipliers that produced strong cuts on historical instances of a task, then generate cuts from those same multipliers when solving new instances. On 50 instance families built from MIPLIB 2017 problems, the heuristic cuts Gurobi's work by up to 1.49x on average and improves its wall-clock time by 1.08–1.17x on the hardest instances, counting all preprocessing and cut-generation overhead. If the results hold, repeatedly solved operational models could move most cut-finding effort out of the solve itself.","feed_headline":"One fixed cut list serves every MILP in a family","feed_subtitle":"Reusing historical aggregation weights cuts Gurobi's work up to 1.49x and its runtime on hard instances.","key_machinery":"The central object is the aggregation multiplier $\\lambda\\in\\mathbb{R}^m$, the vector of weights that combines the constraints $Ax=b$ into a single equality; every GMIC is the Gomory cut of such a one-row relaxation, and the closure is formally $G(IP)=\\bigcap_{\\lambda\\in\\mathbb{R}^m}\\mathrm{GMIC}(IP_\\lambda)$. The mechanism that makes this continuous intersection finite is a sign-pattern cone $C_{\\mathrm{sign}}(u)$ attached to each legitimate cut-generating pair $u=(\\lambda,v)$: the cone fixes which entries of the generator are zero, positive, or negative, and its defining constraints contain no right-hand-side term, so the cone is identical across the whole family. Splitting $u=u_1+u_2$ where the integer part $u_2$ satisfies $(\\theta_2)^\\top(b+\\gamma)\\in\\mathbb{Z}$ gives that the cut of $u$ is dominated by the cut of $u_1$, and Carathéodory-style rescaling of the cone's extreme rays places $u_1$ in the bounded box $\\|u_1\\|_\\infty\\le H=(m+n)\\cdot M(\\Gamma)\\cdot\\Delta$, where $M(\\Gamma)$ clears the lattice denominators and $\\Delta$ is the largest cone subdeterminant. Because undominated cuts must have basis support, the bounded box contains only finitely many candidates, giving the finite list $\\Lambda$. The heuristic side stores each collected cut as the tableau row that produced it — equivalent to storing its multiplier — gathered by a simplified relax-and-cut loop that re-solves the LP with accumulated cuts, transfers cut dual values into the objective, and walks to a new basis.","core_discovery":"On the paper's own terms, the central discovery is Theorem 1. Let $\\Gamma$ be the lattice generated by rational vectors $b_1,\\dots,b_k$ and consider the parametric family $IP(\\gamma)=\\{x\\in\\mathbb{R}_+^n : Ax=b+\\gamma,\\ x_j\\in\\mathbb{Z}\\ \\forall j\\in J\\}$ for $\\gamma\\in\\Gamma$. The theorem states that there exists a finite set $\\Lambda\\subseteq\\mathbb{R}^m$ such that $G(IP(\\gamma))=\\bigcap_{\\lambda\\in\\Lambda}\\mathrm{GMIC}(IP(\\gamma)_\\lambda)$ for every $\\gamma\\in\\Gamma$: one finite multiplier list yields the entire GMIC closure of every member of an infinite family. The proof shows that any non-dominated cut-generating pair $(\\lambda,v)$ can be decomposed so that the dominated part is an integer vector orthogonal to the right-hand-side, leaving a normalized generator inside a box of size $H=(m+n)\\cdot M(\\Gamma)\\cdot\\Delta$; since the sign-pattern cone attached to a cut does not depend on $\\gamma$, and since non-dominated cuts have basis support, only finitely many generator patterns survive. In the pure-integer case the same finite list works for all real right-hand-sides (Corollary 1). The paper also reports the computational consequence: reusing multipliers gathered from 50 historical instances gives the best average work-unit speedup of 1.49x, beating default Gurobi on every configuration tested.","pith_inferences":["A testable prediction: quantizing the right-hand-side perturbations of these families to a rational lattice should preserve the observed speedups, and the theorem would then cover the regime; conversely the current multiplicative perturbations in $[0.9,1.1]$ are continuous and fall outside the theorem's guarantee, so part of the demonstrated gain may rest on a softer empirical regularity.","The insensitivity to which training instances are chosen hints that, for a fixed constraint matrix, the useful aggregation multipliers form a dense and stable set rather than rare points, which would explain why even one historical instance's cuts match the expert's fresh ones on many problems.","The wall-clock gap between work-unit and time speedups is mostly an artifact of the external cut pipeline (recomputing standard form and tableaux outside the solver), so the reported times likely understate what an embedded implementation could achieve on easier instances as well."],"forward_implications":["For an operational MILP solved repeatedly with fixed structure, the full GMIC closure of every future instance is available from one offline-computed multiplier list, at least when right-hand-side data is lattice-valued, so per-instance cut searching becomes unnecessary.","For pure integer programs the finite list covers all real right-hand-sides without any lattice assumption, so the strongest version of the guarantee holds exactly where no continuous variables are present; the paper leaves the general mixed-integer case as an open question.","A data-driven cut-selection method can accelerate a commercial solver at default settings: the best variant reduces Gurobi's work by 1.49x on average over 50 families and 1.40x on the 14 hardest, and every learning variant beats default Gurobi in work units.","Wall-clock gains of 1.08–1.17x on the hardest instances survive after charging multiplier prediction, tableau computation, and cut generation to the method, while freshly recomputing cuts per instance (the expert method plus its collection time) falls below baseline.","Using more training multipliers helps rather than hurts: the best work-unit result uses all 50 training instances, and nearest, farthest, and random instance selection perform similarly, so the gain does not hinge on a similarity model."],"supporting_citations":[{"why":"Supplies the split-cut and GMIC framework, the definition of legitimate cut-generating pairs, and the lemma that undominated cuts have basis support; the proof of Theorem 1 builds directly on these.","marker":"[19]"},{"why":"Original source of the support-is-a-basis characterization of non-dominated split cuts, invoked through the textbook lemma to restrict candidates to finitely many supports.","marker":"[3]"},{"why":"Provides the finite-description argument for MIR/split closures that the paper adapts to a parametric family of right-hand-sides.","marker":"[24]"},{"why":"Establishes polyhedrality of the (mixed-integer) Chvátal closure and its equivalence to split/GMIC closures, the background that makes a finite multiplier list a complete description.","marker":"[20]"},{"why":"Standard results on polyhedral cones and extreme-ray rescaling (including Carathéodory's theorem) used to bound normalized cut generators within the box of radius H.","marker":"[46]"},{"why":"The relax-and-cut framework whose simplified version is the cut collection algorithm that harvests aggregation multipliers from training instances.","marker":"[29]"},{"why":"MIPLIB 2017 is the benchmark library from which the 55-variation training and test families are generated.","marker":"[31]"}],"fun_headline_variants":["One finite cut list fits an infinite MILP family","Historical cuts speed up Gurobi 1.49x","Finite weights close all GMIC closures in a lattice","Data-driven cuts: one list for whole families","Theorem: one multiplier set yields all GMIC closures"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that the right-hand-side shifts $\\gamma$ all belong to one fixed rational lattice; if they instead vary continuously, the theorem's finite-list guarantee is not known to hold, and the paper's own experiments perturb right-hand-sides continuously rather than on a lattice.","fun_headline_variants_meta":{"raw":{"variants":["One finite cut list fits an infinite MILP family","Historical cuts speed up Gurobi 1.49x","Finite weights close all GMIC closures in a lattice","Data-driven cuts: one list for whole families","Theorem: one multiplier set yields all GMIC closures"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00047,"raw_usage":{"total_tokens":2432,"prompt_tokens":1128,"completion_tokens":1304,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":744,"completion_tokens_details":{"reasoning_tokens":1226}},"tokens_in":744,"tokens_out":1304,"duration_ms":9295,"temperature":1.0,"reasoning_tokens":1226,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:31:07.143514+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"To check Theorem 1 itself: fix a small integral matrix $A$ and lattice $\\Gamma$, enumerate all non-dominated rank-1 split cuts for $\\gamma$ over a growing box of lattice points, and record the number of distinct aggregation multipliers required; if that number is unbounded as the box grows, the theorem is false. To check whether the theorem explains the speedups: run the reuse heuristic on two families with the same constraint matrix, one with right-hand-sides perturbed on a lattice and one perturbed continuously; the theorem guarantees the finite-list property only in the lattice case, so similar gains in both regimes would show the practical success rests on a different mechanism.","supporting_citations":[{"cited_title":"Integer programming","cited_arxiv_id":null,"evidence_quote":"Supplies the split-cut and GMIC framework, the definition of legitimate cut-generating pairs, and the lemma that undominated cuts have basis support; the proof of Theorem 1 builds directly on these."},{"cited_title":"Split cl osure and intersection cuts","cited_arxiv_id":null,"evidence_quote":"Original source of the support-is-a-basis characterization of non-dominated split cuts, invoked through the textbook lemma to restrict candidates to finitely many supports."},{"cited_title":"Mir closure s of polyhedral sets","cited_arxiv_id":null,"evidence_quote":"Provides the finite-description argument for MIR/split closures that the paper adapts to a parametric family of right-hand-sides."},{"cited_title":"Chvátal closures for mixed integer programming problems","cited_arxiv_id":null,"evidence_quote":"Establishes polyhedrality of the (mixed-integer) Chvátal closure and its equivalence to split/GMIC closures, the background that makes a finite multiplier list a complete description."},{"cited_title":"A relax-and-c ut framework for gomory mixed-integer cuts","cited_arxiv_id":null,"evidence_quote":"The relax-and-cut framework whose simplified version is the cut collection algorithm that harvests aggregation multipliers from training instances."},{"cited_title":"Miplib 2017: data-driven compilation of t he 6th mixed-integer programming library","cited_arxiv_id":null,"evidence_quote":"MIPLIB 2017 is the benchmark library from which the 55-variation training and test families are generated."}],"review_version":1}