Has anyone performed a benchmark of the various stabilization techniques in column generation? ... implemented in SCIP ...
The thesis "Generic Branch-Cut-and-Price" (.PDF), by Gerald Gamrath (and supervised by our Marco Lübbecke) is mentioned on the About webpage for the Generic Column Generation (GCG) software. Compare with SCIP's VRP (tiny) example docs.
It explains the improvements for Vehicle Routing Problems (VRP) using an enhanced branch-cut-and-price approach. On page 127 he writes:
"... one of the main goals of this thesis was to investigate whether the branch-cut-and-price approach in the implemented generic form is still competitive to a state-of-the-art branch-and-cut MIP solver for these problems. It turned out that the generic branch-cut-and-price solver GCG still outperforms SCIP although it does not use any problem specific knowledge except for the structure of the problem.
We studied how some concepts that are successfully used in LP based
branch-and-cut MIP solvers can be transferred to the branch-cut-and-price approach, using the example of the capacited p-median problem. By performing domain propagation in the original problem and transferring its results into the extended problem, we enforce proper variables . This slightly improved the performance of GCG. It turned out that using pseudocosts to select the variable to branch on has a big impact: it essentially halved the solving time. Furthermore, we tried to separate cutting planes in the original
problem, but did not find any for the problems classes regarded in this thesis. It seems that the reason for this is the special structure of the problems. However, for more general problems, cutting planes were found and could improve the solving capabilities of GCG.
For the column generation process, apart from incorporating further problem specific pricing solvers, stabilization of the dual variables [64, 57] is one of the most promising concepts. During the column generation process, the dual variables may highly oscillate. Through stabilization techniques, e.g., penalizing big differences to the value of the dual variable in the last solution, this is reduced which typically improves the column generation performance.".
The newest version is:
02/Jul/2018 - A major GCG 3.0.0 release is available together with the SCIP optimization Suite 6.0.0. See the CHANGELOG and the Release notes for more information.
The newest version of SCIP, incorporating GCG, is:
0/Jul/2019 - SCIP version 6.0.2 released - The SCIP Optimization Suite 6.0.2 consists of SCIP 6.0.2, SoPlex 4.0.2, ZIMPL 3.3.8, GCG 3.0.2, and UG 0.8.8. It contains important bugfixes and other improvements for all components of the Optimization Suite, see the CHANGELOG of SCIP or browse the individual CHANGELOGs of the other projects.
"A Primer in Column Generation", (March 2006), by Jacques Desrosiers and Marco Lübbecke.
"A unified solution framework for multi-attribute vehicle routing problems", (May 2014), by Thibaut Vidal, Teodor Gabriel Crainic, Michel Gendreau and Christian Prins.
A Unified Hybrid Genetic Search (UHGS) with a unified Split algorithm is proposed.
UHGS matches or outperforms all current best problem-tailored algorithms on 29 notable VRP variants and 42 benchmark sets.
"New benchmark instances for the Capacitated Vehicle Routing Problem", (Mar 2017), by Eduardo Uchoaa, Diego Pecin, Artur Pessoa, Marcus Poggi, Thibaut Vidal, and Anand Subramanian.
We show the limitations of existing Capacitated Vehicle Routing Problem instances.
We propose 100 new instances and evaluate recent exact and heuristic methods.
The same generating scheme is used to create an extended benchmark of 600 instances.
Extensive experiments and statistical analyses are done on the extended benchmark.
We present a sophisticated website containing all existing and new instances. See Thibaut Vidal's webpage.
"Multi-Objective Vehicle Routing Problem Applied to Large Scale Post Office Deliveries", (Dec 2017), by Luis A. A. Meira, Paulo S. Martins, Mauro Menzori, Guilherme A. Zeni.
Abstract: "The number of optimization techniques in the combinatorial domain is large and diversified. Nevertheless, real-world based benchmarks for testing algorithms are few. This work creates an extensible real-world mail delivery benchmark to the Vehicle Routing Problem (VRP) in a planar graph embedded in the 2D Euclidean space. Such problem is multi-objective on a roadmap with up to 25 vehicles and 30,000 deliveries per day. Each instance models one generic day of mail delivery, allowing both comparison and validation of optimization algorithms for routing problems. The benchmark may be extended to model other scenarios.".
"VRPBench: A Vehicle Routing Benchmark Tool", (Oct 2016), by Guilherme A. Zeni, Mauro Menzori, Paulo Martins and Luis Meira (PostVRP Software link).
Abstract: "The number of optimization techniques in the combinatorial domain is large and diversified. Nevertheless, there is still a lack of real benchmarks to validate optimization algorithms. In this work we introduce VRPBench, a tool to create instances and visualize solutions to the Vehicle Routing Problem (VRP) in a planar graph embedded in the Euclidean 2D space. ...".
"Using the primal-dual interior point algorithm within the branch-price-and-cut method", (Aug 2013), by Pedro Munari and Jacek Gondzio.
Abstract: "Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree.
We present the computational results of solving well-known instances of the vehicle routing problem with time windows, a challenging integer programming problem. The results indicate that the proposed approach delivers the best overall performance when compared with a similar branch-price-and-cut method which is based on the simplex algorithm.".
"Exact branch-price-and-cut algorithms for vehicle routing", (Jun 2018), by Luciano Costa, (our) Claudio Contardo and Guy Desaulniers.
Abstract: "Vehicle routing problems (VRPs) are among the most studied problems in operations research. Nowadays, the leading exact algorithms for solving many classes of VRPs are branch-price-and-cut algorithms. In this survey paper, we highlight the main methodological and modeling contributions made over the years on branch-and-price(-and-cut) algorithms for VRPs, whether they are generic or specific to a VRP variant. We focus on problems related to the classical VRP, i.e., problems in which customers must be served by several capacitated trucks, and which are not combinations of a VRP and another optimization problem.".
"Two-stage column generation", (Jan 2010), Matteo Salani, Ilaria Vacca and Michel Bierlaire.
Abstract: "We introduce a new concept in column generation for handling complex large scale optimization problems, called two-stage column generation, where columns for the compact and extensive formulation are simultaneously generated. The new framework is specifically conceived for tackling complex problems that cannot be efficiently solved by standard column generation and exploits the relationship between compact and extensive formulation. In particular, the concept of extensive reduced cost is introduced in order to estimate the contribution of compact formulation variables to the master problem. A formal description of the proposed framework is provided and major theoretical issues are discussed. An example based on the Resource Constrained Shortest Path Problem illustrates how two-stage column generation works when the pricing subproblem satisfies or not the integrality property. The two-stage scheme is applied to the Discrete Split Delivery Vehicle Routing Problem and extensive computational experiments are provided to validate our framework. In particular, computational resurts show that two-stage column generation reduces the number of generated columns and the computational time for complex instances. The transferability of the designed framework across applications and future research directions are further discussed.".
Wikipedia - Branch and Price