Problems modeling a constraint in network design problem

Question

I'm working on a network design problem where the objective is to minimise the network design cost. Given a graph G = (V, E) and a set of point-to-point demands K, the task is to route the demands and capacitate the network accordingly. To that end, we consider two families of variables: routing variables $x^{k}_{p} \in \{0,1\}$, and capacity installation variables $y_{e} \in \mathbb{Z}_{\ge0}$. As to the parameters, $d^{k} > 0, \forall k\in K$ is the volume of traffic to be routed, $c_{e}$ is the cost associated with installing a capacity module $\kappa_{e} \in \mathbb{Z}_{+}$. Here is a simplified model:

$\min \hspace{1em} \sum_{e\in E}c_{e}y_{e}$

$\text{s.t.} \hspace{1em} \sum_{p\in P^{k}}x^{k}_{p} \ge 1 \hspace{1em} \forall k \in K$

$\hspace{2em} \sum_{k\in K}\sum_{p\in P^{k}}\sigma^{e}_{p}d^{k}x^{k}_{p} \le \kappa_{e}y_{e} \hspace{1em} \forall e\in E$

Now for my second experiment, I'd like to introduce a constraint to select two different paths to route the traffic but under the condition that the chosen paths don't differ by more than $r$ edges. So, I declare another family of variables $z^{k}_{p} \in \{0,1\}$ and introduce the following constraints:

$\sum_{p\in P^{k}}z^{k}_{p} \ge 1 \hspace{1em} \forall k \in K$

$x^{k}_{p} + z^{k}_{p} \le 1 \hspace{1em} \forall k \in K, p \in P^{k}$

$\sum_{e\in E} \lvert \sum_{p\in P_{k}} \sigma^{e}_{p}(x^{k}_{p} - z^{k}_{p})\rvert \le r \hspace{1em} \forall k \in K$

$\sum_{k\in K}\sum_{p\in P^{k}}\sigma^{e}_{p}d^{k}(x^{k}_{p} + z^{k}_{p}) \le \kappa_{e}y_{e} \hspace{1em} \forall e\in E$

I have two questions regarding the model. The first one is that the constraint ensuring the chosen paths don't differ by more than $r$ edges is non-linear. Is there any way to linearise this constraint or model it differently altogether? Secondly, since I plan to extend the model to a two-stage network design problem, can a row and column generation approach be applied to solve the problem? Could you please provide some pointers on this approach?

Answer 1

You can linearize by introducing a new binary variable $w_e^k$ to indicate whether edge $e$ appears in exactly one path for commodity $k$ and imposing the following constraints: \begin{align} \sum_{p\in P^k} \sigma_p^e (x_p^k - z_p^k) &\le w_e^k &&\text{for $e\in E$ and $k\in K$} \\ \sum_{p\in P^k} \sigma_p^e (z_p^k - x_p^k) &\le w_e^k &&\text{for $e\in E$ and $k\in K$} \\ \sum_{e\in E} w_e^k &\le r &&\text{for $k\in K$} \end{align}

I wouldn't recommend trying column and/or row generation until you have first tried a compact (edge-based) formulation.