Branch and price with two sets of exponential variables

Question

There are classes of problems which allow for "natural" extended formulations using multiple exponential-size sets of variables. For example, 2-echelon routing problems can be modelled considering an exponential number of variables associated with first-echelon routes, and another exponential number of variables associated with second-echelon routes.

The methods I know of, such as this and this, enumerate one set of variables and perform pricing on the other set. Is there any paper in the literature, in which a model with more than one set of exponential variables is solved via branch-and-price, and pricing happens over more than one set of variables?

Answer 1

A common case where you would see 2 or more exponentially large sets of variables, is in:

• VRPs with heterogeneous vehicles: some vehicles have special equipment or larger capacity and can serve different types of routes
• Rostering problems with employees with different skills: some employees can perform skills that others cannot perform (e.g. drive a forklift)

For those problems, you would typically solve a pricing problem for each class. E.g. for the VRPs you would solve a separate pricing problem for each vehicle class. Naturally, for each (vehicle) class you would maintain a separate set of columns.

The problem you are referencing, the 2E-VRP is different. Although there exist many variants of this problem, the basic variant typically requires:

1. To compute a set of first-echelon (FE) routes. Unlike common VRPs the same location (satellite) can typically be visited by more than 1 FE. As such, it's necessary to uniquely distinguish between FEs.
2. To compute a set of second-echelon (SE) routes, which collectively visit all the customers. Each SE route contains a single satellite as its depot, as well as one or more customers.
3. To link the FE and SE routes in such a way that each FE supplies one or more SE routes, and, as a consequence, that each FE route has enough capacity to serve the total demand of the customers visited in these SE routes.

In the paper A Chance-Constrained Two-Echelon Vehicle Routing Problem with Stochastic Demands by Sluijk et al, you will find a CG approach to solve this problem without the need to enumerate the FE routes (see the 2E1P pricing algorithm). In their approach, a single column comprises of 1 FE route and one or more associated SE routes (so-called tour trees).

If you would impose the limiting condition that each satellite can only be visited by a single FE route, then you could have the following CG model.

Let $R^{FE}$ be the set of FE routes, $R^{SE}$ the set of SE routes, $S$ the set of satellites, $C$ the set of customers, $a_{ir}$ an indicator whether route $r$ visits $i$, $q_r$ the supply or demand of a route $r$, and $c_r$ the cost of a route.

\begin{align} \text{minimize} & \sum_{r\in R^{FE}}c_r y_r + \sum_{r\in R^{SE}}c_r y_r & \\ & \sum_{r\in R^{FE}}a_{ir} y_r \leq 1 & \forall i\in S\\ & \sum_{r\in R^{SE}}a_{ir} y_r = 1 & \forall i\in C\\ & \sum_{r\in R^{FE}}a_{ir}q_ry_r \geq \sum_{r\in R^{SE}}a_{ir}q_r y_r & \forall i\in S\\ & y_r \in \{0,1\} & \forall r \in R^{FE} \cup R^{SE} \end{align} The first constraint ensures that a satellite is visited at most once by a FE route, the 2nd constraint ensures that each customer is visited by a SE route, and the 3rd constraint links FE and SE routes together.

In theory you could allow a satellite to be visited more than once using the above formulation, but that would require introducing copies of the satellites (1 copy for every FE vehicle). This will affect the scalability of the model.

Nevertheless, the challenge with having more than 1 exponentially large set of variables is that you somehow need to link the variables together.