# Column Generation for non/single capacitated routing problems

Introduction

The strategy here documented was applied before for the TSP:

Problem definition

Let's consider the Orienteering Problem (OP) instance, as the tuple $$(G, t, T, p)$$, where:

• $$G(V, E)$$ is the undirected complete graph, where $$0 \in V$$ is the depot node;
• $$t : E \rightarrow \mathbb{R}^{+}$$ is the metric time function for the edges;
• $$T$$ is the total time limit; And
• $$p: V \rightarrow \mathbb{R}^{+}$$.

Solution definition

A feasible solution for an OP instance is given by a tour $$R$$ such that its time is less than or equal to the parameter $$T$$, $$t(R) = \sum_{e \in E(R)} t_e \leqslant T$$. The profit of a tour $$R$$ is given by the sum of the visited nodes profits, i.e. $$p(R) = \sum_{i \in V(R)} p_i$$. An optimal solution for an OP instance is a feasible tour $$R$$ which profit $$p(R)$$ is maximum.

IP

Let

• $$x_e \in \{0, 1\}$$ be the variable telling whether edge $$e \in E$$ is used; And
• $$y_i \in \{0, 1\}$$ be the variable telling whether node $$i \in V$$ is visited, i.e. has its profit collected.

We obtain the following model.

• $$\max$$ $$\sum_{i \in V} p_i y_i$$
• s.t. $$\sum_{e \in \delta(i)} x_e - 2 y_i = 0$$, $$\forall i \in V$$
• $$y_0 = 1$$
• $$\sum_{e \in E} t_e x_e \leqslant T$$
• $$2 y_i - \sum_{e \in \delta(S)} x_e \leqslant 0$$, $$\forall S \subseteq V \backslash \{0\}, i \in S$$

Matching property

A matching $$m$$ for $$G$$ is a set of edges where no two edges share common nodes.

Theorem 1: Let $$M$$ be the set of all matchings in $$G$$, we have that any tour $$R$$ can be expressed by the union of $$3$$ matchings.

Proof: Let $$R = (v_1, \dots, v_n)$$ be a tour, here we consider that $$v_1 \neq v_n$$.

• If $$n$$ is even, than two matchings $$m_1$$ and $$m_2 \in M$$ are enough for the representation of $$R$$, for instance
• $$m_1 = \{ (v_i, v_{i + 1}) | 1 \leqslant i \leqslant n - 1 \wedge i \text{ is odd} \}$$;
• $$m_2 = \{ (v_i, v_{i + 1}) | 2 \leqslant i \leqslant n - 1 \wedge i \text{ is even} \} \cup \{ (v_n, v_1) \}$$; And
• $$m_3 = \emptyset$$.
• If $$n$$ is odd, then three matchings $$m_1$$, $$m_2$$, and $$m_3 \in M$$ are enough for the representation of $$R$$, for instance
• $$m_1$$ as stated;
• $$m_2 = \{ (v_i, v_{i + 1}) | 2 \leqslant i \leqslant n - 1 \wedge i \text{ is even} \}$$; And
• $$m_3 = \{ (v_n, v_1) \}$$.

The picture below present this reasoning.

Column generation

The previously presented IP model can redesigned to use the matchings $$M$$ as variables. Let

• $$\lambda_m \in [0, 1]$$ be this respective variable, for $$m \in M$$; And
• $$h(m, e) \in \{0, 1\}$$ be a function telling whether edge $$e \in E$$ belongs to matching $$m$$.

Let $$M^{'} \subseteq M$$ be a subset of matchings of $$G$$, such that $$\emptyset \in M^{'}$$, we obtain the following Restricted Master Problem (RMP), where the left side letters are the respective duals.

• $$\max$$ $$\frac{1}{2} \sum_{i \in V} p_i \sum_{e \in \delta(i)} \sum_{m \in M^{'}} h(m, e) \lambda_m$$
• s.t. $$(\pi_i)$$ $$\sum_{e \in \delta(i)} \sum_{m \in M^{'}} h(m, e) \lambda_m \leqslant 2$$, $$\forall i \in V \backslash \{0\}$$
• $$(\pi_0)$$ $$\sum_{m \in M^{'}} h(m, 0) \lambda_m = 2$$
• $$(\tau)$$ $$\sum_{e \in E} t_e \sum_{m \in M^{'}} h(m, e) \lambda_m \leqslant T$$
• $$(\xi_S^i)$$ $$\sum_{e \in \delta(i)} \sum_{m \in M^{'}} h(m, e) \lambda_m - \sum_{e \in \delta(S)} \sum_{m \in M^{'}} h(m, e) \lambda_m \leqslant 0$$, $$\forall S \subseteq V \backslash \{0\}, i \in S$$
• $$(\sigma_e)$$ $$\sum_{m \in M^{'}} h(m, e) \lambda_m \leqslant 1$$ $$\forall e \in E$$
• $$(\theta)$$ $$\sum_{m \in M^{'}} \lambda_m = 3$$
• $$(\beta_m)$$ $$- \lambda_m \leqslant 0$$, $$\forall m \in M^{'}$$
• $$(\gamma_m)$$ $$\lambda_m \leqslant 1$$, $$\forall m \in M^{'}$$

Subproblem:

The reduced cost of a matching $$m \in M$$ is given by:

$$\kappa_m = \sum_{e \in E} h(m, e) \kappa_e - \theta - \gamma_m \geqslant 0$$, $$\forall m \in M$$

And the "reduced cost" of an edge is given by

$$\kappa_e = \frac{1}{2}(p_i + p_j) - (\pi_i + \pi_j + \tau t_e - \sum_{S \subseteq V, i \in S : e \in \delta(S)} \xi_S^i + \sum_{S \subseteq V, i \in S : e \in \delta(i)} \xi_S^i + \sigma_e)$$, $$\forall e = (i, j) \in E$$

note that, there is no explicit variables for the edges in the RMP, therefore the $$\kappa_e$$ is just an auxiliary notation.

If a matching does not belong to the RMP, i.e. $$m \notin M^{'}$$, we have that $$\gamma_m = 0$$ (by the complementarity property), and if the matching $$m$$ is a "suitable" candidate for the next iteration of the column generation algorithm, then we have that

$$\kappa_m = \sum_{e \in E} h(m, e) \kappa_e < \theta$$, $$\forall m \notin M^{'}$$

The subproblem of the RMP can be given by the problem of finding a tour $$R$$ which:

• $$\sum_{e \in E(R)} \kappa_e$$ is minimum and $$< \theta$$; And
• $$\sum_{e \in E(R)} t_e \leqslant T$$.

And then, decomposing the found $$R$$ into three matchings.

Alternative subproblems:

I am looking for some alternatives for subproblems for this problem, for now I have in mind two strategies, however, I do not know if they are right, so I decided to share it here to get some feedback.

Subproblem 1: Finding three matchings which $$\kappa_e$$ sum is minimum, and total time is within $$T$$. Note that, these three matchings not necessarily result in a tour.

• $$\min$$ $$\sum_{k \in \{1, 2, 3\}} \sum_{e \in E} \kappa_e x_e^k$$
• s.t. $$\sum_{e \in \delta(i)} x_e^k \leqslant 1$$, $$\forall i \in V, k \in \{1, 2, 3\}$$
• $$\sum_{k \in \{1, 2, 3\}} \sum_{e \in E} t_e x_e^k \leqslant T$$
• $$\sum_{k \in \{1, 2, 3\}} x_e^k \leqslant 1$$, $$\forall e \in E$$
• $$x_e^k \in \{0, 1\}$$, $$\forall e \in E, k \in \{1, 2, 3\}$$

Subproblem 2: Finding a single matching which $$\kappa_e$$ sum is minimum, and total time is within $$T$$.

• $$\min$$ $$\sum_{e \in E} \kappa_e x_e$$
• s.t. $$\sum_{e \in \delta(i)} x_e \leqslant 1$$, $$\forall i \in V$$
• $$\sum_{e \in E} t_e x_e \leqslant T$$
• $$x_e \in \{0, 1\}$$, $$\forall e \in E$$

However, I am not sure if any of these alternative strategies allow the algorithm to converge in an optimal solution, i.e. if three matchings which union results in an optimal tour can be attained. I would like to know if someone has some thoughts on this.

Let me know if there is any mistake in the reasoning.

Update 1: In the subproblem 1, I added a constraint imposing that an edge is used at most once.

• As a further strengthening of subproblem 1, you could impose that at most two edges out of each node are used. Commented Jun 1 at 20:39
• You could also impose exactly two edges out of the depot. Commented Jun 1 at 21:02
• Thank you, I will do that. Commented Jun 1 at 21:07

For a maximization master problem whose variables correspond to matchings, the subproblem is an oracle to find a positive (not negative) reduced cost matching (not a tour) if one exists. Because your sum of matchings must satisfy the $$\le T$$ constraint, you can optionally further restrict each matching to do so. Your Subproblem 2 (but corrected to maximization) is the most natural choice, and Subproblem 1 (but corrected to maximization) is also valid and might reduce the overall number of column generation iterations because it can possibly also generate more than one positive reduced cost column at a time. When updating the master, just be careful not to duplicate existing columns.

If the $$\le T$$ makes the subproblem too difficult, you might also consider omitting it from either Subproblem 1 or Subproblem 2. In particular, Subproblem 2 without the $$\le T$$ side constraint can use a fast specialized algorithm for maximum edge weight matchings.

In any case, you can simplify the master problem by omitting the $$\lambda_m \le 1$$ constraint and its dual $$\gamma_m$$. It is already implied by the other $$\le 1$$ master constraint.

Note also that you will typically need to branch after no more positive reduced cost columns are generated and you have thus solved the master LP to optimality. See Integer column generation without branch & price. Fortunately, branching on the edge variables preserves the subproblem structure for your problem.

• Thank you so much. What concerns me, with, both, subproblems 1 and 2, is that, at least in principle, once a matching $m_1$ is attained, there is no guarantee that the corresponding matchings $m_2$ and $m_3$, that lead to a feasible tour, will be found. For simplicity, let's consider a CG algorithm with the aim of attaining a better relaxation, instead of attaining the optimal solution, what would require, as you mentioned a B&C&P scheme. (to continue ...) Commented Jun 1 at 19:43
• For instance, let's suppose that in a given iteration of the algorithm, we generate a matching $m_1$ and we bring it to the set $M^{'}$, i.e. we expand the RMP. Not necessarily, the corresponding primal variable $\lambda_{m_1}$ will be used in the next iteration, i.e. eventually value$(\lambda_{m_1}) = 0$, since the corresponding $m_2$ and $m_3$ not necessarily exist in the RMP, i.e. exist in $M^{'}$. Commented Jun 1 at 19:43
• And, as far as I know, once a new column is generated, mandatorily it must be used as part of the solution of the next CG algorithm iteration. Commented Jun 1 at 19:44
• Here's another idea you can try in each iteration, with the motivation of getting columns that "play well" together. Solve subproblem 2, temporarily remove the edges $E_m$ of the matching $m$, and solve subproblem 2 again, with $E$ replaced by $E\setminus E_m$ and $T$ decremented by $\sum_{e\in E_m} t_e$. Repeat on a sparser and sparser graph until you no longer get a positive reduced cost matching. Commented Jun 1 at 20:33
• Thank you so much. I've just updated the subproblem 1 to reflect the suggestion you just gave. Commented Jun 1 at 20:38