Pith. sign in

REVIEW 4 major objections 5 minor 42 references

Improving Full Strong Branching Decisions by Incorporating Additional Information

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

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

Pith's one-line read Capping LP gains at the primal-dual gap and reweighting the product score toward the harder 0-or-1 side shrinks full strong branching trees by 22–35 percent on benchmark instances, and the same corrections transfer partially to…

desk verdict A genuinely sensible score correction and a clean tuning/test split, but the MIPLIB headline is built on 10 solved instances and one big outlier; with code and variance it would be a solid paper. read the letter →

arxiv 2507.09455 v1 pith:N3L52ZIX submitted 2025-07-13 math.OC

Prachi Shah , Santanu S. Dey This is my paper · ORCID
classification math.OC MSC 90C1090C11
keywords branch-and-boundfullstrongbranchingscoreefficaciousgainsprimalgapreliabilitymixed-integerprogrammingasymmetry
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 argues that full strong branching makes two correctable mistakes: it counts LP gain beyond the gap that actually needs closing, and it ignores whether fixing variables to 0 or to 1 more often leads to infeasibility or integrality deeper in the tree. The authors propose capping each child's LP gain at the current primal-dual gap ("efficacious gains") and reweighting the product score with exponents 0.3 and 0.7, then adding a multiplier that shifts weight toward the branch that is harder to prune. On a standard 51-instance benchmark set, their rules reduce mean tree size by 20–35% on solved instance–seed combinations and lower the mean remaining gap on unsolved ones by 3.6–5.6%. The same score corrections applied to reliability branching give smaller but consistent improvements, 5–13% on solved instances. The motivation is that FSB trees are often 25–75% larger than optimal trees, and simple imitable rules that close part of that gap can serve as expert policies for learning-based branching.

What carries the argument

The central object is a generalized product score that combines efficacious gains with an asymmetry exponent: score(i) = (q_{i,min})^{a_min} (q_{i,max})^{a_max} multiplied by (q_{i,0})^{a_0}(q_{i,1})^{a_1}. Here q_i^b = min(max(Delta_i^b, epsilon), $\Delta$^{p-d}) is the LP gain on branch b capped at the current primal-dual gap, and (a_0,a_1) come from the last-assignment rule: count, among leaves pruned for integrality or infeasibility, whether the final branching that created the leaf fixed the variable to 0 or 1, and set a_1 = eta(n0-n1)/(n0+n1) when 0-fixings dominate, or a_0 = -eta(n0-n1)/(n0+n1) when 1-fixings dominate. The pruning-aware variant switches to counting all leaves when fewer than 5% of leaves are integral or infeasible, which the paper finds balances the benefits of the two rules.

What would settle it

Randomize the last-assignment signal while keeping everything else: replace the counted n0/n1 leaf labels with random 0/1 labels of the same totals. If PA-LA-SB(3,7,0.15) still beats Def-SB by the same margin, the reported gains do not come from detecting real 0-versus-1 asymmetry.

Watch

Extended reading notes

Core claim

The central claim is that the product score used by full strong branching can be improved in two independent ways: replace raw LP gains with efficacious gains capped at the current primal-dual gap, and raise the exponent of the larger capped gain relative to the smaller one; then detect whether 0-fixings or 1-fixings are globally more likely to finish the tree by pruning, and raise the exponent on the branch that is harder to finish. Implemented as Eff-SB(3,7) and PA-LA-SB(3,7,0.15), with exponents (a_min,a_max)=(0.3,0.7), last-assignment weight eta=0.15, and a pruning-aware switch at 5% integral-or-infeasible leaves, these scores reduce solved-instance mean tree sizes by 35.4%, 27.8%, 23.1%, and 20.5% at 0%, 2%, 5%, and 10% starting primal gaps while also reducing mean remaining gap on unsolved instances. The same cap-and-reweight idea applied to pseudocost-estimated gains in reliability branching reduces solved-instance mean tree sizes by 5.3–13.2%.

Load-bearing premise

The last-assignment rule assumes that the same 0-versus-1 asymmetry seen at leaf nodes applies uniformly to every candidate variable at the next branching decision; the paper states in Section 6 that this requires variables to be similar, which fails on general instances with mixed coefficient signs and heterogeneous variables.

Editorial extensions

If this is right

  • With an optimal primal bound, Eff-SB(3,7) cuts mean FSB tree size by 35.4% on solved benchmark instances; the improvement remains 20.5% even with a 10% starting primal gap.
  • PA-LA-SB(3,7,0.15) is the more robust variant: it reduces solved-instance mean tree sizes by 22.8–35.3% across the four starting gaps and lowers mean remaining gap on unsolved instances by 3.6–5.6%.
  • Applying the same cap-and-reweight idea to pseudocost-based reliability branching gives 5.3–13.2% smaller solved-instance trees with PA-LA-RB and 2.6–4.3% lower remaining gap on unsolved instances.
  • Better primal bounds amplify the gains: the LP-gain correction matters most when the incumbent is near-optimal, while the last-assignment correction adds more when the starting gap is larger.
  • The proposed scores are algebraic changes to an existing score function, so they add no extra LP solves at branching time and can be folded into any solver's strong or reliability branching logic.

Reading between the lines

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

  • An implication not drawn by the paper: because the modified score is a closed-form function of already-computed gains, it can serve as a cheap supervised-learning target, giving imitation-branching policies a better expert than unmodified FSB.
  • The paper fixes its exponents by grid search on generated instances; a natural extension would predict (a_min,a_max) and the asymmetry weight eta per instance from features such as constraint-sign uniformity, potentially recovering part of the 3.5–5% extra gains the paper reports from per-problem-tuned exponents.
  • The last-assignment signal is aggregated globally, and the paper's own Section 6 caveat suggests tracking the same 0-versus-1 leaf counts per variable or per constraint family, which would likely help instances with heterogeneous variables.
  • Because the rebalancing variant uses all leaves rather than only integral or infeasible ones, the asymmetry idea is really about equalizing subtree effort; this could be connected to node-selection rules or effort-based search orders beyond branching scores.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 5 minor

Summary. The paper proposes two modifications to the full strong branching (FSB) score for binary MIPs: first, it caps LP gains by the additive primal-dual gap to form "efficacious gains" and reweights the product score (Section 2, Eqs. (2)-(4)); second, it detects global 0-versus-1 asymmetry using the last branching assignment before infeasible or integral leaves, adds asymmetric exponents to the score (Section 3, Algorithm 1, Eq. (6)), and combines this with a pruning-aware switch between LA-SB and R-LA-SB (Section 4.2). Parameters are tuned on 20 random instances of 14 structured problem classes and then evaluated on MIPLIB 2017 instances in a textbook best-bound-first branch-and-bound using Gurobi as the LP solver. The paper claims 20.5-35.4% mean tree-size reductions for Eff-SB(3,7) and PA-LA-SB(3,7,0.15) on solved MIPLIB instances, 3.6-5.6% lower mean remaining gap on unsolved instances, and, for PA-LA-RB, 13.2%, 4.4%, 5.2%, and 5.3% tree-size reductions at 0%, 2%, 5%, and 10% primal gaps.

Significance. If the MIPLIB claims hold, the paper would show that simple closed-form score modifications can substantially reduce FSB tree sizes and partially transfer to reliability branching, which is relevant both for branching-rule design and for machine-learning imitation of FSB. The strengths include the clear and correct overestimation argument in Example 1, the well-documented random testbed in Appendix D, the use of MIPLIB as an independent out-of-sample benchmark, and transparent reporting of the tuned parameter values. The main weaknesses are statistical: no code or per-seed data are provided, the solved-instance sample for MIPLIB is very small (10 instances for FSB, 8 for RB), and the aggregate improvements are not shown to be stable across instances. The random-instance results and the MIPLIB directional claims are plausible, but the headline percentages require stronger evidence.

major comments (4)
  1. [§5.1, Table 13] The MIPLIB aggregate is computed over a non-fixed set of instances, as the table footnote defines the node mean over instances solved for "some combination of rule, primal gap and seed", and only 10 instances are solved at all. At 10% primal gap, Eff-SB(3,7) is equal-or-worse than Def-SB on 6 of the 10 solved rows (dano3_3, dano3_5, map10, rmatr100-p10, seymour1, supportcase40), while app1-1 alone drops from 1679 to 42 nodes. Because no per-seed counts, confidence intervals, or leave-one-out statistics are reported, the claimed 20.5% mean reduction at 10% gap is not established as a stable property of the test set; the authors should report per-instance and per-seed values and compute the mean over the fixed set of instances solved by all rules at each gap.
  2. [§5.2, Table 14] The extension to reliability branching is not supported for non-optimal primal bounds: Eff-RB(3,7) increases mean tree sizes by 2.7%, 2.6%, and 0.7% at 2%, 5%, and 10% primal gaps relative to Def-RB, and the abstract's 5-13% RB improvement refers to PA-LA-RB, not to efficacious gains alone. The paper should separate the two mechanisms, present the per-instance RB table, and adjust the abstract's RB claim so that it is attributed to the rule that actually achieves the improvement.
  3. [§3.1, Algorithm 1; §6] The last-assignment rule's justification assumes that "all variables have the same coefficient sign" and that "the global trend in asymmetry can be applied to all candidate variables at the current node", as the paper itself acknowledges in Section 6. MIPLIB 2017 instances generally have mixed coefficient signs and heterogeneous variables, so this premise does not hold on the benchmark used for the headline numbers. Table 13 reports only Eff-SB and PA-LA-SB, so the incremental contribution of the last-assignment mechanism is not isolated on MIPLIB; the authors should report a head-to-head Eff-SB versus LA-SB/PA-LA-SB comparison on the solved MIPLIB instances together with the observed fraction of integral/infeasible leaves to show that the asymmetry mechanism is active and beneficial outside the random testbed.
  4. [§5.1, Tables 13-14] No code, no instance list, no seeds, and no per-seed node counts are provided, and the geometric mean of remaining gap is computed over the union of instances unsolved by "some combination" of rule and seed, which makes the 3.6-5.6% gap reduction difficult to interpret. At a minimum, the paper should identify the exact instance set per cell and the per-seed values, or provide a code/data artifact, so that the aggregate results can be independently checked.
minor comments (5)
  1. [Abstract vs. Introduction] The abstract reports 22-35% tree-size reductions on solved MIPLIB instances, while the final bullet of the Introduction reports "around 15-26%" for the same experiments; these numbers should be reconciled.
  2. [Table 14, row neos-5188808-nattai] The entries such as "18845(3.6%)" and "19230(15.8%)" mix node counts and gap percentages in a single cell without explaining the convention; the table footnote should define this notation.
  3. [§5.1] The paper excludes five instances that showed no change in dual bound after 20,000 nodes with any rule; these instances should be listed, and the paper should explain how their exclusion affects the reported aggregates.
  4. [Table 13 footnote] The footnote for the "Geo mean – Nodes" row does not state how instances with both solved and unsolved seeds are treated when computing the node mean; clarify whether they are included only if solved for all seeds or for any seed.
  5. [Appendix C, Eff-Card] The Eff-Card score uses an exponent divisor of 1/4 without tuning or sensitivity analysis; since this is presented as an illustrative extension, a sentence on its intended scope would help.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: parameters are tuned on a random testbed and validated on independent MIPLIB 2017; the main empirical claims do not reduce to fitted inputs by construction.

full rationale

The paper's central empirical claims are the MIPLIB 2017 results for Eff-SB(3,7) and PA-LA-SB(3,7,0.15). The parameters (a_min=0.3, a_max=0.7, eta=0.15) are selected using a separately generated random problem testbed (Tables 1-12 and Figures 1-6), and the MIPLIB evaluation in Section 5 is an independent benchmark set not used for tuning. The paper explicitly separates the two phases: 'Using randomly generated problem instances with known structures, we derive insights and fine-tune our modified scores. Evaluation on MIPLIB 2017 Benchmark instances shows...' (Abstract and Section 5). This is standard train/test separation, so the headline reductions (35.4%, 27.8%, 23.1%, 20.5% for Eff-SB; 35.3%, 28.3%, 25.3%, 22.8% for PA-LA-SB; and 5-13% for RB) are not fitted-on-the-test-data artifacts. The only self-referential elements are citations to the authors' prior work [14] and [40], which motivate tree size as the metric and the choice of best-bound-first node processing; these are contextual motivations, not load-bearing premises whose truth is assumed from the same paper without independent support. The last-assignment rule and the rebalancing extension are new constructions defined within the paper, and the 'asymmetry exponents' are computed from observed pruning statistics (Algorithm 1) rather than being fit to the MIPLIB outcomes. Concerns about statistical fragility (only 10 solved FSB instances, 8 for RB; the aggregate dominated by app1-1 and other outliers) are a matter of experimental robustness and significance testing, not circularity. The paper itself acknowledges limitations of the last-assignment rule in Section 6 ('the proposed approaches based on last assignments assume that variables are similar'), which further shows the derivation is not hiding a definitional equivalence. No equation in the paper defines a prediction as the same expression as an input parameter, and no load-bearing claim is justified solely by a self-citation whose content is unverified in the present work.

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

No new physical or mathematical entities are introduced. The central claim rests on tuned score parameters (a_min, a_max, eta, k_I, threshold, epsilon), on the heuristic assumption that leaf-level asymmetry statistics can be summarized by the last assignment, and on the assumption that primal-dual gap caps overestimated LP gains.

free parameters (7)
  • a_min exponent for efficacious product score = 0.3
    Selected by grid search over a_min in {0, 0.1, ..., 1} with a_max = 1 - a_min on the random testbed; yields the smallest geometric mean tree size (Section 2.2, Figure 1).
  • a_max exponent for efficacious product score = 0.7
    Complements a_min; tuned together with it in the same grid search.
  • eta scaling for last assignment exponents = 0.15
    Grid search over eta in {0.05, 0.1, 0.15, 0.2, 0.25}; selected because geometric mean tree size decreases to eta = 0.15 and does not improve afterwards (Section 3.2, Figure 3).
  • k_I minimum sample size for last assignment rule = 10
    Algorithm 1 uses the asymmetry statistics only when at least 10 infeasible or integral leaves are available; chosen by the authors without sensitivity analysis.
  • PA-LA threshold on fraction of integral/infeasible leaves = 5%
    Policy switch between LA-SB and R-LA-SB; motivated by the observation that problems with fewer than 2% integer/infeasible leaves favored R-LA and problems with more than 7% favored LA (Section 4.2).
  • epsilon floor in score functions = small positive (not reported)
    Used in Eq. (1) and all modified scores to avoid zero or negative scores; standard in the FSB literature but its value is not reported.
  • Eff-Card exponent divisor 1/4 = 1/4
    In Appendix C, the cardinality-based asymmetry exponents are set to f0/4 and f1/4; the factor 4 is chosen without derivation or sensitivity analysis.
assumptions (5)
  • ad hoc to paper The last branching constraint before an infeasible leaf suffices to infer the global direction of asymmetry.
    Section 3.1 justifies tracking only the last fixing before an infeasible node by arguing it must belong to any minimally infeasible subsystem under uniform coefficient signs; this is a structural assumption not established for general MIPLIB instances.
  • domain assumption The primal-dual gap is the appropriate cap for correcting LP gain overestimation.
    Section 2.1 assumes an incumbent feasible solution with a known gap is available at branching time; in practice heuristics supply this, but the gap is only an estimate and capping gains at Delta_p-d treats it as the exact redundant gain threshold.
  • ad hoc to paper Global asymmetry statistics from leaves apply uniformly to all candidate variables at the current node.
    Algorithm 1 and Section 6: exponents computed from global leaf statistics are applied to every candidate variable, assuming variables are homogeneous; the paper explicitly flags this limitation.
  • domain assumption A textbook branch-and-bound without presolve or cuts, using node counts, is a fair evaluation metric for branching quality.
    Section 1.1 uses a Python textbook B&B with best-bound ordering and no presolve or cuts; relevance to production solvers is asserted via ML imitation rather than demonstrated end-to-end.
  • domain assumption Parameters tuned on random structured instances transfer to MIPLIB instances.
    Sections 2-4 tune a_min, a_max, and eta on 14 random problem classes and then apply them to MIPLIB; transferability is an empirical assumption supported only by aggregate MIPLIB results.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Improving Full Strong Branching Decisions by Incorporating Additional Information." pith.science (2026). https://pith.science/paper/N3L52ZIX

@misc{pith2026250709455,
  author       = {Pith},
  title        = {Pith review of: Improving Full Strong Branching Decisions by Incorporating Additional Information},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/N3L52ZIX}},
  note         = {Machine review of arXiv:2507.09455}
}
read the original abstract

The full strong branching (FSB) rule is well known to produce extremely small branch-and-bound trees. This rule guides branching decisions based exclusively on the information regarding local gains in the linear programming (LP) bounds. We identify and correct two key shortcomings in FSB. First, the LP gains may be overestimations of the improvement in global dual bounds whenever pruning is possible. We propose a modification to address this issue, that incorporates primal bounds and readjusts the relative importance of the larger and smaller LP gains. Second, FSB decisions may be myopic as they consider only local LP gains and cannot foresee the impact of branching decisions on feasibility or integrality beyond immediate children. To address this weakness, we present an approach that detects global asymmetry trends in infeasibility and integrality due to 0 and 1 assignments and incorporates them into the FSB score function. We further extend this approach to achieve more balanced trees even when the branch-and-bound tree prunes primarily by bounds. Using randomly generated problem instances with known structures, we derive insights and fine-tune our modified scores. Evaluation on MIPLIB 2017 Benchmark instances shows a 22-35\% reduction in mean tree sizes for solved cases and a 3.6-5.6\% decrease in the remaining gap for unsolved ones. Our approach extends to reliability branching (RB), where improved scores reduce mean tree sizes by 5-13\% on solved instances and lower the mean gap by 2.6-4.3\% on unsolved instances, depending on primal bound quality.

Figures

Figures reproduced from arXiv: 2507.09455 by the authors.

Figure 1
Figure 1. Geometric mean of tree sizes using efficacious gains across problem classes while varying [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Impact of parameter amin on the geometric mean of tree sizes using efficacious gains for different primal gaps. 9 [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Geometric mean of tree sizes across problem classes when using the last assignment rule [PITH_FULL_IMAGE:figures/full_fig_p015_3.png] view at source ↗
Figures from the paper (4 more)
Figure 4
Figure 4. Figure 4: Impact of parameter η on the geometric mean of tree sizes using the last assignment rule for different primal gaps. 16 [PITH_FULL_IMAGE:figures/full_fig_p016_4.png]
Figure 5
Figure 5. Figure 5: Geometric mean of tree sizes across problem classes when using the rebalancing last [PITH_FULL_IMAGE:figures/full_fig_p018_5.png]
Figure 6
Figure 6. Figure 6: Impact of parameter η on the geometric mean of tree sizes using the rebalancing last assignment rule for different primal gaps. 19 [PITH_FULL_IMAGE:figures/full_fig_p019_6.png]
Figure 7
Figure 7. Figure 7: A possible partial branch-and-bound tree for the knapsack problem with constraint [PITH_FULL_IMAGE:figures/full_fig_p033_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

42 extracted references · 39 canonical work pages

  1. [1]

    PhD thesis, 2007

    Tobias Achterberg.Constraint integer programming. PhD thesis, 2007

    work page 2007

  2. [2]

    Hybrid branching

    Tobias Achterberg and Timo Berthold. Hybrid branching. InIntegration of AI and OR Tech- niques in Constraint Programming for Combinatorial Optimization Problems: 6th International Conference, CPAIOR 2009 Pittsburgh, PA, USA, May 27-31, 2009 Proceedings 6, pages 309–

    work page 2009

  3. [3]

    Branching rules revisited.Opera- tions Research Letters, 33(1):42–54, 2005

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

    work page 2005

  4. [4]

    A machine learning-based approximation of strong branching.INFORMS Journal on Computing, 29(1):185–195, 2017

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

    work page 2017

  5. [5]

    Citeseer, 1995

    David Applegate, Robert Bixby, Vašek Chvátal, and William Cook.Finding cuts in the TSP (A preliminary report), volume 95. Citeseer, 1995

    work page 1995

  6. [6]

    Experiments in mixed-integer linear programming

    Michel Bénichou, Jean-Michel Gauthier, Paul Girodet, Gerard Hentges, Gerard Ribière, and Olivier Vincent. Experiments in mixed-integer linear programming. Mathematical program- ming, 1:76–94, 1971

    work page 1971

  7. [7]

    Springer, 2016

    David Bergman, Andre A Cire, Willem-Jan Van Hoeve, and John Hooker.Decision diagrams for optimization, volume 1. Springer, 2016

    work page 2016

  8. [8]

    PhD thesis, Zuse Institute Berlin (ZIB), 2006

    Timo Berthold.Primal heuristics for mixed integer programs. PhD thesis, Zuse Institute Berlin (ZIB), 2006

    work page 2006

Show all 42 references
  1. [9]

    Measuring the impact of primal heuristics

    Timo Berthold. Measuring the impact of primal heuristics. Operations Research Letters, 41(6):611–614, 2013

    2013

  2. [10]

    Primal heuristics in integer program- ming

    Timo Berthold, Andrea Lodi, and Domenico Salvagnin. Primal heuristics in integer program- ming. American history, 1861(1900), 1945

    1900

  3. [11]

    Maher, Frederic Matter, Erik Mühmer, Benjamin Müller, Marc E

    Ksenia Bestuzheva, Mathieu Besançon, Wei-Kun Chen, Antonia Chmiela, Tim Donkiewicz, Jasper van Doornmalen, Leon Eifler, Oliver Gaul, Gerald Gamrath, Ambros Gleixner, Leona Gottwald, Christoph Graczyk, Katrin Halbig, Alexander Hoen, Christopher Hojny, Rolf vander Hulst, Thorste...

    2021

  4. [12]

    A comparison of heuristics and relaxations for the capacitated plant location problem.European journal of operational research, 50(3):280–297, 1991

    Gérard Cornuéjols, Ranjani Sridharan, and Jean-Michel Thizy. A comparison of heuristics and relaxations for the capacitated plant location problem.European journal of operational research, 50(3):280–297, 1991

    1991

  5. [13]

    Lower bounds on the size of general branch-and-bound trees

    Santanu S Dey, Yatharth Dubey, and Marco Molinaro. Lower bounds on the size of general branch-and-bound trees. Mathematical Programming, 198(1):539–559, 2023

    2023

  6. [14]

    A theoretical and compu- tational analysis of full strong-branching.Mathematical Programming, 205(1):303–336, 2024

    Santanu S Dey, Yatharth Dubey, Marco Molinaro, and Prachi Shah. A theoretical and compu- tational analysis of full strong-branching.Mathematical Programming, 205(1):303–336, 2024

    2024

  7. [15]

    Backdoor branching

    Matteo Fischetti and Michele Monaci. Backdoor branching. InInternational Conference on Integer Programming and Combinatorial Optimization, pages 183–191. Springer, 2011

    2011

  8. [16]

    Measuring the impact of branching rules for mixed- integer programming

    Gerald Gamrath and Christoph Schubert. Measuring the impact of branching rules for mixed- integer programming. InOperations Research Proceedings 2017: Selected Papers of the Annual International Conference of the German Operations Research Society (GOR), Freie Universiät Berli...

    2017

  9. [17]

    Exact combinatorial optimization with graph convolutional neural networks

    Maxime Gasse, Didier Ché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

  10. [18]

    Information-theoretic approaches to branching in search

    Andrew Gilpin and Tuomas Sandholm. Information-theoretic approaches to branching in search. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pages 545–547, 2006. 28

    2006

  11. [19]

    Lookahead branching for mixed integer programming

    Wasu Glankwamdee and Jeff Linderoth. Lookahead branching for mixed integer programming. In Twelfth INFORMS Computing Society Meeting, pages 130–150, 2006

    2006

  12. [20]

    Identifying minimally infeasible subsystems of inequalities

    John Gleeson and Jennifer Ryan. Identifying minimally infeasible subsystems of inequalities. ORSA Journal on Computing, 2(1):61–63, 1990

    1990

  13. [21]

    Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D

    Ambros Gleixner, Gregor Hendel, Gerald Gamrath, Tobias Achterberg, Michael Bastubbe, Timo Berthold, Philipp M. Christophel, Kati Jarck, Thorsten Koch, Jeff Linderoth, Marco Lübbecke, Hans D. Mittelmann, Derya Ozyurt, Ted K. Ralphs, Domenico Salvagnin, and Yuji Shinano. MIPLIB ...

    2017

  14. [22]

    Hybrid models for learning to branch

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

    2020

  15. [23]

    Gurobi Optimizer Reference Manual, 2024

    Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2024

    2024

  16. [24]

    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

  17. [25]

    Finding backdoors to integer pro- grams: a monte carlo tree search framework

    Elias B Khalil, Pashootan Vaezipoor, and Bistra Dilkina. Finding backdoors to integer pro- grams: a monte carlo tree search framework. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 3786–3795, 2022

    2022

  18. [26]

    Information-based branching schemes for binary linear mixed integer problems.Mathematical Programming Com- putation, 1:249–293, 2009

    Fatma Kılınç Karzan, George L Nemhauser, and Martin WP Savelsbergh. Information-based branching schemes for binary linear mixed integer problems.Mathematical Programming Com- putation, 1:249–293, 2009

    2009

  19. [27]

    Land and Alison G

    Ailsa H. Land and Alison G. Doig. An automatic method of solving discrete programming problems. Econometrica, 28(3):497–520, 1960

    1960

  20. [28]

    How important are branching decisions: Fooling mip solvers.Operations Research Letters, 43(3):273–278, 2015

    Pierre Le Bodic and George L Nemhauser. How important are branching decisions: Fooling mip solvers.Operations Research Letters, 43(3):273–278, 2015

    2015

  21. [29]

    Towards a universal test suite for combinatorial auction algorithms

    Kevin Leyton-Brown, Mark Pearson, and Yoav Shoham. Towards a universal test suite for combinatorial auction algorithms. In Proceedings of the 2nd ACM conference on Electronic commerce, pages 66–76, 2000

    2000

  22. [30]

    Look-ahead versus look-back for satisfiability problems

    Chu Min Li and Anbulagan. Look-ahead versus look-back for satisfiability problems. InIn- ternational Conference on Principles and Practice of Constraint Programming, pages 341–355. Springer, 1997

    1997

  23. [31]

    A computational study of search strategies for mixed integer programming.INFORMS Journal on Computing, 11(2):173–187, 1999

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

    1999

  24. [32]

    Chaff: Engineering an efficient sat solver

    Matthew W Moskewicz, Conor F Madigan, Ying Zhao, Lintao Zhang, and Sharad Malik. Chaff: Engineering an efficient sat solver. InProceedings of the 38th annual Design Automation Conference, pages 530–535, 2001

    2001

  25. [33]

    Solving mixed integer programs using neural networks.arXiv preprint arXiv:2012.13349, 2020

    Vinod Nair, Sergey Bartunov, Felix Gimeno, Ingrid Von Glehn, Pawel Lichocki, Ivan Lobov, Brendan O’Donoghue, Nicolas Sonnerat, Christian Tjandraatmadja, Pengming Wang, et al. Solving mixed integer programs using neural networks.arXiv preprint arXiv:2012.13349, 2020. 29

    2012 arXiv

  26. [34]

    Integer and Combinatorial Optimization

    GeorgeL.NemhauserandLaurenceA.Wolsey. Integer and Combinatorial Optimization. Wiley- Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, 1988

    1988

  27. [35]

    Computational study of a chance constrained portfolio selection problem.Journal of Optimization Theory and Applica- tions, 142(2):399–416, 2009

    Bernardo K Pagnoncelli, Shabbir Ahmed, and Alexander Shapiro. Computational study of a chance constrained portfolio selection problem.Journal of Optimization Theory and Applica- tions, 142(2):399–416, 2009

    2009

  28. [36]

    Active-constraint variable ordering for faster feasibility of mixed integer linear programs.Mathematical Programming, 110:445–474, 2007

    Jagat Patel and John W Chinneck. Active-constraint variable ordering for faster feasibility of mixed integer linear programs.Mathematical Programming, 110:445–474, 2007

    2007

  29. [37]

    Ecole: A gym-like library for machine learning in combinatorial optimization solvers

    Antoine Prouvost, Justin Dumouchelle, Lara Scavuzzo, Maxime Gasse, Didier Chételat, and Andrea Lodi. Ecole: A gym-like library for machine learning in combinatorial optimization solvers. InLearning Meets Combinatorial Algorithms at NeurIPS2020, 2020

    2020

  30. [38]

    Covering linear program- ming with violations.INFORMS Journal on Computing, 26(3):531–546, 2014

    Feng Qiu, Shabbir Ahmed, Santanu S Dey, and Laurence A Wolsey. Covering linear program- ming with violations.INFORMS Journal on Computing, 26(3):531–546, 2014

    2014

  31. [39]

    Capacitated lot-sizing with extensions: a review

    Daniel Quadt and Heinrich Kuhn. Capacitated lot-sizing with extensions: a review. 4OR, 6(1):61–83, 2008

    2008

  32. [40]

    Non-monotonicity of branching rules with respect to linear relaxations.INFORMS Journal on Computing, 2025

    Prachi Shah, Santanu S Dey, and Marco Molinaro. Non-monotonicity of branching rules with respect to linear relaxations.INFORMS Journal on Computing, 2025

    2025

  33. [41]

    Learning generalized strong branching for set covering, set packing, and 0–1 knapsack problems.European Journal of Operational Research, 301(3):828–840, 2022

    Yu Yang, Natashia Boland, Bistra Dilkina, and Martin Savelsbergh. Learning generalized strong branching for set covering, set packing, and 0–1 knapsack problems.European Journal of Operational Research, 301(3):828–840, 2022

    2022

  34. [42]

    arbitrary relationships

    Giulia Zarpellon, Jason Jo, Andrea Lodi, and Yoshua Bengio. Parameterizing branch-and- bound search trees to learn branching policies. InProceedings of the aaai conference on artificial intelligence, volume 35, pages 3931–3939, 2021. 30 A Alternative to Efficacious Gains An al...

    2021

Pith tools

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