- without changing the paths established in $\tilde{S}^{55}$: we derive a solution $S^{58} = (E^{58}, S^{58})$ from the solution $\tilde{S}^{55}$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $\tilde{S}^{55}$ (i.e., $E_k^{58} = \tilde{E}_k^{55}$ for each $k \in K$), and also the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{55}$ remain the same in $S^{58}$, i.e., $\tilde{S}_{k'}^{55} = S_{k'}^{58}$ for each demand $k'' \in K \setminus \{k, k'\}$, and $S_{k'}^{58} = \tilde{S}_{k'}^{55} \cup \{s'\}$ for the demand $k'$, and modifying the last-slots assigned to the demand $k$ by adding a new last-slot $\tilde{s}$ and removing the last slot $s \in \tilde{S}_k^{55}$ with $s \in \{s_i + w_k + 1, ..., s_j\}$ and $\tilde{s} \notin \{s_i + w_k + 1, ..., s_j\}$ for the demand $k$ with $k \in \tilde{K}$ s.t. $S_k^{58} = (\tilde{S}_k^{55} \setminus \{s\}) \cup \{\tilde{s}\}$ s.t. $\{\tilde{s} - w_k + 1, ..., \tilde{s}\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k' \in K$ and $s' \in S_k^{58}$ with $E_k^{58} \cap E_{k'}^{58} \neq \emptyset$. The solution $S^{58}$ is feasible given that

* a feasible path $E_k^{58}$ is assigned to each demand $k \in K$ (routing constraint),

* a set of last-slots $S_k^{58}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{58}$ with $|S_k^{58}| \ge 1$ (contiguity and continuity constraints),

* $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{58}$ and $s'' \in S_{k'}^{58}$ with $E_k^{58} \cap E_{k'}^{58} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in \mathbb{S}$ we have $\sum_{k \in K, e' \in E_k^{58}} |\{s' \in S_k^{58}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{58}}, z^{S^{58}})$ is belong to $F$ and then to $F_{\tilde{K}}^{\tilde{G}_I^e}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1$. We then obtain that

$$ \mu x^{\tilde{S}^{55}} + \sigma z^{\tilde{S}^{55}} = \mu x^{S^{58}} + \sigma z^{S^{58}} = \mu x^{\tilde{S}^{55}} + \sigma z^{\tilde{S}^{55}} + \sigma_{s'}^{k'} - \sigma_s^k + \sigma_{\tilde{s}}^k. $$

It follows that $\sigma_{s'}^{k'} = \sigma_s^k$ for demand $k'$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $k' \in \tilde{K}$ and $s' \in \{s_i + w_{k'} + 1, ..., s_j\}$ given that $\sigma_{\tilde{s}}^k = 0$ for $\tilde{s} \notin \{s_i + w_k - 1, ..., s_j\}$ with $k \in \tilde{K}$.

- with changing the paths established in $\tilde{S}^{55}$: we construct a solution $S'^{58}$ derived from the solution $\tilde{S}^{55}$ by

* with modifying the paths assigned to a subset of demands $\tilde{K} \subset K$ in $\tilde{S}^{55}$ (i.e., $E_k'^{58} = \tilde{E}_k^{55}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{58} \neq \tilde{E}_k^{55}$ for each $k \in \tilde{K}$),

* and the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{55}$ remain the same in $S'^{58}$, i.e., $\tilde{S}_{k'}^{55} = S_{k'}^{58}$ for each demand $k'' \in K \setminus \{k, k'\}$,

* and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $S_{k'}'^{58} = \tilde{S}_{k'}^{55} \cup \{s'\}$ for the demand $k'$,

* and selecting a demand $k$ from $\tilde{K}_{55}$ which allocates a last slot $s \in \tilde{S}_k^{55}$ with $s \in \{s_i + w_k + 1, ..., s_j\}$ in the solution $\tilde{S}^{55}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $\tilde{S}_{k'}^{55}$ assigned to the demand $k'$ in the solution $\tilde{S}^{55}$),

* and modifying the last-slots assigned to the demand $k$ by adding a new last-slot $\tilde{s}$ and removing the last slot $s \in \tilde{S}_k^{55}$ with $s \in \{s_i + w_k + 1, ..., s_j\}$ and $\tilde{s} \notin \{s_i + w_k + 1, ..., s_j\}$ for the demand $k$ with $k \in \tilde{K}$ s.t. $S_k'^{58} = (\tilde{S}_k^{55} \setminus \{s\}) \cup \{\tilde{s}\}$ s.t. $\{\tilde{s} - w_k + 1, ..., \tilde{s}\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k' \in K$ and $s' \in S_k'^{58}$ with $E_k'^{58} \cap E_{k'}^{58} \neq \emptyset$.

The solution $S'^{58}$ is clearly feasible given that

* a feasible path $E_k'^{58}$ is assigned to each demand $k \in K$ (routing constraint),

* a set of last-slots $S_k'^{58}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{58}$ with $|S_k'^{58}| \ge 1$ (contiguity and continuity constraints),

* $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k'^{58}$ and $s'' \in S_{k'}'^{58}$ with $E_k'^{58} \cap E_{k'}'^{58} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in \mathbb{S}$ we have $\sum_{k \in K, e' \in E_k'^{58}} |\{s' \in S_k'^{58}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S'^{58}}, z^{S'^{58}})$ is belong to $F$ and then to $F_{\tilde{K}}^{\tilde{G}_I^e}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1$. We have so

$$ \mu x^{\tilde{S}^{55}} + \sigma z^{\tilde{S}^{55}} = \mu x^{S'^{58}} + \sigma z^{S'^{58}} = \mu x^{\tilde{S}^{55}} + \sigma z^{\tilde{S}^{55}} + \sigma_{s'}^{k'} - \sigma_s^k + \sigma_{\tilde{s}}^k \\ - \sum_{k \in \tilde{K}} \sum_{e' \in \tilde{E}_k^{55}} \mu_{e'}^k + \sum_{k \in \tilde{K}} \sum_{e' \in E_k'^{58}} \mu_{e'}^k. $$

It follows that $\sigma_{s'}^{k'} = \sigma_s^k$ for demand $k'$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $k' \in \tilde{K}$ and $s' \in \{s_i + w_{k'} + 1, ..., s_j\}$ given that $\sigma_{\tilde{s}}^k = 0$ for $\tilde{s} \notin \{s_i + w_k - 1, ..., s_j\}$ with $k \in \tilde{K}$, and $\mu_{e'}^k = 0$ for all $k \in K$ and all $e' \in E \setminus (E_0^k \cup E_1^k)$ with $e' \neq e$ if $k \in \tilde{K}$.
Given that the pair $(k, k')$ are chosen arbitrary in the minimal cover $\tilde{K}$, we iterate the same procedure for all pairs $(k, k')$ s.t. we find

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all pairs } (k, k') \in \tilde{K} $$

with $s \in \{s_i + w_k - 1, ..., s_j\}$ and $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$. We re-do the same procedure for each two slots $s, s' \in \{s_i + w_k - 1, ..., s_j\}$ for each demand $k \in K$ with $k \in \tilde{K}$ s.t.

$$ \sigma_s^k = \sigma_{s'}^k, \text{ for all } k \in \tilde{K} \text{ and } s, s' \in \{s_i + w_k - 1, ..., s_j\}. $$

Let us prove now that $\mu_e^k$ for all $k \in K$ with $k \in \tilde{K}$ are equivalents. For that, we consider a solution $S^{59} = (E^{59}, S^{59})$ defined as below

- a feasible path $E_k^{59}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k^{59}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{59}$ with $|S_k^{59}| \ge 1$ (contiguity and continuity constraints),

- $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k, k' \in K$ and each $s \in S_k^{59}$ and $s' \in S_{k'}^{59}$ with $E_k^{59} \cap E_{k'}^{59} \neq \emptyset$ (non-overlapping constraint),

- and there is one demand $k$ from the minimal cover $\tilde{K}$ (i.e., $k \in \tilde{K}$ s.t. the demand $k$ pass through the edge $e$ in the solution $S^{59}$, i.e., $e \in E_k^{59}$ for a node $k \in \tilde{K}$, and $e \notin E_{k'}^{59}$ for all $k' \in \tilde{K} \setminus \{k\}$,

- and all the demands in $\tilde{K}$ are covered by the interval $I$ in the solution $S^{59}$, i.e., $\{s_i + w_k + 1, ..., s_j\} \cap S_k^{59} \neq \emptyset$ for each $k \in \tilde{K}$.

Obviously, $S^{59}$ is a feasible solution for the problem given that it satisfies all the constraints of our cut formulation (2)-(12). Moreover, the corresponding incidence vector $(x^{S^{59}}, z^{S^{59}})$ is belong to $P(G, K, \mathbb{S}, \tilde{K}, I, e)$ and then to $F_{\tilde{K}}^{G_e}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1$.

Consider now a node $k'$ in $\tilde{K}$ s.t. $e \notin E_{k'}^{59}$. For that, we consider a solution $\tilde{S}^{59} = (\tilde{E}^{59}, \tilde{S}^{59})$ in which

- a feasible path $\tilde{E}_k^{59}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $\tilde{S}_k^{59}$ is assigned to each demand $k \in K$ along each edge $e \in \tilde{E}_k^{59}$ with $|\tilde{S}_k^{59}| \ge 1$ (contiguity and continuity constraints),

- $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in \tilde{S}_k^{59}$ and $s'' \in \tilde{S}_{k'}^{59}$ with $\tilde{E}_k^{59} \cap \tilde{E}_{k'}^{59} \neq \emptyset$, i.e., for each edge $e \in E$ and each slot $s'' \in \mathbb{S}$ we have $\sum_{k \in K, e \in \tilde{E}_k^{59}} |\{s' \in \tilde{S}_k^{59}, s'' \in \{s' - w_k + 1, ..., s''\}| \le 1$ (non-overlapping constraint),

- and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k \in K$ and $s \in S_k^{59}$ with $\tilde{E}_k^{59} \cap \tilde{E}_{k'}^{59} \neq \emptyset$,

- and there is $|\tilde{K}| - 1$ demands from the minimal cover $\tilde{K}$ that use the edge $e$ denoted by $\tilde{K}_{59}$ (i.e.,if $k \in \tilde{K}_{59}$ means that the demand $k$ pass through the edge $e$ in the solution $\tilde{S}^{59}$, i.e., $e \in \tilde{E}_k^{59}$ for each $k \in \tilde{K}_{59}$, and $e \notin \tilde{E}_{k'}^{59}$ for all $k' \in \tilde{K} \tilde{K}_{59}$,

- and all the demands in $\tilde{K}$ are covered by the interval $I$ in the solution $\tilde{S}^{59}$, i.e., $\{s_i + w_k + 1, ..., s_j\} \cap \tilde{S}_k^{59} \neq \emptyset$ for each $k \in \tilde{K}$.

$\tilde{S}^{59}$ is clearly feasible for the problem given that it satisfies all the constraints of cut formulation (2)-(12). Hence, the corresponding incidence vector $(x^{\tilde{S}^{59}}, z^{\tilde{S}^{59}})$ is belong to $F$ and then to $F_{\tilde{K}}^{\tilde{G}_e}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1$. Based on this, we derive a solution $S^{60} = (E^{60}, S^{60})$ from the solution $\tilde{S}^{59}$ by

- the paths assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{59}$ remain the same in $S^{60}$ (i.e., $E^{60}_k = \tilde{E}_{k'}^{59}$ for each $k \in K \setminus \{k, k'\}$),

- without modifying the last-slots assigned to the demands $K$ in $\tilde{S}^{59}$, i.e., $\tilde{S}_k^{59} = S^{60}_k$ for each demand $k \in K$,

- modifying the path assigned to the demand $k'$ in $\tilde{S}^{59}$ from $\tilde{E}_{k'}^{59}$ to a path $E^{60}_{k'}$ passed through the edge $e$ (i.e., $e \in E^{60}_{k'}$) with $k' \in \tilde{K}$ s.t. $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k \in K$ and each $s' \in \tilde{S}_{k'}^{59}$ and each $s \in \tilde{S}_k^{59}$ with $\tilde{E}_k^{59} \cap E^{60}_{k'} \neq \emptyset$,
- selecting a demand $k$ in $\tilde{K}_{59}$ which use the edge $e$ in the solution $S^{59}$,

- modifying the path assigned to the selected demand $k$ in $\tilde{S}^{59}$ with $e \in \tilde{E}_k^{59}$ and $k \in \tilde{K}$ from $\tilde{E}_k^{59}$ to a path $E_k^{60}$ without passing through the edge $e$ (i.e., $e \notin E_k^{60}$) and $\{s-w_k+1, \dots, s\} \cap \{s'-w_{k'}+1, \dots, s'\} = \emptyset$ for each $k' \in K \setminus \{k, k'\}$ and each $s \in \tilde{S}_k^{59}$ and each $s' \in \tilde{S}_{k'}^{59}$ with $\tilde{E}_k^{59} \cap E_k^{60} \neq \emptyset$, and $\{s-w_k+1, \dots, s\} \cap \{s'-w_{k'}+1, \dots, s'\} = \emptyset$ for each $s \in \tilde{S}_k^{59}$ and each $s' \in \tilde{S}_{k'}^{59}$ with $E_k^{60} \cap E_k^{60} \neq \emptyset$.

The solution $S^{60}$ is feasible given that

- a feasible path $E_k^{60}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k^{60}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{60}$ with $|S_k^{60}| \geq 1$ (contiguity and continuity constraints),

- $\{s' - w_k + 1, \dots, s'\} \cap \{s'' - w_{k'} + 1, \dots, s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{60}$ and $s'' \in S_{k'}^{60}$ with $E_k^{60} \cap E_{k'}^{60} \neq \emptyset$, i.e., for each edge $e \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e \in E_k^{60}} |\{s' \in S_k^{60}, s'' \in \{s' - w_k + 1, \dots, s'\}| \leq 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{60}}, z^{S^{60}})$ is belong to $F$ and then to $F_{\tilde{K}}^{\tilde{G}_I^e}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1$. We then obtain that

$$ \mu x^{S^{59}} + \sigma z^{\tilde{S}^{59}} = \mu x^{S^{60}} + \sigma z^{S^{60}} = \mu x^{S^{59}} + \sigma z^{\tilde{S}^{59}} + \mu_e^{k'} - \mu_e^k + \sum_{e'' \in E_k^{60} \setminus \{e\}} \mu_e^{k'} - \sum_{e'' \in E_k^{60} \setminus \{e\}} \mu_e^{k'} + \sum_{e'' \in E_k^{60}} \mu_e^k - \sum_{e'' \in E_k^{60} \setminus \{e\}} \mu_e^k. $$

It follows that $\mu_e^{k'} = \mu_e^k$ for demand $k'$ and a edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$ with $v_{k',e'} \in \tilde{K}$ given that $\mu_e^{k'} = 0$ for all $k \in K$ and all $e' \in E \setminus (E_0^k \cup E_1^k)$ with $k \notin \tilde{K}$.

Given that the pair $(k, k')$ are chosen arbitrary in the minimal cover $\tilde{K}$, we iterate the same procedure for all pairs $(k, k')$ s.t. we find

$$ \mu_e^k = \mu_e^{k'}, \text{ for all pairs } (k, k') \in \tilde{K}. $$

Furthermore, let prove that all $\sigma_s^k$ and $\mu_e^k$ are equivalents for all $k \in \tilde{K}$ and $s \in \{s_i + w_k - 1, \dots, s_j\}$. For that, we consider for each demand $k'$ with $k' \in \tilde{K}$, a solution $S^{61} = (E^{61}, S^{61})$ derived from the solution $\tilde{S}^{59}$ as below

- the paths assigned to the demands $K \setminus \{k'\}$ in $\tilde{S}^{59}$ remain the same in $S^{61}$ (i.e., $E_k^{61} = \tilde{E}_k^{59}$ for each $k'' \in K \setminus \{k'\}$),

- without modifying the last-slots assigned to the demands $K \setminus \{k\}$ in $\tilde{S}^{59}$, i.e., $\tilde{S}_k^{59} = S_k^{61}$ for each demand $k'' \in K \setminus \{k\}$,

- modifying the set of last-slots assigned to the demand $k'$ in $\tilde{S}^{59}$ from $\tilde{S}_{k'}^{59}$ to $S_{k'}^{61}$ s.t. $S_{k'}^{61} \cap \{s_i + w_{k'} - 1, \dots, s_j\} = \emptyset$.

Hence, there are $|\tilde{K}| - 1$ demands from $\tilde{K}$ that are covered by the interval $I$ (i.e., all the demands in $C \setminus \{k'\}$), and all the demands in $\tilde{K}$ use the edge $e$ in the solution $S^{61}$. The solution $S^{61}$ is then feasible given that

- a feasible path $E_k^{61}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k^{61}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{61}$ with $|S_k^{61}| \geq 1$ (contiguity and continuity constraints),

- $\{s' - w_k + 1, \dots, s'\} \cap \{s'' - w_{k'} + 1, \dots, s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{61}$ and $s'' \in S_{k'}^{61}$ with $E_k^{61} \cap E_{k'}^{61} \neq \emptyset$, i.e., for each edge $e \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e \in E_k^{61}} |\{s' \in S_k^{61}, s'' \in \{s' - w_k + 1, \dots, s'\}| \leq 1$ (non-overlapping constraint),

- and $\sum_{k \in \tilde{K}} |E_k^{61} \cap \{e\}| + |S_k^{61} \cap \{s_i + w_k - 1, \dots, s_j\}| = 2|\tilde{K}| - 1$.

The corresponding incidence vector $(x^{S^{61}}, z^{S^{61}})$ is belong to $F$ and then to $F_{\tilde{K}}^{\tilde{G}_I^e}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1$. We then obtain that

$$ \mu x^{\tilde{S}^{59}} + \sigma z^{\tilde{S}^{59}} = \mu x^{S^{61}} + \sigma z^{S^{61}} = \mu x^{\tilde{S}^{59}} + \sigma z^{\tilde{S}^{59}} + \mu_e^{k'} - \sigma_s^{k'} + \sum_{e'' \in E_{k'}^{61} \setminus \{e\}} \mu_e^{k'} - \sum_{e'' \in E_{k'}^{61}} \mu_e^{k'}. $$
It follows that $\mu_e^{k'} = \sigma_s^{k'}$ for demand $k'$ and slot $s \in \{s_i + w_{k'} - 1, ..., s_j\}$ given that $\mu_e^k = 0$ for all $k \in K$ and all $e'' \in E \setminus (E_0^k \cup E_1^k)$ with $e \neq e''$ if $k \in \tilde{K}$. Moreover, by doing the same thing over all slots $s \in \{s_i + w_{k'} - 1, ..., s_j\}$, we found that

$$ \mu_e^{k'} = \sigma_s^{k'}, \text{ for all } s \in \{s_i + w_{k'} - 1, ..., s_j\}. $$

Given that $k'$ is chosen arbitrarily in $\tilde{K}$, we iterate the same procedure for all $k \in \tilde{K}$ to show that

$$ \mu_e^k = \sigma_s^k, \text{ for all } k \in \tilde{K} \text{ and all } s \in \{s_i + w_k - 1, ..., s_j\}. $$

Based on this, and given that all $\mu_e^k$ are equivalents for all $k \in \tilde{K}$, and that $\sigma_s^k$ are equivalents for all $k \in \tilde{K}$ and $s \in \{s_i + w_{k'} - 1, ..., s_j\}$, we obtain that

$$ \mu_e^k = \sigma_s^{k'}, \text{ for all } k, k' \in \tilde{K} \text{ and all } s \in \{s_i + w_{k'} - 1, ..., s_j\}. $$

Consequently, we conclude that

$$ \mu_e^k = \sigma_s^{k'} = \rho, \text{ for all } k, k' \in \tilde{K} \text{ and all } s \in \{s_i + w_{k'} - 1, ..., s_j\}. $$

On the other hand, we ensure that all $e' \in E_0^k$ for each demand $k$ are independents s.t. for each demand $k \in K$ we have

$$ \sum_{e' \in E_0^k} \mu_{e'}^k = \sum_{e' \in E_0^k} \gamma_1^{k, e'} \rightarrow \sum_{e' \in E_0^k} (\mu_{e'}^k - \gamma_1^{k, e'}) = 0. $$

The only solution of this system is $\mu_{e'}^k = \gamma_1^{k, e'}$ for each $e' \in E_0^k$ for the demand $k$. As $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$. We conclude that

$$ \mu_{e'}^k = \gamma_1^{k, e'}, \text{ for all } k \in K \text{ and all } e' \in E_0^k, $$

We re-do the same thing for the edges $e' \in E_1^k$ for each demand $k$ which are independents s.t. for each demand $k \in K$ we have

$$ \sum_{e' \in E_1^k} \mu_{e'}^k = \sum_{e' \in E_1^k} \gamma_2^{k, e'} \rightarrow \sum_{e' \in E_1^k} (\mu_{e'}^k - \gamma_2^{k, e'}) = 0 $$

The only solution of this system is $\mu_{e'}^k = \gamma_2^{k, e'}$ for each $e' \in E_1^k$ for the demand $k$. As $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$. We conclude that

$$ \mu_{e'}^k = \gamma_2^{k, e'}, \text{ for all } k \in K \text{ and all } e' \in E_1^k, $$

Furthermore, all the slots $s \in \{1, ..., w_k - 1\}$ for each demand $k$ are independents s.t. for each demand $k \in K$, we have

$$ \sum_{s=1}^{w_k-1} \sigma_s^k = \sum_{s=1}^{w_k-1} \gamma_3^{k,s} \rightarrow \sum_{s=1}^{w_k-1} (\sigma_s^k - \gamma_3^{k,s}) = 0 $$

The only solution of this system is $\sigma_s^k = \gamma_3^{k,s}$ for each $s \in \{1, ..., w_k - 1\}$ for the demand $k$. As $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$. We then get that

$$ \sigma_s^k = \gamma_3^{k,s}, \text{ for all } k \in K \text{ and all } s \in \{1, ..., w_k - 1\}. \qquad (52) $$

We conclude that for each $k' \in K$ and $e' \in E$

$$ \mu_{e'}^{k'} = \begin{cases} \gamma_1^{k', e'}, & \text{if } e' \in E_0^k, \\ \gamma_2^{k', e'}, & \text{if } e' \in E_1^k, \\ \rho, & \text{if } k' \in \tilde{K} \text{ and } e' = e, \\ 0, & \text{otherwise,} \end{cases} $$
and for each $k \in K$ and $s \in \mathbb{S}$

$$ \sigma_s^k = \begin{cases} \gamma_3^{k,s}, & \text{if } s \in \{1, \dots, w_k - 1\} \\ \rho, & \text{if } k \in \tilde{K} \text{ and } s \in \{s_i + w_k - 1, \dots, s_j\}, \\ 0, & \text{otherwise.} \end{cases} $$

$$ \text{As a result } (\mu, \sigma) = \sum_{k \in \tilde{K}} \rho \alpha_e^k + \sum_{s=s_i+w_k-1}^{s_j} \rho \beta_s^k + \gamma Q. $$

## 5.10 Edge-Capacity-Cover Inequalities

**Theorem 16.** Consider an edge e in E. Let C be a minimal cover in K for the edge e. Then, the inequality (39) is facet defining for the polytope $P(G, K, \mathbb{S}, C, e)$ where

$$ P(G, K, \mathbb{S}, C, e) = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{k' \in K \setminus (C \cup K_e)} x_e^{k'} = 0\}. $$

*Proof.* Let $F_C^e$ denote the face induced by the inequality (22), which is given by

$$ F_C^e = \{(x, z) \in P(G, K, \mathbb{S}, C, e) : \sum_{k \in C} x_e^k = |C| - 1\}. $$

In order to prove that inequality $\sum_{k \in C} x_e^k \le |C| - 1$ is facet defining for $P(G, K, \mathbb{S}, C, e)$, we start checking that $F_C^e$ is a proper face, and $F_C^e \ne P(G, K, \mathbb{S}, C, e)$.

We construct a solution $S^{63} = (E^{63}, S^{63})$ as below

- a feasible path $E_k^{63}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k^{63}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{63}$ with $|S_k^{63}| \ge 1$ (contiguity and continuity constraints),

- $\{s - w_k + 1, \dots, s\} \cap \{s' - w_{k'} + 1, \dots, s'\} = \emptyset$ for each $k, k' \in K$ and each $s \in S_k^{63}$ and $s' \in S_{k'}^{63}$ with $E_k^{63} \cap E_{k'}^{63} \ne \emptyset$ (non-overlapping constraint),

- and there is $|C| - 1$ demands from the cover C which pass through the edge e in the solution $S^{63}$ denoted by $C_{63}$ (i.e., if $k \in C_{63}$ means that the demand k selects the edge e for its routing in the solution $S^{63}$, i.e., $e \in E_k^{63}$ for each demand $k \in C_{63}$, $e' \notin E_{k'}^{63}$ for all $k' \in C \setminus C_{63}$.

Obviously, $S^{63}$ is a feasible solution for the problem given that it satisfies all the constraints of our cut formulation (2)-(12). Moreover, the corresponding incidence vector $(x^{S^{63}}, z^{S^{63}})$ is belong to $P(G, K, \mathbb{S}, C, e)$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| - 1$. As a result, $F_C^e$ is not empty (i.e., $F_C^e \ne \emptyset$). Furthermore, given that $e \in E \setminus (E_0^k \cup E_1^k)$ for each $k \in C$, this means that there exists at least one feasible routing $E_k$ for each demand k in C with $e \notin E_k$. This means that $F_C^e \ne P(G, K, \mathbb{S}, C, \Xi(C), e)$.

We denote the inequality $\sum_{k \in C} x_e^k \le |C| - 1$ by $\alpha x + \beta z \le \lambda$. Let $\mu x + \sigma z \le \tau$ be a valid inequality that is facet defining F of $P(G, K, \mathbb{S}, C, e)$. Suppose that $F_C^e \subset F = \{(x, z) \in P(G, K, \mathbb{S}, C, e) : \mu x + \sigma z = \tau\}$. We show that there exists $\rho \in \mathbb{R}$ and $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (s.t. $\gamma_1 \in \mathbb{R} \sum_{k \in K} |E_k^k|$, $\gamma_2 \in \mathbb{R} \sum_{k \in K} |E_1^k|$, $\gamma_3 \in \mathbb{R} \sum_{k \in K} (w_k - 1)$) s.t. $(\mu, \sigma) = \rho(\alpha, \beta) + \gamma Q$, and that

- $\sigma_s^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, \dots, \bar{s}\}$,

- and $\mu_{e'}^k = 0$ for all demands $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$ with $e \ne e'$ if $k \in C$,

- and all $\mu_e^k$ are equivalents for the set of demands in C.

We first show that $\mu_{e'}^k = 0$ for each edge $e' \in E \setminus (E_0^k \cup E_1^k)$ for each demand $k \in K$ with $e \ne e'$ if $k \in C$. For that, we consider a solution $S'^{63} = (E'^{63}, S'^{63})$ in which

- a feasible path $E_k'^{63}$ is assigned to each demand $k \in K$ (routing constraint),

- and a set of last-slots $S_k'^{63}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{63}$ with $|S_k'^{63}| \ge 1$ (contiguity and continuity constraints),
- and {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k, k' ∈ K$ and each $s' ∈ S_k'^{63}$ and $s'' ∈ S_{k'}'^{63}$ with $E_k'^{63} ∩ E_{k'}'^{63} ≠ ∅$, i.e., for each edge $e' ∈ E$ and each slot $s'' ∈ S$ we have $\sum_{k \in K, e' \in E_k'^{63}} |\{s' ∈ S_k'^{63}, s'' ∈ \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

- the edge $e'$ is not non-compatible edge with the selected edges $e'' ∈ E_k'^{63}$ of demand $k$ in the solution $S'^{63}$, i.e., $\sum_{e'' \in E_k'^{63}} l_{e''} + l_{e'} \le \bar{l}_k$. As a result, $E_k'^{63} \cup \{e'\}$ is a feasible path for the demand $k$,

- and there is $|C| - 1$ demands from the cover $C$ which pass through the edge $e$ in the solution $S'^{63}$ denoted by $C_{63}'$ (i.e., if $k \in C_{63}'$ means that the demand $k$ selects the edge $e$ for its routing in the solution $S'^{63}$, i.e., $e \in E_k'^{63}$ for each demand $k \in C_{63}'$, $e' \notin E_{k'}'^{63}$ for all $k' \in C \setminus C_{63}'$.

$S'^{63}$ is clearly feasible for the problem given that it satisfies all the constraints of cut formulation (2)-(12). Hence, the corresponding incidence vector $(x^{S'^{63}}, z^{S'^{63}})$ is belong to $F$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| + 1$. Based on this, we derive a solution $S^{64}$ obtained from the solution $S'^{63}$ by adding an unused edge $e' \in E \setminus (E_0^k \cup E_1^k)$ for the routing of demand $k$ in $K$ in the solution $S^{63}$ which means that $E_k^{64} = E_k'^{63} \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^{63}$ remain the same in the solution $S^{64}$, i.e., $S_k^{64} = S_k'^{63}$ for each $k \in K$, and $E_{k'}^{64} = E_{k'}'^{63}$ for each $k' \in K \setminus \{k\}$. $S^{64}$ is clearly feasible given that

- and a feasible path $E_k^{64}$ is assigned to each demand $k \in K$ (routing constraint),

- and a set of last-slots $S_k^{64}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{64}$ with $|S_k^{64}| \ge 1$ (contiguity and continuity constraints),

- and {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k, k' ∈ K$ and each $s' ∈ S_k^{64}$ and $s'' ∈ S_{k'}^{64}$ with $E_k^{64} \cap E_{k'}^{64} ≠ ∅$, i.e., for each edge $e' \in E$ and each slot $s'' ∈ S$ we have $\sum_{k \in K, e' \in E_k'^{64}} |\{s' ∈ S_k'^{64}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{64}}, z^{S^{64}})$ is belong to $F$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| + 1$. It follows that

$$\mu x^{S'^{63}} + \sigma z^{S'^{63}} = \mu x^{S^{64}} + \sigma z^{S^{64}} = \mu x^{S'^{63}} + \mu_{e'}^k + \sigma z^{S'^{63}}.$$

As a result, $\mu_{e'}^k = 0$ for demand $k$ and an edge $e'$.

As $e'$ is chosen arbitrarily for the demand $k$ with $e' \notin E_0^k \cup E_1^k$ and $e' \ne e'$ if $k \in C$, we iterate the same procedure for all $e \in E \setminus (E_0^k \cup E_1^k \cup \{e'\})$ with $e' \ne e''$ if $k \in C$. We conclude that for the demand $k$

$$\mu_{e'}^k = 0, \text{ for all } e' \in E \setminus (E_0^k \cup E_1^k) \text{ with } e' \ne e' \text{ if } k \in C.$$

Moreover, given that $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$ and all $e' \in E \setminus (E_0^k \cup E_1^k)$. We conclude at the end that

$$\mu_{e'}^k = 0, \text{ for all } k \in K \text{ and all } e' \in E \setminus (E_0^k \cup E_1^k) \text{ with } e' \ne e' \text{ if } k \in C.$$

Let's us show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$. For that, we consider a solution $S''^{63} = (E''^{63}, S''^{63})$ in which

- a feasible path $E_k''^{63}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k''^{63}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k''^{63}$ with $|S_k''^{63}| \ge 1$ (contiguity and continuity constraints),

- {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k, k' ∈ K$ and each $s' ∈ S_k''^{63}$ and $s'' ∈ S_{k'}''^{63}$ with $E_k''^{63} \cap E_{k'}''^{63} ≠ ∅$, i.e., for each edge $e' \in E$ and each slot $s'' ∈ S$ we have $\sum_{k \in K, e' \in E_k''^{63}} |\{s' \in S_k''^{63}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

- and {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k' \in K$ and $s'' \in S_{k'}''^{63}$ with $E_k''^{63} \cap E_{k'}''^{63} ≠ ∅$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k''^{63}$ assigned to the demand $k$ in the solution $S''^{63}$),

- and there is $|C| - 1$ demands from the cover $C$ which pass through the edge $e$ in the solution $S''^{63}$ denoted by $C''^{63}$ (i.e., if $k \in C''^{63}$ means that the demand $k$ selects the edge $e$ for its routing in the solution $S''^{63}$, i.e., $e \in E_k''^{63}$ for each demand $k \in C''^{63}$, $e'' \notin E_{k'}''^{63}$ for all $k' \in C \setminus C''^{63}$.
$S^{63}$ is clearly feasible for the problem given that it satisfies all the constraints of cut formulation (2)-(12). Hence, the corresponding incidence vector ($x^{S^{63}}, z^{S^{63}}$) is belong to $F$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| + 1$. Based on this, we distinguish two cases:

- without changing the paths established in $S^{63}$: we derive a solution $S^{65} = (E^{65}, S^{65})$ from the solution $S^{63}$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S^{63}$ (i.e., $E_k^{65} = E_k^{63}$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S^{63}$ remain the same in the solution $S^{65}$ i.e., $S_{k'}^{63} = S_{k'}^{65}$ for each demand $k' \in K \setminus \{k\}$, and $S_k^{65} = S_{k'}^{63} \cup \{s'\}$ for the demand $k$. The solution $S^{65}$ is feasible given that

* a feasible path $E_k^{65}$ is assigned to each demand $k \in K$ (routing constraint),

* a set of last-slots $S_k^{65}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{65}$ with $|S_k^{65}| \ge 1$ (contiguity and continuity constraints),

* $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{65}$ and $s'' \in S_{k'}^{65}$ with $E_k^{65} \cap E_{k'}^{65} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e' \in E_k^{65}} |\{s' \in S_k^{65}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector ($x^{S^{65}}, z^{S^{65}}$) is belong to $F$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| + 1$. We then obtain that

$$ \mu x^{S^{63}} + \sigma z^{S^{63}} = \mu x^{S^{65}} + \sigma z^{S^{65}} = \mu x^{S^{63}} + \sigma z^{S^{63}} + \sigma_{s'}^k. $$

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $k \notin C$.

- with changing the paths established in $S^{63}$: we construct a solution $S'^{65}$ derived from the solution $S^{63}$ by adding the slot $s'$ as last-slot to the demand $k$ with modifying the paths assigned to a subset of demands $\tilde{K} \subset K$ in $S^{63}$ (i.e., $E_k'^{65} = E_k^{63}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{65} \neq E_k^{63}$ for each $k \in \tilde{K}$) s.t.

* a new feasible path $E_k'^{65}$ is assigned to each demand $k \in \tilde{K}$ (routing constraint),

* and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k \in \tilde{K}$ and $k' \in K \setminus \tilde{K}$ and each $s' \in S_k^{63}$ and $s'' \in S_{k'}^{63}$ with $E_k'^{65} \cap E_{k'}^{65} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in S$ we have $\sum_{k \in \tilde{K}, e' \in E_k'^{65}} |\{s' \in S_k^{65}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e' \in E_k'^{65}} |\{s' \in S_k^{63}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

* and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k' \in \tilde{K}$ and $s'' \in S_{k'}^{63}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{63}$ assigned to the demand $k$ in the solution $S^{63}$).

The last-slots assigned to the demands $K \setminus \{k\}$ in $S^{63}$ remain the same in $S'^{65}$, i.e., $S_k'^{63} = S_{k'}'^{65}$ for each demand $k' \in K \setminus \{k\}$, and $S_k'^{65} = S_{k'}^{63} \cup \{s\}$ for the demand $k$. The solution $S'^{65}$ is clearly feasible given that

* a feasible path $E_k'^{65}$ is assigned to each demand $k \in K$ (routing constraint),

* a set of last-slots $S_k'^{65}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{65}$ with $|S_k'^{65}| \ge 1$ (contiguity and continuity constraints),

* $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k'^{65}$ and $s'' \in S_{k'}'^{65}$ with $E_k'^{65} \cap E_{k'}'^{65} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e' \in E_k'^{65}} |\{s' \in S_k'^{65}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector ($x^{S'^{65}}, z^{S'^{65}}$) is belong to $F$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| + 1$. We have so

$$ \mu x^{S^{63}} + \sigma z^{S^{63}} = \mu x^{S^{65}} + \sigma z^{S^{65}} = \mu x^{S^{63}} + \sigma z^{S^{63}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k^{63}} \mu_{e'}^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e'' \in E_k'^{65}} \mu_{e''}^{\tilde{k}}. $$

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $k \notin C$ given that $\mu_{e'}^k = 0$ for all the demand $k \in K$ and all edges $e' \in E \setminus (E_0^k \cup E_1^k)$ with $e \neq e'$ if $k \in C$.
The slot $s'$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ s.t. we find

$$ \sigma_{s'}^k = 0, \text{ for demand } k \text{ and all slots } s' \in \{w_k, ..., \bar{s}\}. $$

Given that the demand $k$ is chosen arbitrarily. We iterate the same thing for all the demands $k'$ in $K \setminus \{k\}$ such that

$$ \sigma_s^{k'} = 0, \text{ for all } k' \in K \setminus \{k\} \text{ and all slots } s \in \{w_{k'}, ..., \bar{s}\}. $$

Consequently, we conclude that

$$ \sigma_s^k = 0, \text{ for all } k \in K \text{ and all slots } s \in \{w_k, ..., \bar{s}\}. $$

Let us prove now that $\mu_e^k$ for all $k \in K$ with $k \in C$ are equivalents. For that, we consider a demand $k'$ in $C$ s.t. $e \notin E_{k'}^{63}$. For that, we consider a solution $S^{66} = (E^{66}, S^{66})$ from the solution $S^{63}$ by

- selecting a demand $k$ from $C_{63}$ s.t. the demand $k$ used the edge $e$ for its routing in the solution $S^{63}$,

- the paths assigned to the demands $K \setminus \{k, k'\}$ in $S^{63}$ remain the same in $S^{66}$ (i.e., $E_{k'}^{66} = E_{k''}^{63}$ for each $k'' \in K \setminus \{k, k'\}$),

- without modifying the last-slots assigned to the demands $K$ in $S^{63}$, i.e., $S_k^{63} = S_k^{66}$ for each demand $k \in K$,

- modifying the path assigned to the demand $k'$ in $S^{63}$ from $E_{k'}^{63}$ to a path $E_{k'}^{66}$ passed through the edge $e$ (i.e., $e \in E_{k'}^{66}$) with $k' \in C$ s.t. $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k \in K$ and each $s' \in S_{k'}^{63}$ and each $s \in S_k^{63}$ with $E_{k'}^{63} \cap E_{k'}^{66} \neq \emptyset$,

- modifying the path assigned to the demand $k$ in $S^{63}$ with $e \in E_k^{63}$ and $k \in C$ from $E_k^{63}$ to a path $E_k^{66}$ without passing through the edge $e$ (i.e., $e \notin E_k^{66}$) and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k'' \in K \setminus \{k, k'\}$ and each $s \in S_k^{63}$ and each $s' \in S_k^{63}$ with $E_k^{63} \cap E_k^{66} \neq \emptyset$, and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $s \in S_k^{63}$ and each $s' \in S_k^{63}$ with $E_k^{66} \cap E_k^{66} \neq \emptyset$.

The solution $S^{66}$ is feasible given that

- a feasible path $E_k^{66}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k^{66}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{66}$ with $|S_k^{66}| \geq 1$ (contiguity and continuity constraints),

- $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{66}$ and $s'' \in S_{k'}^{66}$ with $E_k^{66} \cap E_{k'}^{66} \neq \emptyset$, i.e., for each edge $e \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e \in E_k^{66}} |\{s' \in S_k^{66}, s'' \in \{s' - w_k + 1, ..., s'\}| \leq 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{66}}, z^{S^{66}})$ is belong to $F$ and then to $F_C^e$ given that it is composed by $\sum_{k \in C} x_e^k = |C| - 1$. We then obtain that

$$ \mu x^{S^{63}} + \sigma z^{S^{63}} = \mu x^{S^{66}} + \sigma z^{S^{66}} = \mu x^{S^{63}} + \sigma z^{S^{63}} + \mu_e^{k'} - \mu_e^k + \sum_{e'' \in E_{k'}^{66} \setminus \{e\}} \mu_{e''}^{k'} - \sum_{e'' \in E_{k'}^{63}} \mu_{e''}^{k'} + \sum_{e'' \in E_k^{66}} \mu_{e''}^k - \sum_{e'' \in E_k^{63} \setminus \{e\}} \mu_{e''}^k. $$

It follows that $\mu_e^{k'} = \mu_e^k$ for demand $k'$ and a edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$ with $v_{k'} \in C$ given that $\mu_{e''}^k = 0$ for all $k \in K$ and all $e'' \in E \setminus (E_0^k \cup E_1^k)$ with $k \notin C$.

Given that the pair $(k, k')$ are chosen arbitrary in the cover $C$, we iterate the same procedure for all pairs $(k, k')$ s.t. we find

$$ \mu_e^k = \mu_e^{k'}, \text{ for all pairs } (k, k') \in C. $$

Consequently, we conclude that

$$ \mu_e^k = \rho, \text{ for all } k \in C. $$
On the other hand, we ensure that all $e' \in E_0^k$ for each demand $k$ are independants s.t. for each demand $k \in K$ we have

$$ \sum_{e' \in E_0^k} \mu_{e'}^k = \sum_{e' \in E_0^k} \gamma_1^{k,e'} \rightarrow \sum_{e' \in E_0^k} (\mu_{e'}^k - \gamma_1^{k,e'}) = 0. $$

The only solution of this system is $\mu_{e'}^k = \gamma_1^{k,e'}$ for each $e' \in E_0^k$ for the demand $k$. As $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$. We conclude that

$$ \mu_{e'}^k = \gamma_1^{k,e'}, \text{ for all } k \in K \text{ and all } e' \in E_0^k, $$

We re-do the same thing for the edges $e' \in E_1^k$ for each demand $k$ which are independants s.t. for each demand $k \in K$ we have

$$ \sum_{e' \in E_1^k} \mu_{e'}^k = \sum_{e' \in E_1^k} \gamma_2^{k,e'} \rightarrow \sum_{e' \in E_1^k} (\mu_{e'}^k - \gamma_2^{k,e'}) = 0 $$

The only solution of this system is $\mu_{e'}^k = \gamma_2^{k,e'}$ for each $e' \in E_1^k$ for the demand $k$. As $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$. We conclude that

$$ \mu_{e'}^k = \gamma_2^{k,e'}, \text{ for all } k \in K \text{ and all } e' \in E_1^k, $$

Furthermore, all the slots $s \in \{1, ..., w_k - 1\}$ for each demand $k$ are independants s.t. for each demand $k \in K$, we have

$$ \sum_{s=1}^{w_k-1} \sigma_s^k = \sum_{s=1}^{w_k-1} \gamma_3^{k,s} \rightarrow \sum_{s=1}^{w_k-1} (\sigma_s^k - \gamma_3^{k,s}) = 0 $$

The only solution of this system is $\sigma_s^k = \gamma_3^{k,s}$ for each $s \in \{1, ..., w_k - 1\}$ for the demand $k$. As $k$ is chosen arbitrarily in $K$, we iterate the same procedure for all $k' \in K \setminus \{k\}$. We then get that

$$ \sigma_s^k = \gamma_3^{k,s}, \text{ for all } k \in K \text{ and all } s \in \{1, ..., w_k - 1\}. \qquad (53) $$

We conclude that for each $k' \in K$ and $e' \in E$

$$ \mu_{e'}^{k'} = \begin{cases} \gamma_1^{k',e'}, & \text{if } e' \in E_0^k, \\ \gamma_2^{k',e'}, & \text{if } e' \in E_1^k, \\ \rho, & \text{if } k' \in C \text{ and } e' = e, \\ 0, & \text{otherwise,} \end{cases} $$

and for each $k \in K$ and $s \in \mathbb{S}$

$$ \sigma_s^k = \begin{cases} \gamma_3^{k,s}, & \text{if } s \in \{1, ..., w_k - 1\} \\ 0, & \text{otherwise.} \end{cases} $$

$$ \text{As a result } (\mu, \sigma) = \sum_{k \in C} \rho \alpha_e^k + \gamma Q. $$

# 6 Conclusion

In this paper, we studied the Constrained-Routing and Spectrum Assignment problem. We introduced integer linear programming based on cut formulation for the problem. We investigated the facial structure of the associated polyhedron, and derived valid inequalities that are facet defining under sufficient conditions. Based on these results, we develop a Branch-and-Cut algorithm to solve the problem [16]. The valid inequalities are shown to be efficient and allow improving the effectiveness of our B&C algorithm [16].
References

1. Amar, D. : Performance assessment and modeling of flexible optical networks. Theses, Institut National des Télécommunications 2016.

2. Balas, E. : Facets of the knapsack polytope. In: Journal of Mathematical Programming 1975, pp. 146-164.

3. Bertero, F., and Bianchetti, M., and Marenco, J. : Integer programming models for the routing and spectrum allocation problem. In: Official Journal of the Spanish Society of Statistics and Operations Research 2018, pp. 465-488.

4. Cai, A., Shen, G., Peng, L., and Zukerman, M. : Novel Node-Arc Model and Multiiteration Heuristics for Static Routing and Spectrum Assignment in Elastic Optical Networks. In: Journal of Lightwave Technology 2013, pp. 3402-3413.

5. Carlyle, W.M., Royset, J.O., and Wood, R.K.: Lagrangian relaxation and enumeration for solving constrained shortest-path problems. In: Networks Journal 2008, pp. 256-270.

6. Chatterjee, B.C., and Ba, S., and Oki, E. : Routing and Spectrum Allocation in Elastic Optical Networks: A Tutorial. In: IEEE Communications Surveys Tutorials 2015, pp. 1776-1800.

7. Chatterjee, B.C., and Ba, S., and Oki, E. : Fragmentation Problems and Management Approaches in Elastic Optical Networks: A Survey. In: IEEE Communications Surveys Tutorials 2018, pp. 183-210.

8. Chen, X., and Guo, J., and Zhu, Z., and Proietti, R., and Castro, A., and Yoo, S.J.B. : Deep-RMSA: A Deep-Reinforcement-Learning Routing, Modulation and Spectrum Assignment Agent for Elastic Optical Networks. In: Optical Fiber Communications Conference and Exposition (OFC) 2018, pp. 1-3.

9. Cheng, B., and Hang, C., and Hu, Y., and Liu, S., and Yu, J., and Wang, Y., and Shen, J. : Routing and Spectrum Assignment Algorithm based on Spectrum Fragment Assessment of Arriving Services. In: 28th Wireless and Optical Communications Conference (WOCC) 2019, pp. 1-4.

10. Chouman, H., and Gravey, A., and Gravey, P., and Hadhbi, Y., and Kerivin, H., and Morvan, M, and Wagler, A.: Impact of RSA Optimization Objectives on Optical Network State. In: https://hal.uca.fr/hal-03155966.

11. Chouman, H., and Luay, A., and Colares, R., and Gravey, A, and Gravey, P., and Kerivin, H., and Morvan, M., and Wagler, A.: Assessing the Health of Flexgrid Optical Networks. In: https://hal.archives-ouvertes.fr/hal-03123302.

12. Christodoulopoulos, K., Tomkos, I., and Varvarigos, E.A. : Elastic Bandwidth Allocation in Flexible OFDM-Based Optical Networks. In: Lightwave Technology 2011, pp. 1354-1366.

13. Chudnovsky, M., and Scott, A., and Seymour, P., and Spirkl, S. : Detecting an Odd Hole. In: Journal of the ACM 2020, pp. 1-15.

14. Cplex, I.I., 2020. V12. 9: User's Manual for CPLEX. International Business Machines Corporation, 46(53), pp. 157.

15. Colares, R., Kerivin, H., and Wagler, A. : An extended formulation for the Constraint Routing and Spectrum Assignment Problem in Elastic Optical Networks. In: https://hal.uca.fr/hal-03156189, 2021.

16. Diarassouba, I., Hadhbi, Y., and Mahjoub, A.R.: Valid Inequalities and Branch-and-Cut Algorithm for the Constrained-Routing and Spectrum Assignment Problem. In: Research Report, July 2021, hal-03287146.

17. Diarassouba, I., Hadhbi, Y., and Mahjoub, A.R.: On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part I. In: Research Report in Hal UCA, July 2021, hal-03287174.

18. Ding, Z., and Xu, Z., and Zeng, X., and Ma, T., and Yang, F. : Hybrid routing and spectrum assignment algorithms based on distance-adaptation combined coevolution and heuristics in elastic optical networks. In: Journal of Optical Engineering 2014, pp. 1-10.

19. Dror, M. : Note on the Complexity of the Shortest Path Models for Column Generation in VRPTW. In: Journal of Operations Research 1994, pp. 977-978.

20. Dumitrescu, I., and Boland, N.: Algorithms for the weight constrained shortest path problem. In: International Transactions in Operational Research, pp. 15-29.

21. Enoch, J. : Nested Column Generation decomposition for solving the Routing and Spectrum Allocation problem in Elastic Optical Networks. In: http://arxiv.org/abs/2001.00066, 2020.

22. Eppstein, D. : Finding the k shortest paths. In: 35th Annual Symposium on Foundations of Computer Science, pp. 154-165.

23. Fayez, M., and Katib, I., and George, N.R., and Gharib, T.F., and Khaleed H., and Faheem, H.M. : Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem. In: Ain Shams Engineering Journal 2020, pp. 273-280.

24. Ford, L. R., and Fulkerson, D. R. : Maximal flow through a network. In: Canadian Journal of Mathematics 8, pp. 399404, 1956.
25. Gong, L., and Zhou, X., and Lu, W., and Zhu, Z.: A Two-Population Based Evolutionary Approach for Optimizing Routing, Modulation and Spectrum Assignments (RMSA) in O-OFDM Networks. In: IEEE Communications Letters 2012, pp. 1520-1523.

26. Goldberg, A.V., and Tarjan, R.E.: A New Approach to the Maximum Flow Problem. In: Proceedings of the Eighteenth Annual Association for Computing Machinery Symposium on Theory of Computing 1986, pp. 136-146.

27. Goscien, R., and Walkowiak, K., and Klinkowski, M.: Tabu search algorithm, Routing, Modulation and spectrum allocation, Anycast traffic, Elastic optical networks. In: Journal of Computer Networks 2015, pp. 148-165.

28. Grötschel, M., Lovász, L., and Schrijver, A.: Geometric Algorithms and Combinatorial Optimization. In: Springer 1988.

29. Gu, R., Yang, Z., and Ji, Y.: Machine Learning for Intelligent Optical Networks: A Comprehensive Survey. In: Journal CoRR 2020, pp. 1-42.

30. Gurobi Optimization, LLC.: Gurobi Optimizer Reference Manual. In: https://www.gurobi.com, 2021.

31. Hadhbi, Y., Kerivin, H., and Wagler, A.: A novel integer linear programming model for routing and spectrum assignment in optical networks. In: Federated Conference on Computer Science and Information Systems (FedCSIS) 2019, pp. 127-134.

32. Hadhbi, Y., Kerivin, H., and Wagler, A.: Routage et Affectation Spectrale Optimaux dans des Réseaux Optiques Élastiques FlexGrid. In: Journées Polyédres et Optimisation Combinatoire (JPOC-Metz) 2019, pp. 1-4.

33. Hai, D.H., and Hoang, K.M.: An efficient genetic algorithm approach for solving routing and spectrum assignment problem. In: Journal of Recent Advances in Signal Processing 2017.

34. Hai, D.H., and Morvan, M., and Gravey, P.: Combining heuristic and exact approaches for solving the routing and spectrum assignment problem. In: Journal of Iet Optoelectronics 2017, pp. 65-72.

35. He, S., Qiu, Y., and Xu, J.: Invalid-Resource-Aware Spectrum Assignment for Advanced-Reservation Traffic in Elastic Optical Network. In: Sensors 2020.

36. Jaumard, B., and Daryalal, M.: Scalable elastic optical path networking models. In: 18th International Conference Transparent Optical Networks (ICTON) 2016, pp. 1-4.

37. Jiang, R., and Feng, M., and Shen, J.: An defragmentation scheme for extending the maximal unoccupied spectrum block in elastic optical networks. In: 16th International Conference on Optical Communications and Networks (ICOCN) 2017, pp. 1-3.

38. Jinno, M., Takara, H., Kozicki, B., Tsukishima, Y., Yoshimatsu, T., Kobayashi, T., Miyamoto, Y., Yonenaga, K., Takada, A., Ishida, O., and Matsuoka, S.: Demonstration of novel spectrum-efficient elastic optical path network with per-channel variable capacity of 40 Gb/s to over 400 Gb/s. In: 34th European Conference on Optical Communication 2008.

39. Joksch, H.C.: The shortest route problem with constraints. In: Journal of Mathematical Analysis and Applications, pp. 191-197.

40. https://lemon.cs.elte.hu/trac/lemon.

41. Lezama, F., Martinez-Herrera, A.F., Castanon, G., Del-Valle-Soto, C., Sarmiento, A.M., Munoz de Cote, A.: Solving routing and spectrum allocation problems in flexgrid optical networks using pre-computing strategies. In: Journal of Photon Netw Commun 41, pp. 17-35.

42. Liu, L., and Yin, S., and Zhang, Z., and Chu, Y., and Huang, S.: A Monte Carlo Based Routing and Spectrum Assignment Agent for Elastic Optical Networks. In: Asia Communications and Photonics Conference (ACP) 2019, pp. 1-3.

43. Lohani, V., Sharma, A., and Singh, Y.N.: Routing, Modulation and Spectrum Assignment using an AI based Algorithm. In: 11th International Conference on Communication Systems & Networks (COMSNETS) 2019, pp. 266-271.

44. Lopez, V., and Velasco, L.: Elastic Optical Networks: Architectures, Technologies, and Control. In: Springer Publishing Company, Incorporated 2016.

45. Lozano, L., and Medaglia, A.L.: On an exact method for the constrained shortest path problem. In: Journal of Computers & Operations Research, pp. 378-384.

46. Mahala, N., and Thangaraj, J.: Spectrum assignment technique with first-random fit in elastic optical networks. In: 4th International Conference on Recent Advances in Information Technology (RAIT) 2018, pp. 1-4.

47. Margot, F.: Symmetry in integer linear programming. In: 50 Years of Integer Programming 1958-2008, Springer, 2010, pp. 647-686.

48. Margot, F.: Pruning by isomorphism in branch-and-cut. In: Mathematical Programming 2002, pp. 71-90.

49. Margot, F.: Exploiting orbits in symmetric ilp. In: Mathematical Programming 2003, pp. 3-21.

50. Méndez-Díaz, I. and Zabala, P.: A Branch-and-Cut algorithm for graph coloring. In: Discrete Applied Mathematics Journal 2006, pp. 826-847.
51. Mesquita, L.A.J., and Assis, K., and Santos, A.F., and Alencar, M., and Almeida, R.C.: A Routing and Spectrum Assignment Heuristic for Elastic Optical Networks under Incremental Traffic. In: SBFoton International Optics and Photonics Conference (SBFoton IOPC) 2018, pp. 1-5.

52. Nemhauser, G.L., and Wolsey, L.A.: Integer and Combinatorial Optimization. In: John Wiley 1988.

53. Nemhauser, G. L., and Sigismondi, G.: A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing. In: The Journal of the Operational Research Society 1992, pp. 443-457.

54. Orlowski, S., Pióro, M., Tomaszewski, A., and Wessäly, R.: SNDlib 1.0-Survivable Network Design Library. In: Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium, http://www.zib.de/orlowski/Paper/OrlowskiPioroTomaszewskiWessaely2007-SNDlib-INOC.pdf.gz.

55. Ostrowski, J., Anjos, M. F., and Vannelli, A.: Symmetry in scheduling problems. In: Citeseer 2010.

56. Ostrowski, J., Linderoth, J., Rossi, F., and Smriglio, S.: Orbital branching. In: Mathematical Programming 2011, pp. 147-178.

57. Padberg, M.W.: On the facial structure of set packing polyhedra. In: Journal of Mathematical Programming 1973, pp. 199-215.

58. Patel, B., and Ji, H., and Nayak, S., and Ding, T., and Pan, Y. and Aibin, M.: On Efficient Candidate Path Selection for Dynamic Routing in Elastic Optical Networks. In: 11th IEEE Annual Ubiquitous Computing 2020, pp. 889-894.

59. Kaibel, V., and Pfetsch, M. E.: Packing and partitioning orbitopes. In: Mathematical Programming 2008, pp. 1-36.

60. Kaibel, V., Peinhardt, M., and Pfetsch, M. E.: Orbitopal fixing. In: Discrete Optimization 2011, pp. 595-610.

61. Karp, R.M.: Reducibility among Combinatorial Problems. In: Complexity of Computer Computations: Proceedings of a symposium on the Complexity of Computer Computations, held March 20-22, 1972, at the IBM Thomas J. Watson Research Center 1972, pp. 85-94.

62. Klabjan, D., Nemhauser, G.L., and Tovey, C.: The complexity of cover inequality separation. In: Journal of Operations Research Letters 1998, pp. 35-40.

63. Klinkowski, M., Pedro, J., Careglio, D., Pioro, M., Pires, J., Monteiro, P., and Sole-Pareta, J.: An overview of routing methods in optical burst switching networks. In: Optical Switching and Networking 2010, pp. 41-53.

64. Klinkowski, M., and Walkowiak, K.: Routing and Spectrum Assignment in Spectrum Sliced Elastic Optical Path Network. In: IEEE Communications Letters 2011, pp. 884-886.

65. Klinkowski, M., Pioro, M., Zotkiewicz, M., Ruiz, M., and Velasco, L.: Valid inequalities for the routing and spectrum allocation problem in elastic optical networks. In: 16th International Conference on Transparent Optical Networks (ICTON) 2014, pp. 1-5.

66. Klinkowski, M., Pioro, M., Zotkiewicz, M., Ruiz, M., and Velasco, L.: A Simulated Annealing Heuristic for a Branch and Price-Based Routing and Spectrum Allocation Algorithm in Elastic Optical Networks. In: Intelligent Data Engineering and Automated Learning - IDEAL 2015, Springer International Publishing, pp. 290-299.

67. Panigrahi, D.: Gomory-Hu Trees. In: Encyclopedia of Algorithms 2014, Springer Berlin Heidelberg, pp. 1-4.

68. Ramaswami, R.: Optical Networks: A Practical Perspective, 3rd Edition. In: Morgan Kaufmann Publishers Inc. 2009.

69. Ramaswami, R., Sivarajan, K., and Sasaki, G.: Multiwavelength lightwave networks for computer communication. In: IEEE Communications Magazine 1993, pp. 78-88.

70. Rebennack, S.: Stable Set Problem: Branch & Cut Algorithms. In: Encyclopedia of Optimization Book 2009.

71. Rebennack, S., and Reinelt, G., and Pardalos, P.M.: A tutorial on branch and cut algorithms for the maximum stable set problem. In: Journal of International Transactions in Operational Research 2012, pp. 161-199.

72. Ruiz, M., Pioro, M., Zotkiewicz, M., Klinkowski, M., Velasco, L.: A hybrid meta-heuristic approach for optimization of routing and spectrum assignment in Elastic Optical Network (EON). In: Journal of Enterprise Information Systems 2020, pp. 11-24.

73. Ruiz, M., Pioro, M., Zotkiewicz, M., Klinkowski, M., Velasco, L.: Column generation algorithm for RSA problems in flexgrid optical networks. In: Photonic Network Communications 2013, pp. 53-64.

74. Ryan, D. M. and Foster, B. A.: An integer programming approach to scheduling. In A. Wren (editor), Computer Scheduling of Public Transport Urban Passenger Vehicle and Crew Scheduling, North-Holland, Amsterdam, 1981, pp. 269-280.

75. Salameh, B.H., Qawasmeh, R., and Al-Ajlouni, A.F.: Routing With Intelligent Spectrum Assignment in Full-Duplex Cognitive Networks Under Varying Channel Conditions. In: Journal of IEEE Communications Letters 2020, pp. 872-876.
76. Salani, M., and Rottondi, C., and Tornatore, M. : Routing and Spectrum Assignment Integrating Machine-Learning-Based QoT Estimation in Elastic Optical Networks. In: IEEE INFOCOM - IEEE Conference on Computer Communications 2019, pp. 173846.

77. Santos, A.F.D, and Assis, K., and Guimarães, M.A., and Hebraico, R.: Heuristics for Routing and Spectrum Allocation in Elastic Optical Path Networks. In: 2015, Journal Of Modern Engineering Research (IJMER), pp. 1-13.

78. Gamrath, G., Anderson, D., Bestuzheva, K., Chen, W.K., Eifler, L., Gasse, M., Gemander, P., Gleixner, A., Gottwald, L., Halbig, K., and Hendel, G., and Hojny, C., Koch, T., Bodic, L., Maher, P. J., Matter, F., Miltenberger, M., Mühmer, E., Müller, B., Pfetsch, M.E., Schlösser, F., Serrano, F., Shinano, Y., Tawfik, C., Vigerske, S., Wegscheider, F., Weninger, D., and Witzig, J.: The SCIP Optimization Suite 7.0. In: http://www.optimization-online.org/DB_HTML/2020/03/7705.html, March 2020.

79. Selvakumar, S., and Manivannan, S.S. : The Recent Contributions of Routing and Spectrum Assignment Algorithms in Elastic Optical Network (EON). In: International Journal of Innovative Technology and Exploring Engineering (IJITEE) 2020, pp. 1-11.

80. Shirazipourazad, S., Zhou, C., Derakhshandeh, Z., and Sen, A. : On routing and spectrum allocation in spectrum-sliced optical networks. In: Proceedings IEEE INFOCOM 2013, pp. 385-389.

81. Schrijver, A. : Combinatorial Optimization - Polyhedra and Efficiency. In: Springer-Verlag 2003.

82. Schrijver, A. : Theory of Linear and Integer Programming. In: John Wiley & Sons, Chichester 1986.

83. Talebi, S., Alam, F., Katib, I., Khamis, M., Salama, R., and Rouskas, G. N. : Spectrum management techniques for elastic optical networks: A survey. In: Optical Switching and Networking 2014.

84. The Network Cisco's Technology News Site: Cisco Predicts More IP Traffic in the Next Five Years Than in the History of the Internet. In: https://newsroom.cisco.com.

85. Trotter, L.E. : A class of facet producing graphs for vertex packing polyhedra. In: Journal of Discrete Mathematics 1975. pp. 373-388.

86. Velasco, L., Klinkowski, M., Ruiz, M., and Comellas, J. : Modeling the routing and spectrum allocation problem for flexgrid optical networks. In: Photonic Network Communications 2012, pp. 177-186.

87. Walkowiak, K., and Aibin, M. : Elastic optical networks - a new approach for effective provisioning of cloud computing and content-oriented services. In: Przeglad Telekomunikacyjny + Wiadomosci Telekomunikacyjne 2015.

88. Wan, X., and Hua, N., and Zheng, X.: Dynamic Routing and Spectrum Assignment in Spectrum-Flexible Transparent Optical Networks. In: Journal of Optical Communications and Networking 2012, pp. 603-613.

89. Xuan, H., Wang, Y., Xu, Z., Hao, S., and Wang, X. : New bi-level programming model for routing and spectrum assignment in elastic optical network. In: Opt Quant Electron 49-2017, pp. 1-16.

90. Zhang, Y., Xin, J., and Li, X., and Huang, S. : Overview on routing and resource allocation based machine learning in optical networks. In: Journal of Optical Fiber Technology, pp. 1-21.

91. Zhou, Y., and Sun, Q., and Lin, S. : Link State Aware Dynamic Routing and Spectrum Allocation Strategy in Elastic Optical Networks. In: IEEE Access 2020, pp. 45071-45083.

92. Zhu, Q., and Yu, X., and Zhao, Y., and Zhang, J.: Layered Graph based Routing and Spectrum Assignment for Multicast in Fixed/Flex-grid Optical Networks. In: Journal of Asia Communications and Photonics Conference/International Conference on Information Photonics and Optical Communications 2020 (ACP/IPOC), pp. 1-3.

93. Zotkiewicz, M., Pioro, M., Ruiz, M., Klinkowski, M., and Velasco, L. : Optimization models for flexgrid elastic optical networks. In: 15th International Conference on Transparent Optical Networks (ICTON) 2013, pp. 1-4.