# Mathematical Background¶

## A column generation approach¶

*VRPy* solves vehicle routing problems with a column generation approach. The term column generation refers to the fact
that iteratively, routes (or columns) are generated with a pricing problem, and fed to a master problem which selects the best routes among
a pool such that each vertex is serviced exactly once. The linear formulations of these problems are detailed hereafter.

### Master Problem¶

Let \(G=(V,A)\) be a graph where \(V\) denotes the set of nodes that have to be visited, and \(A\) the set of edges of the network. Let \(\Omega\) be the set of feasible routes. Let \(\lambda_r\) be a binary variable that takes value \(1\) if and only if route \(r \in \Omega\) with cost \(c_r\) is selected. The master problem reads as follows:

subject to set covering constraints:

When using a column generation procedure, integrity constraints \((2)\) are relaxed (such that \(0 \le \lambda_r \le 1\)), and only a subset of \(\Omega\) is used. This subset is generated dynamically with the following sub problem.

### Pricing problem¶

Let \(\pi_v\) denote the dual variable associated with constraints \((1)\). The marginal cost of a variable (or column) \(\lambda_r\) is given by:

Therefore, if \(x_{uv}\) is a binary variable that takes value \(1\) if and only if edge \((u,v)\) is used,
*assuming there are no negative cost sub cycles*, one can formulate the problem of finding a route with negative marginal cost as follows :

subject to flow balance constraints :

In other words, the sub problem is a shortest elementary path problem, and additional constraints (such as capacities, time)
give rise to a shortest path problem with *resource constraints*, hence the interest of using the *cspy* library.

If there are negative cost cycles (which typically happens), the above formulation requires additional constraints
to enforce path elementarity, and the problem becomes computationally intractable.
Linear formulations are then impractical, and algorithms such as the ones available in *cspy* become very handy.

## Does VRPy return an optimal solution?¶

*VRPy* does not necessarily return an optimal solution (even with no time limit). Indeed, once the pricing problems fails to find
a route with negative marginal cost, the master problem is solved as a MIP. This *price-and-branch* strategy does not guarantee optimality. Note however that it
can be shown [BSL97] that asymptotically, the relative error goes to zero as the number of customers increases.
To guarantee that an optimal solution is returned, the column generation procedure should be embedded in a branch-and-bound scheme (*branch-and-price*). This
is part of the future work listed below.

## TO DO¶

Embed the solving procedure in a branch-and-bound scheme:

branch-and-price (exact)

diving (heuristic)

Implement heuristics for initial solutions.

More acceleration strategies:

other heuristic pricing strategies

switch to other LP modeling library (?)

improve stabilization

…

Include more VRP variants:

pickup and delivery with cspy

…