Branch-and-Price: Column Generation for Solving Huge Integer Programs

By Cynthia Barnhart, Ellis L. Johnson, George L. Nemhauser, Martin W. P. Savelsbergh, P. H. Vance. 1998

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

Computing Optimal Decision Sets with SAT (2020, methodology): “Since the IP model has one binary variable for each possible clause, the authors use column generation [6].”
Boolean Decision Rules via Column Generation (2018, methodology): “This approach is called branch-and-price [4] and is quite computationally intensive.”
A robust optimization approach for dynamic traffic signal control with emission considerations (2012, methodology): “Due to the critical role of an MILP in mathematical programming, the solution schemes for an MILP have been heavily investigated in literature (see Barnhart et al. (1998) and Geoffrion and Marstern (1972) for reviews on MILP).”
Clearing algorithms for barter exchange markets: enabling nationwide kidney exchanges (2007, background): “We can even find cycles with the most positive price, which are the ones most likely to improve the objective value of restricted LP [1].”
Integer programming techniques for educational timetabling (2017, methodology): “However, to achieve good/optimal solutions through exact methods may be possible only when the timetabling problem is small or when advanced techniques of formulation, such as Column Generation [16], Cuts [17, 18], and Decomposition [19] are applied.”
Order batching to minimize total travel time in a parallel-aisle warehouse (2005, background): “A set covering formulation is usually preferred, since its linear programming relaxation, obtained by replacing the conditions in Equation (2) by the conditions xs ≥ 0 for all s ∈ S, is far more stable and thus easier to solve; see for instance Barnhart et al. (1998).”
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows (2014, methodology): “Denote by qi the demand of customer i ∈ N and by [ei, `i] the time window in which service has to start at this customer.”
Market-clearing with stochastic security-part II: case studies (2005, methodology): “In addition, as mentioned in the companion paper, the use of scenario reduction techniques [15]–[17] is promising, as are decomposition techniques based on Benders’ decomposition [18]–[21] and “branch-and-price” decomposition [22]–[24].”
From physical security to cybersecurity (2015, methodology): “ASPEN exploits this by using a “column generation”- based approach [25] for the defender, in which defender pure strategies are iteratively generated and added to the optimization formulation.”
Branch and Cut and Price for the Pickup and Delivery Problem with Time Windows (2009, methodology): “Branch-and-price methods (see, e.g., Barnhart et al., 1998; Desaulniers et al., 1998) use a branch-and-bound scheme in which lower bounds are computed by column generation.”
Flow shop scheduling with earliness, tardiness, and intermediate inventory holding costs (2004, background): “See Barnhart et al. (1998) for a discussion of this so-called “tailing-off effect.”
On Dantzig-Wolfe Decomposition in Integer Programming and ways to Perform Branching in a Branch-and-Price Algorithm (2000, methodology): “For a discussion of other ways in which to carry out the phase 1 of the simplex algorithm, of various column generation strategies that may be used (generation of multiple columns, heuristic generation,: : :), and of early termination of the column generation procedure, the reader is referred to Bar”
An interior-point Benders based branch-and-cut algorithm for mixed integer programs (2010, methodology): “…solution methodology, it was necessary to modify some of the IP solution approaches to integrate with interior-point methods, as the simple replacement of the simplex method with an interior-point method fails to exploit some desired features such as warm starting (Barnhart et al. 1998).”