Has anyone performed a benchmark of the various stabilisation techniques in column generation? Which ones perform better for set pack/partition/cover problems like VRP? And are there theoretical reasons for their performance (e.g. tighter dual relaxation or less degeneracy)?
I’m particularly interested in those that can be implemented in SCIP (e.g. don’t change objective coefficients).
Stabilization methods are tricky. Dual optimal inequalities are you best chance to obtain significant speed ups. Basically they prevent a bunch of useless dual values by exploiting problem-specific structures to impose constraints on the dual space. They reduce the number of pricing iterations without compromising the complexity. Unfortunately, they are problem specific and cannot be easily generalized.
When DOIs are not an option, you can impose artificial constraints in the dual space or penalties for deviation from a sought target (center). For this to converge, you need to assure that the constraints are incrementally relaxed and the penalties reduced. The trade off is not always positive and the impact is very sensitive to the underlying implementation. Typical examples of this type of strategy are bundle methods or bounding box methods.
In a recent paper published in JOC by Pessoa et al, a simpler strategy is proposed that relies at a much lesser extent on specific implementations and parameters fine tuning. You simply use a dual center to compute an average between the current duals and the center. The master problem does not need to be modified and the strategy usually leads to significant gains.
My advice would be: try to see if DOIs can be adapted to your specific problem (unlikely for VRPs). Otherwise, use Pessoa et al method (simple and effective).
EDIT: Pessoa at al 2018 @ JOC => https://pubsonline.informs.org/doi/10.1287/ijoc.2017.0784
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 [96]. 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.
See also:
"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
In our JOC paper (Pessoa et al.) mentioned by Claudio, we have performed comparison (on 9 different problems including VRP) between some penalty function approaches and dual price smoothing (both are described in the Claudio's answer). Penalty function approaches we tried have generally better performance than dual price smoothing. However, the former are harder to implement and they are tricky to parameterize. The issue with parameterization gets worse when you start to add cuts and branch (dual values for cuts and branching constraints have generally different magnitude than ones for the "core" constraints). As a result, we almost always employ only dual price smoothing when using column generation or branch-(cut)-and-price (and we use them a lot).
In the paper, we present a modification of original dual price smoothing by Wentges in which no parameterization is needed. This is very convenient, and it allows us to use dual price smoothing by default. Our experiments showed that using the parameter-less dual price smoothing is usually much better than not using any stabilization, and it never significantly deteriorates results.
The easiest way to stabilize column generation is to use barrier solver for the master LP instead of the simplex algorithm. It may have a significant impact on the column generation performance. However, in some cases using barrier solver can deteriorate results significantly. We give some notes about this in the conclusions of our JOC paper.
Unfortunately, I am not familiar with SCIP and I do not understand about which objective coefficients you talk about (in the master problem or in the pricing problem).
