Branching rules revisited

By Tobias Achterberg, Thorsten Koch, Alexander Martin. 2005

572 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Networks and Communications, Industrial and Manufacturing Engineering

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

Citations in the corpus

Learning to Branch in Mixed Integer Programming (2016, methodology): “This is the case for modern strategies such as reliability branching (Achterberg, Koch, and Martin 2005) and hybrid branching (Achterberg and Berthold 2009).”
Branching on nonchimerical fractionalities (2012, background): “This is particularly encouraging if one considers the proof-of-concept nature of our implementation.”
ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations (2014, unknown): “…119,127,128];branchesonthesearchspace[3,17];ﬁndsfeasiblesolutions.”
Solving Max-Cut to optimality by intersecting semidefinite and polyhedral relaxations (2009, background): “Contrary to linear optimization based B&B, where branching is a critical issue (see for instance [2]), we concentrate on the bounding procedure as this will turn out to be the only nontrivial part.”
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning (2016, unknown): “Strong branching is another method of variable selection that branches on the variable that induces the most change in the objective function [61,64].”
Algorithms and Software for Convex Mixed Integer Nonlinear Programs (2012, unknown): “A popular one is reliability branching [4].”
Traveling Salesman Problem (2008, unknown): “Strong branching chooses the ”best” possible fractional variable with respect to a certain score, based on LPrelaxations related to the current Branch-and-Bound node (see [3] for details).”
Primal Heuristics for Mixed Integer Programs (2006, background): “An exact definition and discussion of pseudocosts and their applications is given in [5, 46].”
Information-based branching schemes for binary linear mixed integer problems (2009, background): “Pseudocosts, introduced by Bénichou et al. (1971), estimate the degradation in the objective function value of the LP relaxation of the child node per unit change in the value of a candidate branching variable.”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, background): “e expandednext (in pink). On the right, a new state st+1 resulting frombranchingon the variableat =x4. moreextensivediscussionofB&BbranchingstrategiesinMILP,thereaderisreferredtoAchterberg et al. [3]. 3.3 Markov decision process formulation As remarked by He et al. [24], the sequential decisions”
Branching and bounds tighteningtechniques for non-convex MINLP (2009, methodology): “This is similar to the observation that for MILP problems, branching on the most fractional variable is a poor choice 2 .”
Hybrid Branching (2009, background): “In MIP, reliability pseudocost branching [2] is the current state-of-the-art.”
Solving Mixed Integer Programs Using Neural Networks (2020, background): “A CPU-based implementation of FSB can be too expensive on large-scale MIPs even for offline data generation.”
Integer and Combinatorial Optimization (2013, background): “Papers discussing branching methods include Achterberg et al. (2005) There has been a surge in research on the use of heuristic methods within the branch-cut-cut framework in order to generate good solutions and improve bounds as the search progresses.”
On learning and branching: a survey (2017, background): “This reminds of procedures such ashybrid strong/pseudocost branching (SB + PC, in short) where SB is employed only until a certain depth, and then switched for PC (Achterberg et al. 2005), and reliability branching.1 Indeed, the use of supervised learning calls for labels, meaning that one still nee”