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?


  • $\begingroup$ What is $\sigma_p^e$ ? $\endgroup$ – Kuifje Jun 15 at 10:24
  • $\begingroup$ It indicates if path $p$ traverses along edge $e$ $\endgroup$ – crypto 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}

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

  • $\begingroup$ 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? $\endgroup$ – crypto Jun 15 at 15:28
  • 1
    $\begingroup$ 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. $\endgroup$ – RobPratt Jun 15 at 16:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.