Selected Topics in Column Generation

By Marco E. Lübbecke, Jacques Desrosiers. Operational Research, 2002

1,292 citations recorded by the source corpus.

Subfields: Computational Theory and Mathematics, Industrial and Manufacturing Engineering

View Paper: https://www.semanticscholar.org/paper/5fed399a386055aa73101eaa20a32e5763563827

How researchers see this paper

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

In Computational Theory and Mathematics

In Industrial and Manufacturing Engineering

Citations in the corpus

Branch-and-bound algorithms: A survey of recent advances in searching, branching, and pruning (2016, neutral): “Detailed descriptions of branch-and-price algorithms are given in [116,117].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, methodology): “This linear program have many variables and a certain version of simplex method may be seen as a column decomposition approach [136], as we now describe.”
Subset-Row Inequalities Applied to the Vehicle-Routing Problem with Time Windows (2008, background): “Furthermore, Righini and Salani (2005) and Boland et al.”
Routing, flow, and capacity design in communication and computer networks (2004, background): “linear relaxation with column (path) generation can be found in [BJN+98], [LD02], and [Wil01]).”
Railway Track Allocation: Models and Algorithms (2012, methodology): “Same observations for large scale LPs that are solved by column generation are mentioned in Lübbecke & Desrosiers (2005) [156].”
Uncertain convex programs: randomized solutions and confidence levels (2005, background): “We address the reader to the survey [23] and the references therein for further discussion on this topic.”
Boosting Classifiers with Tightened L0-Relaxation Penalties (2010, methodology): “Note that it would also be possible to add multiple features at each iteration, and there are techniques for terminating the algorithm early while still providing guarantees on the quality of the solution; see Lübbecke & Desrosiers (2005) and Goldberg (2010).”
Traveling Salesman Problem (2008, neutral): “To alleviate the problem, an obvious approach is to use column-generation (see [23] for a summary on the topic).”
Bin packing and cutting stock problems: Mathematical models and exact algorithms (2016, background): “Other relevant remarks can be found in the general survey by Lübbecke and Desrosiers [101], who treat a number of implementation issues, including specific considerations on the BPP and the CSP.”
An exact algorithm for the vehicle routing problem based on the set partitioning formulation with additional cuts (2008, background): “[34], Lübbecke and Desrosiers [30] and Rousseau et al.”
Exact Algorithms for Electric Vehicle-Routing Problems with Time Windows (2014, methodology): “To solve the set-partitioning model (1), we develop two branch-price-and-cut algorithms (Barnhart et al., 1998; Desaulniers et al., 2005; Lübbecke and Desrosiers, 2005) for each problem variant.”
Dynamic Constraint Aggregation for Solving Very Large-scale Airline Crew Pairing Problems (2020, methodology): “Saddoune et al. (2013) applied a rolling-horizon (RH) technique where overlapping CPP subproblems restricted to a 3-day time window each are sequentially solved by CG.”