A Computational Study of Search Strategies for Mixed Integer Programming

By Jeff T. Linderoth, Martin W. P. Savelsbergh. 1999

How researchers see this paper

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

Citations in the corpus

Learning Certifiably Optimal Rule Lists (2017, methodology): “ strategies in the MIP literature. Strategies such as best-rst (best-bound) search and DFS are known as static methods, and the framework we present in x5.6 has the spirit of estimate-based methods (Linderoth and Savelsbergh, 1999). 5.3 Symmetry-aware Map The symmetry-aware map supports the symmetry”
Learning to Branch in Mixed Integer Programming (2016, methodology): “Variable selection for branching is considered to be a main component of modern MIP solvers (Linderoth and Savelsbergh 1999; Achterberg and Wunderling 2013).”
Impact-Based Search Strategies for Constraint Programming (2004, background): “A fundamental observation about pseudo-costs is that experiments reveal that the pseudo-costs of a variable tend to be the same from one node to another (see [7] and [12]).”
Exact Combinatorial Optimization with Graph Convolutional Neural Networks (2019, background): “the core of modern combinatorial optimization solvers, and have been the focus of extensive research [40; 43; 1; 17].”
A survey of variants and extensions of the location-routing problem (2015, background): “It successively fixes to zero the binary customer-to-facility assignment variables with smallest positive value and highest pseudocost (see Linderoth and Savelsbergh 1999) and then solves the resulting LP relaxation again.”
On learning and branching: a survey (2017, methodology): “Overall, it seems that the systematic analysis performed (for the ﬁrst, and still most complete, time) in Linderoth and Savelsbergh (1999) can now be revisited in the light of modern ML techniques.”
Performance Variability in Mixed-Integer Programming (2013, background): “, Linderoth and Savelsbergh [19]) that essentially simulates one level of branching for each fractional variable to select the best variable to branch on at each node.”
CAQL: Continuous Action Q-Learning (2019, methodology): “In practice however, a modern MIP solver combines many different techniques to signiﬁcantly speed up this process, such as branch-and-bound, cutting planes, preprocessing techniques, and primal heuristics (Linderoth & Savelsbergh, 1999).”
MIPLIB 2010 - Mixed Integer Programming Library version 5 (2011, unknown): “Similarly, some decisions consider a subset of candidates: for example, strong branching [76] is typically applied to the top N branching variable candidates according to some criterion.”
Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning (2016, unknown): “Linderoth and Savelsbergh [67] proposed to combine strong branching and pseudocost branching by applying strong branching only to variables with uninitialized pseudocosts.”
Branching rules revisited (2005, unknown): “For a comprehensive study of B&B strategies we refer to [8,10] and the references therein.”