Column Generation for the CVRP

This tutorial walks through the column generation (CG) example provided under examples/cvrp_python. It shows how PathWyse can be used as a pricer inside a CG loop to solve a Capacitated Vehicle Routing Problem (CVRP) via column generation at the root node, that is, without branching.

The example is shown here in Python, but the same model and algorithm are equally valid in C++; see the C++ implementation for the corresponding port. Note that PathWyse's core is written in C++ for performance regardless of which language you use to drive it: the Python interface used here is a thin wrapper around the same compiled library.

Problem overview

The CVRP asks for a set of minimum-cost vehicle routes that serve all customers, starting and ending at a depot, subject to a vehicle capacity constraint. We solve it via column generation, where each column represents a feasible route.

The master problem is a Restricted Master Problem (RMP) over a subset of routes, that we solve, in this example, via Gurobi. At each iteration, new routes (columns) with negative reduced cost are generated by the pricing subproblem and added to the RMP until no improving column exists.

Pricing subproblem

The pricing subproblem is an Elementary Shortest Path Problem with Resource Constraints (ESPPRC). Given the current dual variables from the RMP, we look for a route whose reduced cost is negative.

For a route visiting nodes \(i_1, i_2, \ldots, i_k\), the reduced cost is:

\[ \bar{c} = c_{\text{route}} - \sum_{i} \mu_i - \gamma \]

where \(\mu_i\) are the dual variables of the customer covering constraints and \(\gamma\) is the dual of the vehicle count constraint. PathWyse solves this directly: node costs are set to \(-\mu_i\) and the initial cost is set to \(-\gamma\), so minimizing the objective is equivalent to finding the most negative reduced cost route.

Layout

File	Role
`columngen/pricer.py`	`Pricer` — wraps a PathWyse `PWSolver` as an ESPPRC pricer.
`columngen/master.py`	`RMP` — the Restricted Master Problem, solved with `gurobipy`.
`vrp.py`	The CG loop.
`pathwyse.set`	Algorithm configuration for the pricer.

Requirements

The PathWyse Python wrapper, built by running ./install.sh (or the manual build steps) from the repository root. This produces the bin folder that columngen/pricer.py imports via from bin.wrapper import PWSolver (see the Python getting started guide).
gurobipy, used by columngen/master.py to solve the Restricted Master Problem.

The bin folder produced by the build lives at the repository root, so point PYTHONPATH at it when running the example from examples/cvrp_python. The wrapper's shared library also needs to be found at runtime, so LD_LIBRARY_PATH must point at the same bin folder:

cd examples/cvrp_python
PYTHONPATH=../.. LD_LIBRARY_PATH=../../bin python3 vrp.py <instance_path> <K>

Alternatively, copy vrp.py and the columngen folder to the repository root, next to bin, and run them from there without setting any environment variable:

cp -r examples/cvrp_python/vrp.py examples/cvrp_python/columngen .
python3 vrp.py <instance_path> <K>

<instance_path> is a CVRP instance in PathWyse's instance format (see instances/spprclib for examples), and <K> is the number of available vehicles.

Setting up the pricer

The pricer is initialized once, reading the instance and configuring the algorithms:

self.pathwyse = PWSolver()
self.pathwyse.readProblem(instance_path)
self.pathwyse.setupAlgorithms()
self.pathwyse.setAlgorithmsParallel(True)

The pathwyse.set file in the example folder (examples/cvrp_python/pathwyse.set) configures three algorithms:

Algorithm 0 — PWDefault: the exact bidirectional labeling algorithm with DSSR.
Algorithm 1 — PWDefaultRelaxDom: heuristic variant with relaxed dominance.
Algorithm 2 — PWDefaultRelaxQueue: heuristic variant with bounded label queues.

It also sets problem/decimal_digits = 2, which tells PathWyse to scale all floating-point costs to integers by multiplying by \(10^2 = 100\). This is necessary because the dual variables coming from the master problem solver are real-valued, while PathWyse operates on integer costs internally. The scaling factor must be large enough to preserve the relevant decimal precision of the input data.

Updating reduced costs

At each CG iteration, the dual variables from the RMP are used to update PathWyse's objective:

def updatePricers(self, duals):
    mu = [-m for m in duals[0]]
    self.pathwyse.setNodeCosts(mu)

    gamma = -1 * duals[1]
    self.pathwyse.setInitCost(gamma)

    for algo_id in self.pathwyse.getEnabledAlgorithms():
        self.pathwyse.resetAlgorithm(algo_id, self.reset_level)

Node costs and initial cost are updated, then each enabled algorithm is reset to its unoptimized state so it starts fresh with the new costs.

Heuristic and exact switching

The key idea is to use fast heuristic algorithms during most iterations, and switch to the exact algorithm only when necessary to certify optimality.

def useHeuristics(self):
    self.pathwyse.enableAllAlgorithms()
    self.pathwyse.disableAlgorithm(0)   # disable exact

def useExact(self):
    self.pathwyse.disableAllAlgorithms()
    self.pathwyse.enableAlgorithm(0)    # enable exact only

The CG loop applies the following strategy:

if bestRC < threshold:
    # negative RC columns found: add them and continue with heuristics
    for i in range(len(columns)):
        master.addColumn(costs[i], columns[i])
    if pricers.isUsingExact():
        pricers.useHeuristics()
elif pricers.isUsingHeuristics():
    # heuristics found nothing: switch to exact to verify
    pricers.useExact()
else:
    # exact found nothing: no improving column exists
    termination = True

This avoids running the exact algorithm at every iteration, which is crucial for performance on large instances. Heuristics are fast but may miss some negative RC routes; the exact algorithm provides a certificate that no improving column exists.

Recomputing reduced costs

Because PathWyse scales costs to integers (via decimal_digits), the objective value it returns may differ slightly from the true reduced cost computed using the original floating-point duals, as rounding errors accumulate over the nodes of a route. To avoid incorrectly discarding columns, reduced costs are recomputed explicitly from the unscaled values before checking the threshold:

def recomputeRC(self, cost, col):
    rc = cost + sum(self.mu[x] for x in col) + self.gamma
    return rc

Here cost is the original arc cost of the route (retrieved via getSolutionArcCost), and self.mu, self.gamma are the original (unscaled) duals. A warning is raised if the discrepancy between PathWyse's objective and the recomputed value exceeds 1.

Collecting columns

After each pricing solve, all solutions are inspected and those with negative reduced cost are passed to the master:

nsol = self.pathwyse.getNumberOfSolutions()
for i in range(nsol):
    cost  = self.pathwyse.getSolutionArcCost(i)
    col   = self.pathwyse.getSolutionTour(i)
    rc    = self.recomputeRC(cost, col)
    if rc < threshold:
        costs.append(cost)
        columns.append(col)

Multiple solutions can be collected in a single pricing solve when algo/requested_solutions is set to a value greater than 1.