# Problems modeling a constraint in network design problem

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?

TIA

• What is $\sigma_p^e$ ? Jun 15 at 10:24
• It indicates if path $p$ traverses along edge $e$ Jun 15 at 11:26

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}
• Thanks a lot for the answer @RobPratt. By compact formulation, do you mean replacing variables $x^{k}_{p}$ with $x^{k}_{e}$ and introducing a flow conservation constraint at each vertex? Jun 15 at 15:28
• Yes, compact means a polynomial number of variables and constraints with respect to $|V|$, $|E|$, and $|K|$. In contrast, the paths $P^k$ are typically exponentially many. Jun 15 at 16:20