Local branching

By Matteo Fischetti, Andrea Lodi. Mathematical programming, 2003

723 citations recorded by the source corpus.

Subfields: Industrial and Manufacturing Engineering, Management Information Systems, Organizational Behavior and Human Resource Management

View Paper: https://www.semanticscholar.org/paper/e3d1071bf528610d19e6e298a9635718fd9fb9b8

How researchers see this paper

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

In Industrial and Manufacturing Engineering

In Management Information Systems

In Organizational Behavior and Human Resource Management

Citations in the corpus

Combinatorial optimization and reasoning with graph neural networks (2021, methodology): “They utilize the output, i.e., a variable assignment for binary variables, of the GNN to generate either local branching global cuts [Fischetti and Lodi, 2003] or using these cuts to branch at the root node.”
Integer programming techniques for the nurse rostering problem (2014, methodology): “[22,27], or with hard fixation of variables as in Relaxation Induced Neighborhood Search (RINS)[19].”
Deep neural networks and mixed integer linear optimization (2018, methodology): “In those hard cases, one should resort to heuristics possibly based on a restricted version of the model itself, in the vein of [6, 7, 12].”
Exploring relaxation induced neighborhoods to improve MIP solutions (2005, methodology): “Our implementation also outperformed the version Fischetti and Lodi used in their paper [17], which was built on top of an earlier version of CPLEX (7.”
Combining Metaheuristics and Exact Algorithms in Combinatorial Optimization: A Survey and Classification (2005, neutral): “Fischetti and Lodi [15] introduced local branching, an exact approach combining the spirit of local search metaheuristics with a generic MIP-solver (CPLEX).”
Algorithms and Software for Convex Mixed Integer Nonlinear Programs (2012, methodology): “We note that several other heuristic principles could be used such as RINS [40] or Local Branching [50] but as far as we know, these have not been applied yet to (convex) MINLPs and we will not cover them here.”
Integer-Programming Software Systems (2005, background): “Fortunately, several researchers have produced promising computational results using novel ideas, such as local branching [25] and its variants [17].”
SCIP: solving constraint integer programs (2009, background): “Other heuristics without special support in SCIP include local search heuristics like tabu search [54], rounding heuristics which try to round the current fractional LP solution to a feasible integral solution, and improvement heuristics like local branching [48] or RINS [40], which try to generate ”
Hybrid metaheuristics in combinatorial optimization: A survey (2011, background): “Fischetti and Lodi [103] also showed how the local branching constraints can be generalized to non-binary integer variables.”
The SCIP Optimization Suite 3.2 (2016, methodology): “In contrast to other LNS heuristics for MIP like rins [22], rens [12], and Local Branching [27] they do not rely on a feasible or LP solution to define the neighborhood, but rather use two structures globally available in SCIP, the clique table and the variable bound graph.”
The feasibility pump (2005, background): “25 70 2312 1681 3291 [14] rail2536c 15293 15284 2539 [8] manpower1 10565 10564 25199 [22] rail2586c 13226 13215 2589 [8] manpower2 10009 10008 23881 [22] rail4284c 21714 21705 4284 [8] manpower3 10009 10008 23915 [22] rail4872c 24656 24645 4875 [8] manpower3a 10009 10008 23865 [22] A2C1S1 3648 192 3”
Deep Neural Networks as 0-1 Mixed Integer Linear Programs: A Feasibility Study (2017, methodology): “In those hard cases, one should resort to heuristics possibly based on a restricted version of the model itself, in the vein of [5,10,6].”
Primal Heuristics for Mixed Integer Programs (2006, methodology): “Local Branching was introduced by Fischetti and Lodi [25] as a new branching strategy for MIPs which can also be effectively used as a heuristic improving the incumbent solution.”
MIPLIB 2010 - Mixed Integer Programming Library version 5 (2011, neutral): “Table 3 continued Name Originator and description biella1, dc1c, dc1l, dolom1, nsr8k, siena1 Double-Click SAS [54,55] Crew scheduling instances bienst2, binkar10_1 H.”