Pith. sign in

REVIEW 3 major objections 6 minor 60 references

Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data

T0 review · 3 major / 6 minor · reviewed 2026-08-12 · deepseek-v4-flash

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

Pith's one-line read 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.

desk verdict Solid finiteness theorem for GMIC closures over lattices; computational speedups are real but overstated due to benchmark preselection and marginal total-time gains. read the letter →

arxiv 2411.15090 v1 pith:R7Y6JVJ4 submitted 2024-11-22 math.OC

Berkay Becu , Santanu S. Dey , Feng Qiu , Alinson S. Xavier This is my paper · ORCID
classification math.OC MSC 90C1190C1090C57
keywords Mixed-integerlinearprogrammingGomorycutsGMICclosureaggregationmultipliersmachinelearningcuttingplanesdata-drivenoptimizationsplit
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

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

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

  • 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.
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

3 major / 6 minor

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.

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 (3)
  1. [Section 5.4, Table 1] 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.
  2. [Section 5.4, Tables 1, 2, 12, 14] 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."
  3. [Section 3 vs. Section 5.2] 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.
minor comments (6)
  1. [Appendix A] 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.
  2. [Corollaries 1 and 2] The text says "there exists a finite set of multipliers Γ" but the displayed intersection is over Λ; this is a typo and should be fixed.
  3. [Appendix A, proof of Theorem 1] 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.
  4. [Tables 1 and 4] Several tables contain formatting artifacts, including "1.2 8", "1.3 0", and "77,5 00"; the tables should be regenerated.
  5. [Section 5.2] 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."
  6. [Section 5.4] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: Theorem 1 is proved from standard polyhedral results with an explicit bound, the learned multipliers are trained on held-out perturbations, and the expert-positive subset selection is evaluation screening rather than a derivation that assumes its conclusion.

full rationale

The paper's central theoretical claim, Theorem 1, is self-contained: it proves the existence of a finite multiplier set Lambda for a lattice-parameterized family of MILPs by bounding the norm of any non-dominated legitimate pair (lambda, v) by H = (m+n)*M(Gamma)*Delta and then observing that the set Pi of split disjunctions with bounded integer coefficients is finite. The proof invokes standard results (Corollary 5.6 of Conforti et al., subdeterminant bounds from Schrijver) and does not assume the conclusion. No fitted parameter appears in the theorem or its bound. The computational heuristic is trained on 50 training perturbations and tested on 5 separate test perturbations per MIPLIB instance, so the aggregation multipliers are not fit to the instances on which speedups are reported. The evaluation set is restricted to the 50 instances where the expert cut-collection method had average work speedup above 1.01 (Section 5.3), and the learning heuristic is then measured on that same set (Section 5.4); this is a legitimate concern about selection bias and external validity, but it is not circularity, because the learning heuristic's speedups are not forced by the screening rule and the screening variable (expert speedup) is not a parameter of the learned model. The paper's self-citations, e.g., the MIPLearn software reference [45], are implementation and background citations, not load-bearing evidence for the finiteness theorem or for the empirical speedup. The lattice assumption in the theorem is acknowledged as a limitation and does not smuggle in the heuristic's success. Overall, the derivation chain is not circular: the theoretical result is proved independently, and the empirical claim rests on held-out test variations, albeit on a favorably selected subset.

Assumptions & free parameters 5 free parameters · 6 assumptions · 0 invented entities

The theorem's finite-list construction uses no fitted constants; the bound H is derived from A, Gamma, and the dimensions. The computational method introduces several hand-chosen hyperparameters: K, the fractionality threshold, the tableau cut cap, perturbation intervals, and the k/selection rule for training instances. The lattice-RHS assumption is the main domain axiom, and it is not satisfied by the continuous multiplicative perturbations used in the experiments. No new physical or mathematical entities are postulated.

free parameters (5)
  • Cut collection iteration limit K = 10
    Appendix B: the relax-and-cut procedure repeats at most K iterations; chosen by hand.
  • Fractionality threshold = 0.001
    Appendix B: tableau rows are selected only if fractionality is greater than 0.001.
  • Maximum cuts per tableau = 500
    Appendix B: q(B) = min(hat q, 500), capping cuts generated from one basis.
  • Perturbation ranges for RHS and objective = RHS r~U[0.9,1.1]; objective r~U[0.75,1.25]; additive {-1,0,1} for all-integer equalities
    Section 5.2: benchmark generation uses these hand-chosen ranges; the paper does not test sensitivity to them.
  • Training set size k and selection strategy = k in {1,10,50}; closest, farthest, or random with z-scored Euclidean features
    Section 5.4: these hyperparameters are chosen by the authors and varied, but no principled selection rule is derived.
assumptions (6)
  • standard math The constraint matrix A and base right-hand-side b can be assumed integral after scaling.
    Section 3 states the data is integral without loss of generality; standard MILP scaling.
  • domain assumption Right-hand-side perturbations lie on a lattice Gamma generated by rational vectors.
    Section 3, Equation (5) and Theorem 1: this premise is what makes the finite multiplier list possible.
  • standard math Every non-dominated split/GMI cut corresponds to a legitimate pair (lambda, v) whose support is a basis.
    Appendix A, Lemma 1 (Corollary 5.6 in [19]); used to restrict attention to finitely many candidates.
  • standard math Caratheodory's theorem applies to the cone C_sign(u), and its extreme rays can be scaled to bounded integral vectors.
    Proof of Theorem 2 in Appendix A; standard polyhedral cone argument.
  • domain assumption Perturbed MIPLIB 2017 families represent realistic distributions of similar operational MILPs.
    Section 5.2: the benchmark families are synthetic perturbations of MIPLIB instances, not verified real-world recurring instances.
  • domain assumption Gurobi with default settings and with the optimal solution supplied is an appropriate testbed for cut effectiveness.
    Section 5.1: the authors intentionally focus on the dual side by providing optimal solutions; this isolates cut progress but does not model full solve-from-scratch usage.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data." pith.science (2026). https://pith.science/paper/R7Y6JVJ4

@misc{pith2026241115090,
  author       = {Pith},
  title        = {Pith review of: Approximating the Gomory Mixed-Integer Cut Closure Using Historical Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/R7Y6JVJ4}},
  note         = {Machine review of arXiv:2411.15090}
}
read the original abstract

Many operations related optimization problems involve repeatedly solving similar mixed integer linear programming (MILP) instances with the same constraint matrix but differing objective coefficients and right-hand-side values. The goal of this paper is to generate good cutting-planes for such instances using historical data. Gomory mixed integer cuts (GMIC) for a general MILP can be parameterized by a vector of weights to aggregate the constraints into a single equality constraint, where each such equality constraint in turn yields a unique GMIC. In this paper, we prove that for a family of MILP instances, where the right-hand-side of the instances belongs to a lattice, the GMIC closure for every instance in this infinite family can be obtained using the same finite list of aggregation weights. This result motivates us to build a simple heuristic to efficiently select aggregations for generating GMICs from historical data of similar instances with varying right-hand-sides and objective function coefficients. For testing our method, we generated families of instances by perturbing the right-hand-side and objective functions of MIPLIB 2017 instances. The proposed heuristic can significantly accelerate the performance of Gurobi for many benchmark instances, even when taking into account the time required to predict aggregation multipliers and compute the cut coefficients. To the best of our knowledge, this is the first work in the literature of data-driven cutting plane generation that is able to significantly accelerate the performance of a commercial state-of-the-art MILP solver, using default solver settings, on large-scale benchmark instances.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

60 extracted references · 55 canonical work pages

  1. [1]

    Miplib 2003

    Tobias Achterberg, Thorsten Koch, and Alexander Martin. Miplib 2003. Operations Research Letters, 34(4):361–372, 2006

    work page 2003

  2. [2]

    A machine learning-based approximation of strong branching

    Alejandro Marcos Alvarez, Quentin Louveaux, and Louis We henkel. A machine learning-based approximation of strong branching. INFORMS Journal on Com- puting, 29(1):185–195, 2017

    work page 2017

  3. [3]

    Split cl osure and intersection cuts

    Kent Andersen, Gérard Cornuéjols, and Yanjun Li. Split cl osure and intersection cuts. Mathematical programming, 102(3):457–493, 2005

    work page 2005

  4. [4]

    Embedding {0, 1/2}- cuts in a branch-and-cut framework: A computational study

    Giuseppe Andreello, Alberto Caprara, and Matteo Fischet ti. Embedding {0, 1/2}- cuts in a branch-and-cut framework: A computational study. INFORMS Journal on Computing , 19(2):229–238, 2007

    work page 2007

  5. [5]

    On finitely generated closures in the th eory of cutting planes

    Gennadiy A verkov. On finitely generated closures in the th eory of cutting planes. Discrete Optimization , 9(4):209–215, 2012

    work page 2012

  6. [6]

    Disjunctive programming

    Egon Balas. Disjunctive programming. Annals of discrete mathematics , 5:3–51, 1979

    work page 1979

  7. [7]

    Gomory cuts revisited

    Egon Balas, Sebastian Ceria, Gérard Cornuéjols, and N Nat raj. Gomory cuts revisited. Operations Research Letters, 19(1):1–9, 1996

    work page 1996

  8. [8]

    Optimizing over the split c losure

    Egon Balas and Anureet Saxena. Optimizing over the split c losure. Mathematical Programming, 113(2):219–240, 2008

    work page 2008

Show all 60 references
  1. [9]

    Structural analysis of branch-and-cut and the learnabilit y of gomory mixed integer cuts

    Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandho lm, and Ellen Vitercik. Structural analysis of branch-and-cut and the learnabilit y of gomory mixed integer cuts. Advances in Neural Information Processing Systems , 35:33890–33903, 2022

    2022

  2. [10]

    L earning to use local cuts

    Timo Berthold, Matteo Francobaldi, and Gregor Hendel. L earning to use local cuts. arXiv preprint arXiv:2206.11618 , 2022

    2022 arXiv

  3. [11]

    Online mix ed-integer optimization in milliseconds

    Dimitris Bertsimas and Bartolomeo Stellato. Online mix ed-integer optimization in milliseconds. INFORMS Journal on Computing , 34(4):2229–2248, 2022

    2022

  4. [12]

    Solving real-world linear programs: A de cade and more of progress

    Robert E Bixby. Solving real-world linear programs: A de cade and more of progress. Operations research, 50(1):3–15, 2002

    2002

  5. [13]

    Aggregation-based cutting-planes for packing an d covering integer pro- grams

    Merve Bodur, Alberto Del Pia, Santanu S Dey, Marco Molina ro, and Sebastian Pokutta. Aggregation-based cutting-planes for packing an d covering integer pro- grams. Mathematical Programming, 171:331–359, 2018

    2018

  6. [14]

    On the separation o f split cuts and related inequalities

    Alberto Caprara and Adam N Letchford. On the separation o f split cuts and related inequalities. Mathematical Programming, 94:279–294, 2003. 14 Becu, Dey, Qiu & Xavier

    2003

  7. [15]

    Learning cut generating f unctions for integer programming

    Hongyu Cheng and Amitabh Basu. Learning cut generating f unctions for integer programming. arXiv preprint arXiv:2405.13992 , 2024

    2024 arXiv

  8. [16]

    Sample complexity of algorithm selection using neural networks an d its applications to branch-and-cut

    Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and A mitabh Basu. Sample complexity of algorithm selection using neural networks an d its applications to branch-and-cut. arXiv preprint https://arxiv.org/abs/2402.02328 , 2024

    2024 arXiv

  9. [17]

    Continuous cutting pla ne algorithms in integer programming

    Didier Chételat and Andrea Lodi. Continuous cutting pla ne algorithms in integer programming. Operations Research Letters, 51(4):439–445, 2023

    2023

  10. [18]

    Sensitivi ty analysis for mixed bi- nary quadratic programming

    Diego Cifuentes, Santanu S Dey, and Jingye Xu. Sensitivi ty analysis for mixed bi- nary quadratic programming. In International Conference on Integer Programming and Combinatorial Optimization , pages 446–459. Springer, 2024

    2024

  11. [19]

    Integer programming

    Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli , Michele Conforti, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming. Springer, 2014

    2014

  12. [20]

    Chvátal closures for mixed integer programming problems

    William Cook, Ravindran Kannan, and Alexander Schrijve r. Chvátal closures for mixed integer programming problems. Mathematical Programming, 47(1):155–174, 1990

    1990

  13. [21]

    Revival of the gomory cuts in the 1990’s

    Gérard Cornuéjols et al. Revival of the gomory cuts in the 1990’s. Annals of Operations Research, 149(1):63–66, 2007

    1990

  14. [22]

    On the safety of gomory cut generators

    Gérard Cornuéjols, François Margot, and Giacomo Nannic ini. On the safety of gomory cut generators. Mathematical Programming Computation, 5:345–395, 2013

    2013

  15. [23]

    A heuristic to genera te rank-1 gmi cuts

    Sanjeeb Dash and Marcos Goycoolea. A heuristic to genera te rank-1 gmi cuts. Mathematical Programming Computation, 2(3-4):231–257, 2010

    2010

  16. [24]

    Mir closure s of polyhedral sets

    Sanjeeb Dash, Oktay Günlük, and Andrea Lodi. Mir closure s of polyhedral sets. Mathematical Programming, 121:33–60, 2010

    2010

  17. [25]

    On the pol yhedrality of cross and quadrilateral closures

    Sanjeeb Dash, Oktay Günlük, and Diego A Morán R. On the pol yhedrality of cross and quadrilateral closures. Mathematical Programming, 160:245–270, 2016

    2016

  18. [26]

    Theoretical challenge s towards cutting-plane selection

    Santanu S Dey and Marco Molinaro. Theoretical challenge s towards cutting-plane selection. Mathematical Programming, 170:237–266, 2018

    2018

  19. [27]

    Machine learning for cutt ing planes in integer programming: A survey

    Arnaud Deza and Elias B Khalil. Machine learning for cutt ing planes in integer programming: A survey. arXiv preprint arXiv:2302.09166 , 2023

    2023 arXiv

  20. [28]

    Differentiable cutting-plane layers for mixed-integer lin ear optimization

    Gabriele Dragotto, Stefan Clarke, Jaime Fernández Fisa c, and Bartolomeo Stellato. Differentiable cutting-plane layers for mixed-integer lin ear optimization. arXiv preprint arXiv:2311.03350, 2023

    2023 arXiv

  21. [29]

    A relax-and-c ut framework for gomory mixed-integer cuts

    Matteo Fischetti and Domenico Salvagnin. A relax-and-c ut framework for gomory mixed-integer cuts. Mathematical Programming Computation , 3:79–102, 2011

    2011

  22. [30]

    Approximatin g the split closure

    Matteo Fischetti and Domenico Salvagnin. Approximatin g the split closure. IN- FORMS Journal on Computing , 25(4):808–819, 2013

    2013

  23. [31]

    Miplib 2017: data-driven compilation of t he 6th mixed-integer programming library

    Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, et al. Miplib 2017: data-driven compilation of t he 6th mixed-integer programming library. Mathematical Programmin...

    2017

  24. [32]

    An Algorithm for the Mixed Integer Problem: Notes Linear Programming and Extens ions-Part 54

    Ralph Gomory and RAND CORP SANTA MONICA CA. An Algorithm for the Mixed Integer Problem: Notes Linear Programming and Extens ions-Part 54 . Rand, 1960

    1960

  25. [33]

    An algorithm for integer solutions to lin ear programs

    Ralph E Gomory. An algorithm for integer solutions to lin ear programs. Recent advances in mathematical programming , 64(260-302):14, 1963

    1963

  26. [34]

    Machine learning for optimization-based separation: the case of mi xed-integer rounding cuts

    Oscar Guaje, Arnaud Deza, Aleksandr M Kazachkov, and Eli as B Khalil. Machine learning for optimization-based separation: the case of mi xed-integer rounding cuts. arXiv preprint arXiv:2408.08449 , 2024. Approximating GMIC Closure Using Historical Data 15

    2024 arXiv

  27. [35]

    Hybrid models for learning to branch

    Prateek Gupta, Maxime Gasse, Elias Khalil, Pawan Mudigo nda, Andrea Lodi, and Yoshua Bengio. Hybrid models for learning to branch. Advances in neural information processing systems , 33:18087–18097, 2020

    2020

  28. [36]

    Learning to select cu ts for efficient mixed-integer programming

    Zeren Huang, Kerong Wang, Furui Liu, Hui-Ling Zhen, Wein an Zhang, Mingxuan Yuan, Jianye Hao, Yong Yu, and Jun Wang. Learning to select cu ts for efficient mixed-integer programming. Pattern Recognition, 123:108353, 2022

    2022

  29. [37]

    A k- nearest neighbor heuristic for real-time dc optimal transm ission switching

    Emma S Johnson, Shabbir Ahmed, Santanu S Dey, and Jean-Pa ul Watson. A k- nearest neighbor heuristic for real-time dc optimal transm ission switching. arXiv preprint arXiv:2003.10565, 2020

    2003 arXiv

  30. [38]

    A cycle-based formulation and valid inequaliti es for dc power trans- mission problems with switching

    Burak Kocuk, Hyemin Jeon, Santanu S Dey, Jeff Linderoth, J ames Luedtke, and Xu Andy Sun. A cycle-based formulation and valid inequaliti es for dc power trans- mission problems with switching. Operations Research, 64(4):922–938, 2016

    2016

  31. [39]

    On the np-hardness of deciding emptiness of t he split closure of a rational polytope in the 0, 1 hypercube

    Dabeen Lee. On the np-hardness of deciding emptiness of t he split closure of a rational polytope in the 0, 1 hypercube. Discrete Optimization , 32:11–18, 2019

    2019

  32. [40]

    Aggregation and m ixed integer round- ing to solve mips

    Hugues Marchand and Laurence A Wolsey. Aggregation and m ixed integer round- ing to solve mips. Operations research, 49(3):363–371, 2001

    2001

  33. [41]

    Solving mixed integer programs using n eural networks

    Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Gl ehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christi an Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using n eural networks. arXiv preprint arXiv:2012.13349 , 2020

    2012 arXiv

  34. [42]

    A recursive pro cedure to generate all cuts for 0–1 mixed integer programs

    George L Nemhauser and Laurence A Wolsey. A recursive pro cedure to generate all cuts for 0–1 mixed integer programs. Mathematical Programming, 46(1):379–390, 1990

    1990

  35. [43]

    Learning to cut by looking ahead: Cutting plane se lection via imitation learning

    Max B Paulus, Giulia Zarpellon, Andreas Krause, Laurent Charlin, and Chris Maddison. Learning to cut by looking ahead: Cutting plane se lection via imitation learning. In International conference on machine learning , pages 17584–17600. PMLR, 2022

    2022

  36. [44]

    The group-the oretic approach in mixed integer programming

    Jean-Philippe P Richard and Santanu S Dey. The group-the oretic approach in mixed integer programming. 50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art , pages 727–801, 2010

    1958

  37. [45]

    Álinson Santos Xavier, Feng Qiu, Xiaoyi Gu, Berkay Becu, and Santanu S. Dey. MI- PLearn: An Extensible Framework for Learning- Enhanced Opt imization, February 2024

    2024

  38. [46]

    Theory of linear and integer programming

    Alexander Schrijver. Theory of linear and integer programming . John Wiley & Sons, 1998

    1998

  39. [47]

    Reinforce ment learning for integer programming: Learning to cut

    Yunhao Tang, Shipra Agrawal, and Yuri Faenza. Reinforce ment learning for integer programming: Learning to cut. In International conference on machine learning , pages 9367–9376. PMLR, 2020

    2020

  40. [48]

    Adaptive cut selection in mixed-integer linear programming

    Mark Turner, Thorsten Koch, Felipe Serrano, and Michael Winkler. Adaptive cut selection in mixed-integer linear programming. arXiv preprint arXiv:2202.10962 , 2022

    2022 arXiv

  41. [49]

    A constructive characterization of t he split closure of a mixed integer linear program

    Juan Pablo Vielma. A constructive characterization of t he split closure of a mixed integer linear program. Operations Research Letters, 35(1):29–35, 2007

    2007

  42. [50]

    Learning cut selection for mixed-in teger linear pro- gramming via hierarchical sequence model

    Zhihai Wang, Xijun Li, Jie Wang, Yufei Kuang, Mingxuan Yu an, Jia Zeng, Yong- dong Zhang, and Feng Wu. Learning cut selection for mixed-in teger linear pro- gramming via hierarchical sequence model. arXiv preprint arXiv:2302.00244 , 2023

    2023 arXiv

  43. [51]

    The b-hull of an integer program

    Laurence A Wolsey. The b-hull of an integer program. Discrete Applied Mathe- matics, 3(3):193–201, 1981

    1981

  44. [52]

    Learning t o solve large-scale security-constrained unit commitment problems

    Álinson S Xavier, Feng Qiu, and Shabbir Ahmed. Learning t o solve large-scale security-constrained unit commitment problems. INFORMS Journal on Comput- ing, 33(2):739–756, 2021. 16 Becu, Dey, Qiu & Xavier

    2021

  45. [53]

    Exploiting instance an d variable similarity to improve learning-enhanced branching

    Gu Xiaoyi, S Dey, ÁS Xavier, et al. Exploiting instance an d variable similarity to improve learning-enhanced branching. arXiv, 2022. A Proofs Given a vector u∈ Rk, let u+,u −∈ Rk + be the vectors defined as: u+ i = { ui if ui≥ 0 0 if ui≤ 0. u− i = {−ui if ui< 0 0 if ui≥ 0. Giv...

    2022

  46. [54]

    Letc⊤x be the objective function of our IP

    Assuming we have already visited basis B1,...,B k, we have thus collected and retained the cuts in the set ⋃ k l=1 C(Bl). Letc⊤x be the objective function of our IP. We solve the LP where we add all these GMICs, that is w e solve: minc⊤x Ax =b,x≥ 0, (αj Bl )⊤x≥αj 0Bl∀j = 1,......

  47. [55]

    We now construct the following Lagrangian relaxation to the previous LP: minc⊤x + ∑ l∈[k] ∑ j∈q(Bl)uj Bl(αj 0Bl− (αj Bl )⊤x) Ax =b,x≥ 0

    Let uj Bl be an optimal dual solution of the above LP corresponding to t he constraint (αj Bl)⊤x ≥ αj 0Bl . We now construct the following Lagrangian relaxation to the previous LP: minc⊤x + ∑ l∈[k] ∑ j∈q(Bl)uj Bl(αj 0Bl− (αj Bl )⊤x) Ax =b,x≥ 0. (10) Notice that the optimal obj...

  48. [56]

    We collect a subset of GMICs corresponding to this optimal tableaux, call these cu tsC(Bk+1)

    We solve (10), and let Bk+1 be the optimal basis. We collect a subset of GMICs corresponding to this optimal tableaux, call these cu tsC(Bk+1). See details of which cuts are collected from a tableaux below. Fo r cuts selected from the previously visited basis, we discard those...

  49. [57]

    Rule 3 perturbs the right-hand-side multiplicatively since the constraint is in inequality for m

    Prevent integer infeasibility to occur locally at the con straint level as far as possible: Rule 1 and Rule 2 perturb the right-hand-side multiplicatively since a continuous variable is present. Rule 3 perturbs the right-hand-side multiplicatively since the constraint is in in...

  50. [58]

    Step 2: Checking the preliminary right-hand-side changes

    Preserve typical combinatorial constraints: special st ructures such as set par- titioning, set covering, and set packing constraints are no t changed; see Rule 3 and Rule 4 . Step 2: Checking the preliminary right-hand-side changes. The perturbations in the previous step may ...

  51. [59]

    In this case, we cannot make any right-hand-side changes to t his MIPLIB instance

    Firstly, none of the constraints satisfy the requirement s of Rules 1 -Rule 4 . In this case, we cannot make any right-hand-side changes to t his MIPLIB instance

  52. [60]

    We, then check if these per- turbations are integer feasible using Gurobi

    Otherwise, we generate 5 random perturbations. We, then check if these per- turbations are integer feasible using Gurobi. If any pertur bation is infeasible, then we do not make any right-hand-side changes to this MIPLI B instance. 24 Becu, Dey, Qiu & Xavier Objective changes....

    2017

Pith tools

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