Pith. sign in

REVIEW 3 major objections 4 minor 49 references

Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming

T0 review · 3 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

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

Pith's one-line read This paper proves that branch-and-cut policies whose decisions are scored by piecewise polynomial functions, including ReLU neural networks, have explicit sample-complexity guarantees because the overall cost is a piecewise constant…

desk verdict ReLU policy bounds for branch-and-cut are a genuine extension, but a reversed inequality in Lemma B.2 inflates the stated constant; asymptotic bounds survive, so the paper merits review with a required fix. read the letter →

arxiv 2505.11636 v1 pith:3COD6MQZ submitted 2025-05-16 cs.LG math.OC

Hongyu Cheng , Amitabh Basu This is my paper · ORCID
classification cs.LGmath.OC MSC 68Q3290C1190C10
keywords branch-and-cutintegerprogramminggeneralizationboundssamplecomplexitypseudo-dimensionpiecewisepolynomialfunctionsReLUneuralnetworkssequentialdecisionmaking
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 establishes a worst-case generalization theory for learned branch-and-cut policies. Its central claim is that when the scoring functions guiding node selection, cut selection, and branching are piecewise polynomial in the policy parameters—a class covering both linear score rules and ReLU networks—the overall performance metric, such as the size of the branch-and-cut tree, is a piecewise constant function of the parameters. From that structure the paper derives pseudo-dimension bounds and sample-complexity guarantees that grow only logarithmically with the number of available actions and with the size of the network. A separate data-dependent bound replaces worst-case action counts with the number of state-action pairs actually observed, which can be much smaller. The argument is carried out in a general sequential decision framework, so the bounds apply beyond branch-and-cut.

What carries the argument

The load-bearing object is the $(\Gamma,\gamma,\beta)$-structure of a function class: any $N$ functions from the class partition their common domain into at most $N^\gamma\Gamma$ regions, and on each region every function is a fixed polynomial of degree at most $\beta$. The paper shows that this local polynomial behaviour is preserved through the greedy action-selection loop of Algorithm 2: comparing scores at each state only requires fixing the sign of polynomial differences, so the whole trajectory of states and actions—and hence the accumulated cost—is constant on the cells of a refined partition. The count of cells is kept finite by bounding the number of distinct state-action pairs encountered, $\rho_k\bar{\rho}^M$ per instance, and by applying a standard sign-pattern bound for polynomials. A supporting lemma shows that multilayer perceptrons with piecewise polynomial activations, including ReLU, have this structure with explicit constants.

What would settle it

A concrete way to test the central claim is to construct a mixed-integer programming family in which the set of candidate cuts at some state is not bounded by any constant $\rho_2$ and to check whether a single linear scoring weight already shatters an arbitrarily large labelled set; if the sign-pattern count grows faster than the bound permits, the piecewise-constant conclusion fails. For the bounded-action version, one can compute the pseudo-dimension of a small ReLU-scored policy by exhaustive enumeration of sign patterns and compare it with Proposition 3.8's bound.

Watch

Extended reading notes

Core claim

The central discovery is Theorem 3.3: if each scoring function class $\mathcal{F}^*_k$ has a $(\Gamma_k,\gamma_k,\beta_k)$-structure—meaning any finite collection of scoring functions partitions the parameter space into at most $N^{\gamma_k}\Gamma_k$ regions inside which each function is a fixed polynomial of degree at most $\beta_k$—then the dual class of cost functions $\mathcal{V}^*$ has a $(\Gamma',\gamma',0)$-structure: the entire cost is piecewise constant on the parameter space. Combined with a sign-pattern counting bound, this yields pseudo-dimension bounds such as $O((\sum_k L_k W_k)(M\sum_k \log\rho_k + \log(\sum_k U_k)))$ for ReLU multilayer perceptron policies, where $L_k,W_k,U_k$ are the depth, parameter count, and neuron count for decision type $k$, $M$ is the maximum number of rounds, and $\rho_k$ bounds the number of available actions per state. The paper also gives an empirical Rademacher complexity bound in Proposition 3.9 that depends on the observed total number of distinct state-action pairs rather than the worst-case $\rho_k\bar{\rho}^M$.

Load-bearing premise

The load-bearing premise is that branch-and-cut really is the sequential decision process of Algorithm 2 with a uniformly bounded number of available actions at every state; in a real solver the set of candidate cuts can be large or unbounded, and if it is, the counting arguments behind the pseudo-dimension bounds no longer apply.

Editorial extensions

If this is right

  • For a fixed policy class, the number of training instances needed for uniform convergence grows only logarithmically with the number of candidate cuts, nodes, or branching variables per state.
  • Learning a ReLU-scored cut-selection policy under root-only cutting has pseudo-dimension $O(L_2W_2(\kappa R\log r + \log U_2))$, so sample complexity stays polynomial in network size and logarithmic in the cut-pool size.
  • Tuning node, cut, and branching policies simultaneously with three ReLU networks yields pseudo-dimension $O((L_1W_1+L_2W_2+L_3W_3)(M(\log(m+M)+\log n)+\log(U_1+U_2+U_3)))$ for the branch-and-cut tree size.
  • When the search terminates early, the Rademacher bound can be dramatically smaller than the pseudo-dimension bound because it uses the observed number of distinct state-action pairs instead of the worst-case $\rho_k\bar{\rho}^M$.
  • Because the argument is stated for any sequential decision process satisfying the structural assumptions, the same sample-complexity guarantees cover learned policies for other iterative algorithms, not only branch-and-cut.

Reading between the lines

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

  • Editorial inference: the same machinery should extend to learned tie-breaking rules, primal heuristics, or presolve decisions whenever their scores are piecewise polynomial, because only the form of the score and the bounded-action assumption are used.
  • Editorial inference: the worst-case dependence on the maximum number of rounds $M$ suggests that for long-running searches the sample requirement grows linearly in tree depth; measuring the actual number of distinct state-action pairs on a benchmark distribution is a cheap way to know whether the tighter Rademacher bound applies.
  • Editorial inference: a practical test of the theory would be to train a small ReLU cut-scoring policy on mixed-integer instances, record $Q_{M,k}(I)$ on held-out instances, and verify that the uniform-convergence rate tracks the square root of the observed state-action count rather than the worst-case bound.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. This paper develops a general framework for sample-complexity bounds in sequential decision processes, with a focus on branch-and-cut (B&C) policies for integer programming. It formalizes a (Gamma, gamma, beta)-structure for classes of parameterized scoring functions and proves, in Theorem 3.3, that if each scoring class has such a structure and the available action sets are uniformly bounded by rho_k, then the dual class of the overall cost function has a (Gamma', gamma', 0)-structure, meaning the cost is piecewise constant in the parameters. Combining this with a pseudo-dimension bound (Lemma 3.2) yields sample-complexity guarantees. The framework covers linear scoring policies and, via Lemma 3.7, ReLU/MLP policies, giving bounds such as Pdim = O((sum L_k W_k)(M sum log rho_k + log(sum U_k))). The paper also gives an empirical-Rademacher-complexity bound that depends on the actual number of encountered state-action pairs (Proposition 3.9), and applies the results to branch-and-cut tree size in Section 4.

Significance. If the proofs are correct, this is a valuable contribution to the theory of data-driven algorithm design. It extends the earlier linear-scoring analyses by Balcan et al. to a broader piecewise-polynomial class that includes the ReLU networks used in practice, and it provides a clean structural condition for when the induced cost function is piecewise constant. The empirical Rademacher bound is a useful data-dependent complement to the worst-case pseudo-dimension bounds. The paper also carefully situates its results relative to prior work. However, the proof of the central Lemma B.2 contains a reversed inequality that affects the stated constants of Theorem 3.3; this is fixable and the asymptotic bounds appear to survive, but the current manuscript does not support its exact claims as written.

major comments (3)
  1. [Appendix B, Lemma B.2 and Theorem 3.3] The proof of Lemma B.2 contains a reversed inequality. It states that the number of relevant states is bounded by |Delta_k| <= ~Q_{M,k}/rho_k, writing ~Q_{M,k}/rho_k as sum_i Q_{M,k}(I_i)/rho_k. Since each state in Delta_k contributes at least one distinct type-k state-action pair, the correct bound is |Delta_k| <= ~Q_{M,k}; in fact, each state can contribute up to rho_k pairs, so ~Q_{M,k} <= rho_k|Delta_k|. Consequently, the number of score-difference polynomials is at most ~Q_{M,k} rho_k^2/2, not ~Q_{M,k} rho_k/2. This changes Lemma B.2's bound and, when substituted into Theorem 3.3, makes the displayed Gamma' too small by an extra factor of prod_k rho_k^{W_k} (equivalently, the aggregate term becomes (e sum_k rho_k^3 beta_k / W)^W instead of (e sum_k rho_k^2 beta_k / W)^W). The proof as written does not support the stated Gamma'. The asymptotic pseudo-dimension claims in Propositions 3.4 and 3.8 appear to survive, because the extra W sum_k log rho_k is absorbed into the leading O(WM sum log rho_k) term, but the exact statements of Lemma B.2, Theorem 3.3, and Proposition 3.9 need to be corrected.
  2. [Appendix B, Lemma B.2] The proof applies Definition 3.1 to the collection of functions f_k(s,a,.) indexed by all distinct state-action pairs, asserting that its cardinality is at most ~Q_{M,k} and that ~Q_{M,k} >= N >= gamma_k. This inequality is not justified: ~Q_{M,k} = sum_i Q_{M,k}(I_i) can be smaller than N when some instances never take a type-k action, or when state-action pairs recur across instances. If ~Q_{M,k} < gamma_k, the (Gamma_k, gamma_k, beta_k)-structure does not directly give the claimed partition bound. A separate argument is needed for this small-count case, or the condition on N should be reworked.
  3. [Section 3.1, after Definition 3.1] The uniform bound |A^s_k| <= rho_k is load-bearing for Lemma B.1, Theorem 3.3, and all downstream pseudo-dimension bounds. For cut selection in real branch-and-cut solvers, the set of candidate cuts can be large or unbounded (for example, the family of all Gomory mixed-integer cuts), so the results do not apply to that practically important setting. Section 4 restricts to a finite candidate pool (r = O(m + kappa R)), but the abstract and introduction make broader claims about learning B&C policies. The paper should state this limitation explicitly in the main text, not only in the future-work section.
minor comments (4)
  1. [Appendix B, Lemma B.2, Eq. (4)] In the display after Eq. (4), the definition 'where ~gamma = sum_{k=1}^d rho_k' is a typo; it should be '~gamma = sum_{k=1}^d gamma_k'.
  2. [Proposition 3.9 and Appendix C.2] Several displayed square-root formulas use malformed LaTeX (√ radicaltp, √ radicalvertex). These should be typeset correctly.
  3. [Appendix B, Lemma B.2] The notation ~Q_{M,k} is defined in the lemma statement, but the proof uses sum_i Q_{M,k}(I_i) without distinguishing the per-instance count Q_{M,k}(I_i) from the total; this should be made explicit for readability.
  4. [Remark 3.5] The claim that Proposition 3.4 improves on the bound of Balcan et al. [2021c] should be rechecked after the correction of Lemma B.2; the asymptotic improvement is preserved, but the constant-factor discussion should be updated.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: The main theorem derives piecewise-constant cost structure from assumed piecewise-polynomial scoring functions using external sign-counting lemmas, and the self-citations are contextual rather than load-bearing.

full rationale

The paper's central claim, Theorem 3.3, is not circular. Its assumption is that each scoring function class F*_k has a (Gamma_k, gamma_k, beta_k)-structure (Definition 3.1), a property of functions of the policy parameters. The conclusion is that the cost dual class V* has a (Gamma', gamma', 0)-structure, meaning the overall cost is piecewise constant in the parameters. The proof proceeds by partitioning each parameter space W_k using the assumed piecewise-polynomial structure, then bounding the number of sign patterns of polynomial differences via the external Lemma A.2 (Theorem 8.3 of Anthony et al.), not by assuming the conclusion. Lemma 3.2 is a standard pseudo-dimension bound proved from the same external polynomial sign-counting lemma. Lemma 3.7, which supplies the structure for MLPs, invokes an external theorem of Bartlett et al. (2019) with an explicit mapping of depth, width, activation degree, and neuron count to the structural parameters; this is independent support, not a self-citation. The self-citations to Cheng et al. (2024) and Cheng and Basu (2024) appear only in the related-work survey and are not used to justify Theorem 3.3, Proposition 3.4, or Proposition 3.8. There are no fitted parameters renamed as predictions, no uniqueness theorem imported from the authors' prior work, and no ansatz smuggled in via citation. The skeptical note about Lemma B.2 concerns a possible reversed inequality affecting the constants in the counting argument; even if correct, that is a proof-technical correctness issue, not circularity. The derivation chain is therefore self-contained apart from standard external lemmas, and the circularity score is 0.

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

No free parameters are fitted; the paper is purely analytical. The central claim rests on standard results from the theory of sign patterns of polynomials and on modeling assumptions that branch-and-cut is a sequential decision process with bounded action sets and fixed feature extractors.

assumptions (5)
  • standard math Standard PAC-learning uniform convergence bounds relating pseudo-dimension to sample complexity (e.g., Eq. (1), Anthony et al. 1999).
    Used to convert pseudo-dimension bounds into sample complexity guarantees.
  • standard math Existing results on the number of sign patterns of polynomials (Lemma A.2, Anthony et al. 1999).
    Core counting tool in Lemma B.2 and Lemma 3.2.
  • standard math Piecewise polynomial structure of MLPs with piecewise polynomial activations (Lemma 3.7, building on Bartlett et al. 2019).
    External theorem imported to establish (Gamma, gamma, beta)-structure for ReLU networks.
  • domain assumption The sequential decision process (Algorithm 2) faithfully models branch-and-cut, with at most M rounds and uniformly bounded action sets of size rho_k.
    This is the bridge from the general framework to integer programming; if real B&C has unbounded cut pools or backtracking behavior outside this model, the application of the bounds is not justified.
  • domain assumption Fixed feature extractors phi_k are given and not learned.
    The framework requires a fixed mapping from (s,a) to feature vectors; end-to-end feature learning is outside the analysis.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming." pith.science (2026). https://pith.science/paper/3COD6MQZ

@misc{pith2026250511636,
  author       = {Pith},
  title        = {Pith review of: Generalization Guarantees for Learning Branch-and-Cut Policies in Integer Programming},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3COD6MQZ}},
  note         = {Machine review of arXiv:2505.11636}
}
read the original abstract

Mixed-integer programming (MIP) provides a powerful framework for optimization problems, with Branch-and-Cut (B&C) being the predominant algorithm in state-of-the-art solvers. The efficiency of B&C critically depends on heuristic policies for making sequential decisions, including node selection, cut selection, and branching variable selection. While traditional solvers often employ heuristics with manually tuned parameters, recent approaches increasingly leverage machine learning, especially neural networks, to learn these policies directly from data. A key challenge is to understand the theoretical underpinnings of these learned policies, particularly their generalization performance from finite data. This paper establishes rigorous sample complexity bounds for learning B&C policies where the scoring functions guiding each decision step (node, cut, branch) have a certain piecewise polynomial structure. This structure generalizes the linear models that form the most commonly deployed policies in practice and investigated recently in a foundational series of theoretical works by Balcan et al. Such piecewise polynomial policies also cover the neural network architectures (e.g., using ReLU activations) that have been the focal point of contemporary practical studies. Consequently, our theoretical framework closely reflects the models utilized by practitioners investigating machine learning within B&C, offering a unifying perspective relevant to both established theory and modern empirical research in this area. Furthermore, our theory applies to quite general sequential decision making problems beyond B&C.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

49 extracted references · 30 canonical work pages

  1. [1]

    Constraint integer programming

    Tobias Achterberg. Constraint integer programming. 2007

    2007

  2. [2]

    Scip: solving constraint integer programs

    Tobias Achterberg. Scip: solving constraint integer programs. Mathematical Programming Computation, 1: 0 1--41, 2009

    work page 2009

  3. [3]

    Branching rules revisited

    Tobias Achterberg, Thorsten Koch, and Alexander Martin. Branching rules revisited. Operations Research Letters, 33 0 (1): 0 42--54, 2005

    work page 2005

  4. [4]

    A machine learning-based approximation of strong branching

    Alejandro Marcos Alvarez, Quentin Louveaux, and Louis Wehenkel. A machine learning-based approximation of strong branching. INFORMS Journal on Computing, 29 0 (1): 0 185--195, 2017

    work page 2017

  5. [5]

    Neural network learning: Theoretical foundations, volume 9

    Martin Anthony, Peter L Bartlett, Peter L Bartlett, et al. Neural network learning: Theoretical foundations, volume 9. Cambridge: Cambridge University Press, 1999

    work page 1999

  6. [6]

    Data-driven algirithm design

    Maria-Florina Balcan. Data-driven algirithm design. In Tim Roughgarden, editor, Beyond the Worst Case Analysis of Algorithms. Cambridge University Press, 2020

    work page 2020

  7. [7]

    Learning accurate and interpretable decision trees

    Maria-Florina Balcan and Dravyansh Sharma. Learning accurate and interpretable decision trees. arXiv preprint arXiv:2405.15911, 2024

    arXiv 2024

  8. [8]

    Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems

    Maria-Florina Balcan, Vaishnavh Nagarajan, Ellen Vitercik, and Colin White. Learning-theoretic foundations of algorithm configuration for combinatorial partitioning problems. In Conference on Learning Theory, pages 213--274. PMLR, 2017

    2017

Show all 49 references
  1. [9]

    Improved sample complexity bounds for branch-and-cut

    Maria-Florina Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Improved sample complexity bounds for branch-and-cut. arXiv preprint arXiv:2111.11207, 2021 a

    2021 arXiv

  2. [10]

    Generalization in portfolio-based algorithm selection

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization in portfolio-based algorithm selection. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12225--12232, 2021 b

    2021

  3. [11]

    How much data is sufficient to learn high-performing algorithms? J

    Maria-Florina Balcan, Dan Deblasio, Travis Dick, Carl Kingsford, Tuomas Sandholm, and Ellen Vitercik. How much data is sufficient to learn high-performing algorithms? J. ACM, 71 0 (5), October 2024 a . ISSN 0004-5411. doi:10.1145/3676278. URL https://doi.org/10.1145/3676278

    2024 doi

  4. [12]

    Learning to branch: Generalization guarantees and limits of data-independent discretization

    Maria-Florina Balcan, Travis Dick, Tuomas Sandholm, and Ellen Vitercik. Learning to branch: Generalization guarantees and limits of data-independent discretization. J. ACM, 71 0 (2), April 2024 b . ISSN 0004-5411. doi:10.1145/3637840. URL https://doi.org/10.1145/3637840

    2024 doi

  5. [13]

    Algorithm configuration for structured pfaffian settings

    Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Algorithm configuration for structured pfaffian settings. arXiv preprint arXiv:2409.04367, 2024 c

    2024 arXiv

  6. [14]

    Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function

    Maria-Florina Balcan, Anh Tuan Nguyen, and Dravyansh Sharma. Sample complexity of data-driven tuning of model hyperparameters in neural networks with structured parameter-dependent dual function. arXiv preprint arXiv:2501.13734, 2025 a

    2025 arXiv

  7. [15]

    Generalization guarantees for multi-item profit maximization: Pricing, auctions, and randomized mechanisms

    Maria-Florina Balcan, Tuomas Sandholm, and Ellen Vitercik. Generalization guarantees for multi-item profit maximization: Pricing, auctions, and randomized mechanisms. Operations Research, 73 0 (2): 0 648--663, 2025 b

    2025

  8. [16]

    Sample complexity of tree search configuration: Cutting planes and beyond

    Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Sample complexity of tree search configuration: Cutting planes and beyond. Advances in Neural Information Processing Systems, 34: 0 4015--4027, 2021 c

    2021

  9. [17]

    Provably tuning the E lastic N et across instances

    Maria-Florina F Balcan, Misha Khodak, Dravyansh Sharma, and Ameet Talwalkar. Provably tuning the E lastic N et across instances. Advances in Neural Information Processing Systems, 35: 0 27769--27782, 2022 a

    2022

  10. [18]

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

    Maria-Florina F Balcan, Siddharth Prasad, Tuomas Sandholm, and Ellen Vitercik. Structural analysis of branch-and-cut and the learnability of gomory mixed integer cuts. Advances in Neural Information Processing Systems, 35: 0 33890--33903, 2022 b

    2022

  11. [19]

    Generalization bounds for data-driven numerical linear algebra

    Peter Bartlett, Piotr Indyk, and Tal Wagner. Generalization bounds for data-driven numerical linear algebra. In Conference on Learning Theory, pages 2013--2040. PMLR, 2022

    2013

  12. [20]

    Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks

    Peter L Bartlett, Nick Harvey, Christopher Liaw, and Abbas Mehrabian. Nearly-tight vc-dimension and pseudodimension bounds for piecewise linear neural networks. The Journal of Machine Learning Research, 20 0 (1): 0 2285--2301, 2019

    2019

  13. [21]

    A geometric approach to cut-generating functions

    Amitabh Basu, Michele Conforti, and Marco Di Summa. A geometric approach to cut-generating functions. Mathematical Programming, 151: 0 153--189, 2015

    2015

  14. [22]

    Learning cut generating functions for integer programming

    Hongyu Cheng and Amitabh Basu. Learning cut generating functions for integer programming. Advances in Neural Information Processing Systems, 37: 0 61455--61480, 2024

    2024

  15. [23]

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

    Hongyu Cheng, Sammy Khalife, Barbara Fiedorowicz, and Amitabh Basu. Sample complexity of algorithm selection using neural networks and its applications to branch-and-cut. Advances in Neural Information Processing Systems, 37: 0 25036--25060, 2024

    2024

  16. [24]

    Integer programming, volume 271

    Michele Conforti, G \'e rard Cornu \'e jols, and Giacomo Zambelli. Integer programming, volume 271. Springer, 2014

    2014

  17. [25]

    Cutting planes from the branch-and-bound tree: Challenges and opportunities

    Claudio Contardo, Andrea Lodi, and Andrea Tramontani. Cutting planes from the branch-and-bound tree: Challenges and opportunities. INFORMS Journal on Computing, 35 0 (1): 0 2--4, 2023

    2023

  18. [26]

    u t \"u nc \

    Gerard Cornuejols, Javier Pe \ n a, and Reha T \"u t \"u nc \"u . Optimization methods in finance. Cambridge University Press, 2018

    2018

  19. [27]

    The scip optimization suite 7.0

    Gerald Gamrath, Daniel Anderson, Ksenia Bestuzheva, Wei-Kun Chen, Leon Eifler, Maxime Gasse, Patrick Gemander, Ambros Gleixner, Leona Gottwald, Katrin Halbig, et al. The scip optimization suite 7.0. 2020

    2020

  20. [28]

    Exact combinatorial optimization with graph convolutional neural networks

    Maxime Gasse, Didier Ch \'e telat, Nicola Ferroni, Laurent Charlin, and Andrea Lodi. Exact combinatorial optimization with graph convolutional neural networks. Advances in neural information processing systems, 32, 2019

    2019

  21. [29]

    Extremely randomized trees

    Pierre Geurts, Damien Ernst, and Louis Wehenkel. Extremely randomized trees. Machine learning, 63: 0 3--42, 2006

    2006

  22. [30]

    A pac approach to application-specific algorithm selection

    Rishi Gupta and Tim Roughgarden. A pac approach to application-specific algorithm selection. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, pages 123--134, 2016

    2016

  23. [31]

    Integer linear programming in computational and systems biology: an entry-level text and course

    Dan Gusfield. Integer linear programming in computational and systems biology: an entry-level text and course. Cambridge University Press, 2019

    2019

  24. [32]

    Learning to search in branch and bound algorithms

    He He, Hal Daum\' e , and Jason Eisner. Learning to search in branch and bound algorithms. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger, editors, Advances in Neural Information Processing Systems, volume 27. Curran Associates, Inc., 2014

    2014

  25. [33]

    Learning to select cuts for efficient mixed-integer programming

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

    2022

  26. [34]

    Learning complexity of gradient descent and conjugate gradient algorithms

    Xianqi Jiao, Jia Liu, and Zhiping Chen. Learning complexity of gradient descent and conjugate gradient algorithms. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 17671--17679, 2025

    2025

  27. [35]

    50 Years of integer programming 1958-2008: From the early years to the state-of-the-art

    Michael J \"u nger, Thomas M Liebling, Denis Naddef, George L Nemhauser, William R Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, and Laurence A Wolsey. 50 Years of integer programming 1958-2008: From the early years to the state-of-the-art. Springer Science & Business Media, 2009

    1958

  28. [36]

    An abstract model for branch and cut

    Aleksandr M Kazachkov, Pierre Le Bodic, and Sriram Sankaranarayanan. An abstract model for branch and cut. Mathematical Programming, 206 0 (1): 0 175--202, 2024

    2024

  29. [37]

    Design of survivable networks: A survey

    Herv \'e Kerivin and A Ridha Mahjoub. Design of survivable networks: A survey. Networks: An International Journal, 46 0 (1): 0 1--21, 2005

    2005

  30. [38]

    Learning to branch in mixed integer programming

    Elias Khalil, Pierre Le Bodic, Le Song, George Nemhauser, and Bistra Dilkina. Learning to branch in mixed integer programming. In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016

    2016

  31. [39]

    A computational study of search strategies for mixed integer programming

    Jeff T Linderoth and Martin WP Savelsbergh. A computational study of search strategies for mixed integer programming. INFORMS Journal on Computing, 11 0 (2): 0 173--187, 1999

    1999

  32. [40]

    Foundations of Machine Learning

    Mehryar Mohri, Afshin Rostamizadeh, and Ameet Talwalkar. Foundations of Machine Learning. The MIT Press, 2018. Second Edition

    2018

  33. [41]

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

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

    2022

  34. [42]

    Production planning by mixed integer programming, volume 149

    Yves Pochet and Laurence A Wolsey. Production planning by mixed integer programming, volume 149. Springer, 2006

    2006

  35. [43]

    Sample complexity of learning heuristic functions for greedy-best-first and A * search

    Shinsaku Sakaue and Taihei Oki. Sample complexity of learning heuristic functions for greedy-best-first and A * search. Advances in Neural Information Processing Systems, 35: 0 2889--2901, 2022

    2022

  36. [44]

    Generalization bound and learning methods for data-driven projections in linear programming

    Shinsaku Sakaue and Taihei Oki. Generalization bound and learning methods for data-driven projections in linear programming. Advances in Neural Information Processing Systems, 37: 0 12825--12846, 2024

    2024

  37. [45]

    Understanding machine learning: From theory to algorithms

    Shai Shalev-Shwartz and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014

    2014

  38. [46]

    Reinforcement learning for integer programming: Learning to cut

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

    2020

  39. [47]

    Vehicle routing: problems, methods, and applications

    Paolo Toth and Daniele Vigo. Vehicle routing: problems, methods, and applications. SIAM, 2014

    2014

  40. [48]

    Implementing cutting plane management and selection techniques

    Franz Wesselmann and Uwe Stuhl. Implementing cutting plane management and selection techniques. In Technical Report. University of Paderborn, 2012

    2012

  41. [49]

    A study of learning search approximation in mixed integer branch and bound: Node selection in scip

    Kaan Yilmaz and Neil Yorke-Smith. A study of learning search approximation in mixed integer branch and bound: Node selection in scip. Ai, 2 0 (2): 0 150--178, 2021

    2021

Pith tools

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