## Sufficiency.

Let $F_{H,C}^{\tilde{G}_S^E}$ denote the face induced by the inequality (32), which is given by

$$F_{H,C}^{\tilde{G}_S^E} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}\}.$$

In order to prove that inequality $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} \le \frac{|H|-1}{2}$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_{H,C}^{\tilde{G}_S^E}$ is a proper face, and $F_{H,C}^{\tilde{G}_S^E} \ne P(G, K, \mathbb{S})$. We construct a solution $S^{24} = (E^{24}, S^{24})$ as below

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

- a set of last-slots $S_k^{24}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{24}$ with $|S_k^{24}| \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^{24}$ and $s' \in S_{k'}^{24}$ with $E_k^{24} \cap E_{k'}^{24} \ne \emptyset$ (non-overlapping constraint),

- and there is $\frac{|H|-1}{2}$ pairs of demand $k$ and slot $s$ from the odd-hole $H$ (i.e., $v_{k,s} \in H$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S^{24}$ denoted by $\tilde{H}_{24}$, i.e., $s \in S_k^{24}$ for each $v_{k,s} \in \tilde{H}_{24}$, and $s' \notin S_{k'}^{24}$ for all $v_{k',s'} \in H \setminus \tilde{H}_{24}$.

Obviously, $S^{24}$ 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^{24}}, z^{S^{24}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$.

As a result, $F_{H,C}^{\tilde{G}_S^E}$ is not empty (i.e., $F_{H,C}^{\tilde{G}_S^E} \ne \emptyset$). Furthermore, given that $s \in \{w_k, ..., \bar{s}\}$ for each $v_{k,s} \in H$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $H$ with $s \notin S_k$ for each $v_{k,s} \in H$. This means that $F_{H,C}^{\tilde{G}_S^E} \ne P(G, K, \mathbb{S})$.

Let denote the inequality $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} \le \frac{|H|-1}{2}$ 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})$. Suppose that $F_{H,C}^{\tilde{G}_S^E} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \mu x + \sigma z = \tau\}$. We show that there exist $\rho \in \mathbb{R}$ and $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (s.t. $\gamma_1 \in \mathbb{R} \sum_{k \in K} |E_0^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, ..., \bar{s}\}$ with $v_{k,s} \notin H \cup C$ as done in the proof of theorem 5,

- 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)$ as done in the proof of theorem 5,

- and $\sigma_s^k$ are equivalents for all $v_{k,s} \in H$ as done in the proof of theorem 5,

given that the solutions $S^{16} - S^{23}$ still feasible given that their corresponding incidence vectors are belong to $P(G, K, \mathbb{S})$ and then to $F_{H,C}^{\tilde{G}_S^E}$ given that they are composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. In what follows, we prove that $\sigma_{s'}^k$ are equivalents for all $v_{k',s'} \in C$.

To do so, we consider a node $v_{k,s'}^k \in C$, and a solution $S^{25} = (E^{25}, S^{25})$ in which

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

- a set of last-slots $S_k^{25}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{25}$ with $|S_k^{25}| \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^{25}$ and $s'' \in S_{k'}^{25}$ with $E_k^{25} \cap E_{k'}^{25} \ne \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^{25}} |\{s' \in S_k^{25}, 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^{25}$ with $E_k^{25} \cap E_{k'}^{25} \ne \emptyset$,

- and there is $\frac{|H|-1}{2}$ pairs of demand $k$ and slot $s$ from the odd-hole $H$ (i.e., $v_{k,s} \in H$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S^{25}$ denoted by $H'_{25}$, i.e., $s \in S_k^{25}$ for each $v_{k,s} \in H'_{25}$, and $s' \notin S_{k'}^{25}$ for all $v_{k',s'} \in H \setminus H'_{25}$.
$\mathcal{S}^{25}$ is clearly feasible for the problem given that it satisfies all the constraints of cut formulation (2)-(12). Hence, the corresponding incidence vector $(x^{\mathcal{S}^{25}}, z^{\mathcal{S}^{25}})$ is belong to $F$ and then to $F_{H,C}^{\mathcal{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. Based on this, we distinguish two cases:

- without changing the paths established in $\mathcal{S}^{25}$: we derive a solution $\mathcal{S}^{26}$ from the solution $\mathcal{S}^{25}$ by

* without modifying the paths assigned to the demands $K$ in $\mathcal{S}^{25}$ (i.e., $E_k^{26} = E_k^{25}$ for each $k \in K$),

* and the last-slots assigned to the demands $K \setminus (\{k \in K \text{ with } v_{k,s} \in \tilde{H}_{25}\} \cup \{k'\})$ in $\mathcal{S}^{25}$ remain the same in $\mathcal{S}^{26}$, i.e., $S_k^{25} = S_{k'}^{26}$ for each demand $k'' \in K \setminus (\{k \in K \text{ with } v_{k,s} \in \tilde{H}_{25}\} \cup \{k'\})$,

* and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $S_{k'}^{26} = S_{k'}^{25} \cup \{s'\}$ with $v_{k',s'} \in C$,

* and modifying the last-slots assigned to each demand $k \in \{\tilde{k} \in K \text{ with } v_{\tilde{k},s} \in \tilde{H}_{25}\}$ by adding a new last-slot $\tilde{s}_k$ and removing the last slot $s_k \in S_k^{25}$ with $v_{k,s_k} \in H$ and $v_{k,\tilde{s}_k} \notin H \cup C$ s.t. $S_k^{26} = (S_k^{25} \setminus \{s_k\}) \cup \{\tilde{s}_k\}$ for each demand $k \in \{\tilde{k} \in K \text{ with } v_{\tilde{k},s} \in \tilde{H}_{25}\}$ s.t. $\{\tilde{s} - w_k + 1, \dots, \tilde{s}\} \cap \{s' - w_{k'} + 1, \dots, s'\} = \emptyset$ for each $k' \in K$ and $s' \in S_{k'}^{26}$ with $E_k^{26} \cap E_{k'}^{26} \neq \emptyset$.

The solution $\mathcal{S}^{26}$ is clearly feasible given that

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

* a set of last-slots $S_k^{26}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{26}$ with $|S_k^{26}| \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^{26}$ and $s'' \in S_{k'}^{26}$ with $E_k^{26} \cap E_{k'}^{26} \neq \emptyset$, i.e., for each edge $e \in E$ and each slot $s'' \in \mathcal{S}$ we have $\sum_{k \in K, e \in E_k^{26}} |\{s' \in S_k^{26}, s'' \in \{s' - w_k + 1, \dots, s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{\mathcal{S}^{26}}, z^{\mathcal{S}^{26}})$ is belong to $F$ and then to $F_{H,C}^{\mathcal{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. We have so

$$ \mu x^{\mathcal{S}^{25}} + \sigma z^{\mathcal{S}^{25}} = \mu x^{\mathcal{S}^{26}} + \sigma z^{\mathcal{S}^{26}} = \mu x^{\mathcal{S}^{25}} + \sigma z^{\mathcal{S}^{25}} + \sigma_{s_k}^{k'} - \sum_{(k,s_k) \in \tilde{H}_{25}} \sigma_{s_k}^{k} + \sum_{k \in \{\tilde{k} \in K \text{ with } v_{\tilde{k},s} \in \tilde{H}_{25}\}} \sigma_{\tilde{s}_k}^{k}. $$

It follows that $\sigma_{s'}^{k'} = \sum_{(k,s_k) \in \tilde{H}_{25}} \sigma_{s_k}^k$ for demand $k'$ and a slot $s' \in \{w_{k'}, \dots, \bar{s}\}$ with $v_{k',s'} \in C$ given that $\sigma_{\tilde{s}_k}^k = 0$ for $v_{k,\tilde{s}_k} \notin H \cup C$. As a result, $\sigma_{s'}^{k'} = \rho \frac{|H|-1}{2}$ given that $\sigma_s^k$ are equivalents for all $v_{k,s} \in H$. This means that $\sigma_{s'}^{k'} = \sigma_s^k$ for all pairs $(v_{k,s}, v_{k',s'}) \in C$.

- with changing the paths established in $\mathcal{S}^{25}$: we construct a solution $\mathcal{S}^{\prime 26}$ derived from the solution $\mathcal{S}^{25}$ by

* with modifying the paths assigned to a subset of demands $\tilde{K} \subset K$ in $\mathcal{S}^{25}$ (i.e., $E_k^{\prime 26} = E_k^{25}$ for each $k \in K \setminus \tilde{K}$, and $E_k^{\prime 26} \neq E_k^{25}$ for each $k \in \tilde{K}$),

* and the last-slots assigned to the demands $K \setminus (\{k \in K \text{ with } v_{k,s} \in \tilde{H}_{25}\} \cup \{k'\})$ in $\mathcal{S}^{25}$ remain the same in $\mathcal{S}^{\prime 26}$, i.e., $S_k^{25} = S_{k'}^{\prime 26}$ for each demand $k'' \in K \setminus (\{k \in K \text{ with } v_{k,s} \in \tilde{H}_{25}\} \cup \{k'\})$,

* and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $S_{k'}^{\prime 26} = S_{k'}^{25} \cup \{s'\}$ with $v_{k',s'} \in C$,

* and modifying the last-slots assigned to each demand $k \in \{\tilde{k} \in K \text{ with } v_{\tilde{k},s} \in \tilde{H}_{25}\}$ by adding a new last-slot $\tilde{s}_k$ and removing the last slot $s_k \in S_k^{25}$ with $v_{k,s_k} \in H$ and $v_{k,\tilde{s}_k} \notin H \cup C$ s.t. $S_k^{\prime 26} = (S_k^{25} \setminus \{s_k\}) \cup \{\tilde{s}_k\}$ for each demand $k \in \{\tilde{k} \in K \text{ with } v_{\tilde{k},s} \in \tilde{H}_{25}\}$ s.t. $\{\tilde{s} - w_k + 1, \dots, \tilde{s}\} \cap \{s' - w_{k'} + 1, \dots, s'\} = \emptyset$ for each $k' \in K$ and $s' \in S_{k'}^{\prime 26}$ with $E_k^{\prime 26} \cap E_{k'}^{\prime 26} \neq \emptyset$.

The solution $\mathcal{S}^{\prime 26}$ is clearly feasible given that

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

* a set of last-slots $S_k^{\prime 26}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{\prime 26}$ with $|S_k^{\prime 26}| \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'^{26}$ and $s'' ∈ S_{k'}'^{26}$ with $E_k'^{26} ∩ E_{k'}'^{26} ≠ ∅$, i.e., for each edge $e ∈ E$ and each slot $s'' ∈ S$ we have $\sum_{k \in K, e \in E_k'^{26}} |\{s' \in S_k'^{26}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector ($x^{S'^{26}}, z^{S'^{26}}$) is belong to $F$ and then to $F_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. We have so

$$ \mu x^{S^{25}} + \sigma z^{S^{25}} = \mu x^{S'^{26}} + \sigma z^{S'^{26}} = \mu x^{S^{25}} + \sigma z^{S^{25}} + \sigma_{s'}^{k'} - \sum_{(k,s_k) \in \tilde{H}_{25}} \sigma_{s_k}^k + \sum_{k \in \tilde{K}} \sigma_{s_k}^k + \sum_{k \in \tilde{K}} \sum_{e \in E_k'^{26}} \mu_e^k - \sum_{k \in \tilde{K}} \sum_{e \in E_k'^{25}} \mu_e^k $$

It follows that $\sigma_{s'}^{k'} = \sum_{(k,s_k) \in \tilde{H}_{25}} \sigma_{s_k}^k$ for demand $k'$ and a slot $s' \in \{w_{k'}, ..., \bar{s}\}$ with $v_{k',s'} \in C$ given that $\sigma_{s_k}^k = 0$ for $v_{k,\bar{s}_k} \notin H \cup C$, and $\mu_e^k = 0$ for all $k \in K$ and all $e \in E \setminus (E_0^k \cup E_1^k)$. As a result, $\sigma_{s'}^{k'} = \rho^{\frac{|H|-1}{2}}$ given that $\sigma_s^k$ are equivalent for all $v_{k,s} \in H$.

Given that the pair $v_{k',s'}$ is chosen arbitrary in the clique $C$, we iterate the same procedure for all $v_{k',s'} \in C$. Consequently, we obtain that $\sigma_{s'}^{k'} = \rho^{\frac{|H|-1}{2}}$ for all $v_{k',s'} \in C$.

Furthermore, we ensure that all the edges $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, $$

On the other hand, 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\}. \quad (46) $$

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, \\ 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 } v_{k,s} \in H, \\ \rho \frac{|H| - 1}{2}, & \text{if } v_{k,s} \in C, \\ 0, & \text{otherwise.} \end{cases} $$

$$ \text{As a result } (\mu, \sigma) = \sum_{v_{k,s} \in H} \rho \beta_s^k + \frac{|H| - 1}{2} \sum_{v_{k',s'} \in C} \rho \beta_{s'}^{k'} + \gamma Q. $$

Let $N(v)$ denote the set of neighbors of node $v$ in a given graph.

**Theorem 7.** Consider an interval of contiguous slots $I = [s_i, s_j]$, and a pair of demands $k, k' \in K$ with $(v_k, v_{k'})$ in $G_I^E$. Then, the inequality (24) is facet defining for $P(G, K, \mathbb{S})$ if and only if $N(v_k) \cap N(v_{k'}) = \emptyset$ in the conflict graph $\tilde{G}_I^E$.

**Proof. Necessity.**

We distinguish two cases:

- if $N(v_k) \cap N(v_{k'}) \neq \emptyset$ in the conflict graph $\tilde{G}_I^E$, this means that there exists a clique $C$ in the conflict graph $\tilde{G}_I^E$ of cardinality equals to $|C| \ge 3$ with $k, k' \in C$. As a result, the inequality (24) is dominated by the inequality (25) induced by the clique $C$. Hence, the inequality (24) is not facet defining for $P(G, K, \mathbb{S})$.

- if there exists an interval of contiguous slots $I'$ in $[1, \bar{s}]$ s.t. $I \subset I'$ with

$w_k + w_{k'} \ge |I'|,$

$w_k \le |I'|$ and $2w_k \ge |I'| + 1,$

$w_{k'} \le |I'|$ and $2w_{k'} \ge |I'| + 1.$

This means that the inequality (24) induced by the two demands $k, k'$ for the interval $I$ is dominated by the inequality (24) induced by the same demands for the interval $I'$.

**Sufficiency.**

We use the same proof of the theorem 2 for a clique $C = \{v_k, v_{k'}\}$ in the conflict graph $\tilde{G}_I^E$.

## 5.5 Non-Compatibility-Clique Inequalities

**Theorem 8.** Consider a clique $C$ in the conflict graph $\tilde{G}_E^K$. Then, the inequality (35) is facet defining for $P(G, K, \mathbb{S})$ if and only if $C$ is a maximal clique in the conflict graph $\tilde{G}_E^K$.

**Proof.** It is trivial given that the inequality (35) can never be dominated by another inequality without changing its right-hand side.

Let $F_C^{\tilde{G}_E^K}$ denote the face induced by the inequality (35), which is given by

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

In order to prove that inequality $\sum_{v_{k,e} \in C} x_e^k \le 1$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_C^{\tilde{G}_E^K}$ is a proper face, and $F_C^{\tilde{G}_E^K} \neq P(G, K, \mathbb{S})$. We construct a solution $S^{28} = (E^{28}, S^{28})$ as below

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

- a set of last-slots $S_k^{28}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{28}$ with $|S_k^{28}| \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^{28}$ and $s' \in S_{k'}^{28}$ with $E_k^{28} \cap E_{k'}^{28} \neq \emptyset$ (non-overlapping constraint),

- and there is one pair of demand $k$ and edge $e$ from the clique $C$ (i.e., $v_{k,e} \in C$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S^{28}$, i.e., $e \in E_k^{28}$ for a node $v_{k,e} \in C$, and $e' \notin E_{k'}^{28}$ for all $v_{k',e'} \in C \setminus \{v_{k,e}\}$).
Obviously, $S^{28}$ 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^{28}}, z^{S^{28}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_C^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in C} x_e^k = 1$. As a result, $F_C^{\tilde{G}_E^K}$ is not empty (i.e., $F_C^{\tilde{G}_E^K} \neq \emptyset$). Furthermore, given that $s \in \{w_k, ..., \bar{s}\}$ for each $v_{k,s} \in C$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $C$ with $s \notin S_k$ for each $v_{k,s} \in C$. This means that $F_C^{\tilde{G}_E^K} \neq P(G, K, \mathbb{S})$.

Let denote the inequality $\sum_{v_{k,e} \in C} x_e^k \le 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})$. Suppose that $F_C^{\tilde{G}_E^K} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \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 \kappa} |E_0^k|}, \gamma_2 \in \mathbb{R}^{\sum_{k \in \kappa} |E_1^k|}, \gamma_3 \in \mathbb{R}^{\sum_{k \in \kappa} (w_k - 1)}$) s.t. $(\mu, \sigma) = (\rho(\alpha, \beta) + \gamma Q, \text{and that}$

- $\mu_e^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, ..., \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 $v_{k,e} \notin C$,

- and $\mu_e^k$ are equivalent for all $v_{k,e} \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 $v_{k,e} \notin C$. Consider a demand $k \in K$ and an edge $e \in E \setminus (E_0^k \cup E_1^k)$. For that, we consider a solution $S'^{28} = (E'^{28}, S'^{28})$ in which

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

- a set of last-slots $S_k'^{28}$ is assigned to each demand $k \in K$ along each edge $e \in E_k'^{28}$ with $|S_k'^{28}| \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'^{28}$ and $s'' \in S_{k'}'^{28}$ with $E_k'^{28} \cap E_{k'}'^{28} \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'^{28}} |\{s' \in S_k'^{28}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

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

- and there is one pair of demand $k$ and edge $e$ from the clique $C$ (i.e., $v_{k,e} \in C$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S'^{28}$, i.e., $e \in E_k'^{9}$ for a node $v_{k,e} \in C$, and $e' \notin E_k'^{9}$ for all $v_{k',e'} \in C \setminus \{v_{k,e}\}$.

$S'^{28}$ 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'^{28}}, z^{S'^{28}})$ is belong to $F$ and then to $F_C^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in C} x_e^k = 1$. Based on this, we derive a solution $S^{29}$ obtained from the solution $S'^{28}$ 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^{28}$ which means that $E_k'^{29} = E_k'^{28} \cup \{e\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^{28}$ remain the same in the solution $S^{29}$, i.e., $S_k'^{29} = S_k'^{28}$ for each $k \in K$, and $E_k'^{29} = E_k'^{28}$ for each $k' \in K \setminus \{k\}$. $S^{29}$ is clearly feasible given that

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

- a set of last-slots $S_k'^{29}$ is assigned to each demand $k \in K$ along each edge $e \in E_k'^{29}$ with $|S_k'^{29}| \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'^{29}$ and $s'' \in S_{k'}'^{29}$ with $E_k'^{29} \cap E_{k'}'^{29} \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'^{29}} |\{s' \in S_k'^{29}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{S'^{28}} + \sigma z^{S'^{28}} = \mu x^{S^{29}} + \sigma z^{S^{29}} = \mu x^{S'^{28}} + \mu_e^k + \sigma z^{S'^{28}}. $$

As a result, $\mu_e^k = 0$ for demand $k$ and an edge $e$ with $v_{k,e} \notin C$.

As $e$ is chosen arbitrarily for the demand $k$ with $e \notin E_0^k \cup E_1^k$ and $v_{k,e} \notin C$, we iterate the same procedure for all $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$ with $v_{k,e'} \notin 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 } v_{k,e} \notin 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)$ with $v_{k',e} \notin C$. 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 } v_{k,e} \notin 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}\}$, and a solution $S^{28} = (E^{28}, S^{28})$ in which

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

- a set of last-slots $S_k^{28}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{28}$ with $|S_k^{28}| \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^{28}$ and $s'' \in S_{k'}^{28}$ with $E_k^{28} \cap E_{k'}^{28} \ne \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^{28}} |\{s' \in S_k^{28}, 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'}^{28}$ with $E_k^{28} \cap E_{k'}^{28} \ne \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{28}$ assigned to the demand $k$ in the solution $S^{28}$),

- and there is one pair of demand $k$ and edge $e$ from the clique $C$ (i.e., $v_{k,e} \in C$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S^{28}$, i.e., $e \in E_k^{28}$ for a node $v_{k,e} \in C$, and $e' \notin E_{k'}^{28}$ for all $v_{k',e'} \in C \setminus \{v_{k,e}\}$.

$S^{28}$ 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^{28}}, z^{S^{28}})$ is belong to $F$ and then to $F_C^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in C} x_e^k = 1$. Based on this, we distinguish the following cases:

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

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

• a set of last-slots $S_k^{30}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{30}$ with $|S_k^{30}| \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^{30}$ and $s'' \in S_{k'}^{30}$ with $E_k^{30} \cap E_{k'}^{30} \ne \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^{30}} |\{s' \in S_k^{30}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

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

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$.

- with changing the paths established in $S^{28}$: we construct a solution $S'^{30}$ derived from the solution $S^{28}$ 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^{28}$ (i.e., $E_k'^{30} = E_k^{28}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{30} \ne E_k^{28}$ for each $k \in \tilde{K}$) s.t.

• a new feasible path $E_k'^{30}$ 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^{28}$ and $s'' \in S_{k'}^{28}$ with $E_k'^{30} \cap E_{k'}^{28} \ne \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'^{30}} |\{s' \in S_k^{28}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e \in E_k'^{28}} |\{s' \in S_k^{28}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

• and there is one pair of demand $k$ and edge $e$ from the clique $C$ (i.e., $v_{k,e} \in C$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S'^{30}$, i.e., $e \in E_k'^{30}$ for a node $v_{k,e} \in C$, and $e' \notin E_{k'}'^{30}$ for all $v_{k',e'} \in C \setminus \{v_{k,e}\}$,
* and {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k' ∈ \tilde{K}$ and $s'' ∈ S''_{\tilde{k}''}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S''_{\tilde{k}''}$ assigned to the demand $k$ in the solution $S''^{28}$).

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

* a feasible path $E'^{30}_{\tilde{k}''}$ is assigned to each demand $k' ∈ K$ (routing constraint),

* a set of last-slots $S'^{30}_{\tilde{k}''}$ is assigned to each demand $k' ∈ K$ along each edge $e ∈ E'^{30}_{\tilde{k}''}$ with $|S'^{30}_{\tilde{k}''}| ≥ 1$ (contiguity and continuity constraints),

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

The corresponding incidence vector $(x^{S'^{30}}, z^{S'^{30}})$ is belong to $F$ and then to $F^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in C} x_e^k = 1$. We have so

$$ \mu x^{S''^{28}} + \sigma z^{S''^{28}} = \mu x^{S'^{30}} + \sigma z^{S'^{30}} = \mu x^{S''^{28}} + \sigma z^{S''^{28}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e \in E''^{28}_{\tilde{k}}} \mu_e^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E'^{30}_{\tilde{k}}} \mu_{e'}^{\tilde{k}} $$

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ given that $\mu_e^k = 0$ for all the demand $k' ∈ K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$ with $v_{k,e} \notin 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$ with $v_{k,s'} \notin C$ s.t. we find

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

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}\} \text{ with } v_{k',s} \notin C. $$

Consequently, we conclude that

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

Let's prove that $\mu_e^k$ for all $v_{k,e}$ are equivalents. Consider a node $v_{k',e'}$ in $C$ s.t. $e' \notin E'^{28}_{\tilde{k}''}$. For that, we consider a solution $\tilde{S}^{28} = (\tilde{E}^{28}, \tilde{S}^{28})$ in which

* a feasible path $\tilde{E}^{28}_{\tilde{k}''}$ is assigned to each demand $k' ∈ K$ (routing constraint),

* a set of last-slots $\tilde{S}^{28}_{\tilde{k}''}$ is assigned to each demand $k' ∈ K$ along each edge $e \in \tilde{E}^{28}_{\tilde{k}''}$ with $|\tilde{S}^{28}_{\tilde{k}''}| ≥ 1$ (contiguity and continuity constraints),

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

* and there is one pair of demand $k$ and edge $e$ from the clique $C$ (i.e., $v_{k,e} \in C$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $\tilde{S}^{28}$, i.e., $e \in \tilde{E}^{28}_{\tilde{k}''}$ for a node $v_{k,e} \in C$, and $e'' \notin \tilde{E}^{28}_{\tilde{k}''}$ for all $v_{k',e''} \in C \setminus \{v_{k,e}\}$.

$\tilde{S}^{28}$ 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}^{28}}, z^{\tilde{S}^{28}})$ is belong to $F$ and then to $F^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in C} x_e^k = 1$. Based on this, we distinguish two cases:

* without changing the spectrum assignment established in $\tilde{S}^{28}$: we derive a solution $S^{31} = (E^{31}, S^{31})$ from the solution $\tilde{S}^{28}$ by

* modifying the path assigned to the demand $k'$ in $\tilde{S}^{28}$ from $\tilde{E}^{28}_{\tilde{k}''}$ to a path $E'^{31}_{\tilde{k}''}$ passed through the edge $e'$ with $v_{k',e'} \in C$,
* modifying the path assigned to the demand k in $\tilde{S}^{28}$ with $e \in \tilde{E}_k^{28}$ and $v_{k,e} \in C$ from $\tilde{E}_k^{28}$ to a path $E_k^{31}$ without passing through any edge $e'' \in E \setminus (E_0^k \cup E_1^k)$ s.t. $v_{k',e'}$ and $v_{k,e''}$ linked in C and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k' \in K$ and each $s' \in \tilde{S}_{k'}^{28}$ with $\tilde{E}_{k'}^{28} \cap E_k^{31} \neq \emptyset$.

The paths assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{28}$ remain the same in $S^{31}$ (i.e., $E_k^{31} = \tilde{E}_k^{28}$ for each $k'' \in K \setminus \{k, k'\}$), and also without modifying the last-slots assigned to the demands $K$ in $\tilde{S}^{28}$, i.e., $\tilde{S}_k^{28} = S_k^{31}$ for each demand $k \in K$. The solution $S^{31}$ is feasible given that

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

* a set of last-slots $S_k^{31}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{31}$ with $|S_k^{31}| \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^{31}$ and $s'' \in S_{k'}^{31}$ with $E_k^{31} \cap E_{k'}^{31} \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^{31}} |\{s' \in S_k^{31}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{\tilde{S}^{28}} + \sigma z^{\tilde{S}^{28}} = \mu x^{S^{31}} + \sigma z^{S^{31}} = \mu x^{\tilde{S}^{28}} + \sigma z^{\tilde{S}^{28}} + \mu_{e'}^{k'} - \mu_e^k + \sum_{e'' \in E_{k'}^{31} \setminus \{e'\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_{k'}^{28}} \mu_{e''}^{k'} + \sum_{e'' \in E_k^{31}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_k^{28} \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 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 $v_{k,e''} \notin C$.

* with changing the spectrum assignment established in $\tilde{S}^{28}$: we construct a solution $S'^{31}$ derived from the solution $\tilde{S}^{28}$ by

* modifying the path assigned to the demand $k'$ in $\tilde{S}^{28}$ from $\tilde{E}_k^{28}$ to a path $E_{k'}^{31}$ passed through the edge $e'$ with $v_{k',e'} \in C$,

* modifying the path assigned to the demand $k$ in $\tilde{S}^{28}$ with $e \in \tilde{E}_k^{28}$ and $v_{k,e} \in C$ from $\tilde{E}_k^{28}$ to a path $E_k^{31}$ without passing through any edge $e'' \in E \setminus (E_0^k \cup E_1^k)$ s.t. $v_{k',e'}$ and $v_{k,e''}$ linked in C,

* modifying the last-slots assigned to some demands $\tilde{K} \subset K$ from $\tilde{S}_k^{28}$ to $S_k^{31}$ for each $\tilde{k} \in \tilde{K}$ while satisfying non-overlapping constraint.

The paths assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{28}$ remain the same in $S'^{31}$ (i.e., $E_k'^{31} = \tilde{E}_k^{28}$ for each $k'' \in K \setminus \{k, k'\}$), and also without modifying the last-slots assigned to the demands $K \setminus \tilde{K}$ in $\tilde{S}^{28}$, i.e., $\tilde{S}_k^{28} = S_k'^{31}$ for each demand $k \in K \setminus \tilde{K}$. The solution $S'^{31}$ is clearly feasible given that

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

* a set of last-slots $S_k'^{31}$ is assigned to each demand $k \in K$ along each edge $e \in E_k'^{31}$ with $|S_k'^{31}| \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'^{31}$ and $s'' \in S_{k'}'^{31}$ with $E_k'^{31} \cap E_{k'}'^{31} \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'^{31}} |\{s' \in S_k'^{31}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{\tilde{S}^{28}} + \sigma z^{\tilde{S}^{28}} = \mu x^{S'^{31}} + \sigma z^{S'^{31}} = \mu x^{\tilde{S}^{28}} + \sigma z^{\tilde{S}^{28}} + \mu_{e'}^{k'} - \mu_e^k + \sum_{\tilde{k} \in \tilde{K}} \sum_{s' \in S_{\tilde{k}}'^{31}} \sigma_{s'}^{\tilde{k}} - \sum_{s \in \tilde{S}_k^{28}} \sigma_s^{\tilde{k}} + \sum_{e'' \in E_{k'}'^{31} \setminus \{e'\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_{k'}^{28}} \mu_{e''}^{k'} + \sum_{e'' \in E_k'^{31}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_k^{28} \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 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 $v_{k,e''} \notin C$, and $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$.
Given that the pair $(v_{k,e}, v_{k',e'})$ are chosen arbitrary in the clique $C$, we iterate the same procedure for all pairs $(v_{k,e}, v_{k',e'})$ s.t. we find

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

Consequently, we obtain that $\mu_e^k = \rho$ for all $v_{k,e} \in C$.

On the other hand, we ensure that all the edges $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, $$

On the other hand, 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\}. \quad (47) $$

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 } v_{k,e} \in C, \\ 0, & \text{otherwise,} \end{cases} $$

and for each $k \in K$ and $s \in S$

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

As a result $(\mu, \sigma) = \sum_{v_{k,e} \in C} \rho \alpha_e^k + \gamma Q$.
## 5.6 Edge-Interval-Clique Inequalities

**Theorem 9.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots. Let $C$ be a clique in the conflict graph $\tilde{G}_I^e$ with $|C| \ge 3$, and $\sum_{k \in C} w_k \le \bar{s} - \sum_{k' \in K_e \setminus C} w_{k'}$. Then, the inequality (22) is facet defining for $P(G, K, \mathbb{S})$ iff

- there does not exist a demand $k' \in K_e \setminus C$ with $w_k + w_{k'} > |I|$ and $w_{k'} \le |I|$ and $2w_{k'} > |I|$,

- and $|\{s_i + w_k - 1, ..., s_j\}| \ge w_k$ for each demand $k$ with $v_k \in C$,

- and there does not exist an interval $I'$ of contiguous slots with $I \subset I'$ s.t. $C$ defines also a clique in the associated conflict graph $\tilde{G}_I^e$.

**Proof.** **Necessity.**

It is trivial given that

- if

- there does not exist a demand $k' \in K_e \setminus C$ with $w_k + w_{k'} > |I|$ and $w_{k'} \le |I|$ and $2w_{k'} > |I|$,

- and $|\{s_i + w_k - 1, ..., s_j\}| \ge w_k$ for each demand $k$ with $v_k \in C$.

Then, the inequality (22) can never be dominated by another inequality without changing its right hand side. Otherwise, if there exists a demand $k' \in K_e \setminus C$ with $w_k + w_{k'} > |I|$ and $w_{k'} \le |I|$ and $2w_{k'} > |I|$, this implies that the inequality is dominated by (23). Moreover, if $|\{s_i + w_k - 1, ..., s_j\}| < w_k$ for each demand $k$ with $v_k \in C$, then the inequality (22) is then dominated by the inequality (15) for a set of demands $\tilde{K} = \{k \in K \text{ s.t. } v_k \in C\}$ and slot $s = s_i + \min_{k \in C} w_k + 1$ over edge $e$. Hence, the inequality (22) is not facet defining for $P(G, K, \mathbb{S})$.

- if there exists an interval $I'$ of contiguous slots with $I \subset I'$ s.t. $C$ defines also a clique in the associated conflict graph $\tilde{G}_I^e$. This implies that the inequality (22) induced by the clique $C$ for the interval $I$ is dominated by the inequality (22) induced by the same clique $C$ for the interval $I'$ given that $\{s_i + w_k - 1, ..., s_j\} \subset I'$ for each $k \in C$. As a result, the inequality (22) is not facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let $F_C^{\tilde{G}_I^e}$ denote the face induced by the inequality (22), which is given by

$$F_C^{\tilde{G}_I^e} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = |C| + 1\}.$$

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

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

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

- a set of last-slots $S_k^{32}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{32}$ with $|S_k^{32}| \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^{32}$ and $s' \in S_{k'}^{32}$ with $E_k^{32} \cap E_{k'}^{32} \ne \emptyset$ (non-overlapping constraint),

- and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{32}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{32}$ for a node $v_k \in C$, and for each $s' \in S_{k'}^{32}$ for all $v_{k'} \in C \setminus \{v_k\}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and all the demands in $C$ pass through the edge $e$ in the solution $S^{32}$, i.e., $e \in E_k^{32}$ for each $k \in C$.

Obviously, $S^{32}$ 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^{32}}, z^{S^{32}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_C^{\tilde{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 1$. As a result, $F_C^{\tilde{G}_I^e}$ is not empty (i.e., $F_C^{\tilde{G}_I^e} \ne \emptyset$). Furthermore, given that $s \in \{s_i + w_k - 1, ..., s_j\}$ for each $v_k \in C$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $C$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ for each $s \in S_k$ and each $v_k \in C$. This means that $F_C^{\tilde{G}_I^e} \ne P(G, K, \mathbb{S})$.
We denote the inequality $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^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})$. Suppose that $F_C^{\bar{G}_I^e} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \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_0^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, ..., \bar{s}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in C$,

- and $\sigma_{e'}^k$ are equivalents for all $v_k \in C$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$,

- 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 \neq e'$ if $v_k \in C$,

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

- and $\sigma_s^k$ and $\mu_e^k$ are equivalents for all $v_k \in C$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$.

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 \neq e'$ if $k \in C$. Consider a demand $k \in K$ and an edge $e' \in E \setminus (E_0^k \cup E_1^k)$ with $e \neq e'$ if $k \in C$. For that, we consider a solution $S'^{32} = (E'^{32}, S'^{32})$ in which

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

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

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k'^{32}$ and $s'' \in S_{k'}'^{32}$ with $E_k'^{32} \cap E_{k'}'^{32} \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'^{32}} |\{s' \in S_k'^{32}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

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

- and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S'^{32}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k'^{32}$ for a node $v_k \in C$, and for each $s' \in S_{k'}'^{32}$ for all $v_{k'} \in C \setminus \{v_k\}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and all the demands in $C$ pass through the edge $e$ in the solution $S'^{32}$, i.e., $e \in E_k'^{32}$ for each $k \in C$.

$S'^{32}$ 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'^{32}}, z^{S'^{32}})$ is belong to $F$ and then to $F_C^{\bar{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_{e'}^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = |C| + 1$. Based on this, we derive a solution $S^{33}$ obtained from the solution $S'^{32}$ 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^{32}$ which means that $E_k^{33} = E_k'^{32} \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^{32}$ remain the same in the solution $S^{33}$, i.e., $S_k^{33} = S_k'^{32}$ for each $k \in K$, and $E_k^{33} = E_k'^{32}$ for each $k' \in K \setminus \{k\}$. $S^{33}$ is clearly feasible given that

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

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

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{33}$ and $s'' \in S_{k'}^{33}$ with $E_k^{33} \cap E_{k'}^{33} \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^{33}} |\{s' \in S_k^{33}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{33}}, z^{S^{33}})$ is belong to $F$ and then to $F_C^{\bar{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_{e'}^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = |C| + 1$. It follows that

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

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 \neq 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 \neq 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 \neq 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 \neq 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}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \notin C$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \notin C$. For that, we consider a solution $S^{32} = (E^{32}, S^{32})$ in which

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

- a set of last-slots $S_k^{32}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{32}$ with $|S_k^{32}| \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^{32}$ and $s'' \in S_{k'}^{32}$ with $E_k^{32} \cap E_{k'}^{32} \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^{32}} |\{s' \in S_k^{32}, 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'}^{32}$ with $E_k^{32} \cap E_{k'}^{32} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{32}$ assigned to the demand $k$ in the solution $S^{32}$),

- and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{32}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{32}$ for a node $v_k \in C$, and for each $s' \in S_k^{32}$ for all $v_{k'} \in C \setminus \{v_k\}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and all the demands in $C$ pass through the edge $e$ in the solution $S^{32}$, i.e., $e' \in E_k^{32}$ for each $k \in C$.

$S^{32}$ 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^{32}}, z^{S^{32}})$ is belong to $F$ and then to $F_C^{\tilde{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_{e'}^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 1$. Based on this,

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

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

* a set of last-slots $S_k^{34}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{34}$ with $|S_k^{34}| \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^{34}$ and $s'' \in S_{k'}^{34}$ with $E_k^{34} \cap E_{k'}^{34} \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^{34}} |\{s' \in S_k^{34}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{S^{32}} + \sigma z^{S^{32}} = \mu x^{S^{34}} + \sigma z^{S^{34}} = \mu x^{S^{32}} + \sigma z^{S^{32}} + \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 $v_k \notin C$.

- with changing the paths established in $S^{32}$: we construct a solution $S'^{34}$ derived from the solution $S^{32}$ 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^{32}$ (i.e., $E_k'^{34} = E_k^{32}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{34} \neq E_k^{32}$ for each $k \in \tilde{K}$) s.t.

* a new feasible path $E_k'^{34}$ 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^{32}$ and $s'' \in S_{k'}^{32}$ with $E_k'^{34} \cap E_{k'}^{32} \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'^{34}} |\{s' \in S_k^{32}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e' \in E_k'^{32}} |\{s' \in S_k^{32}, 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' ∈ \tilde{K}$ and $s'' ∈ S''_{\tilde{k}''}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S''_{\tilde{k}''}$ assigned to the demand $k$ in the solution $S''^{32}$).

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

• a feasible path $E'^{34}_{\tilde{k}''}$ is assigned to each demand $k \in K$ (routing constraint),

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

• {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k, k' \in K$ and each $s' \in S'^{34}_{\tilde{k}''}$ and $s'' \in S'^{34}_{\tilde{k}''}$ with $E'^{34}_{\tilde{k}''} \cap E'^{34}_{\tilde{k}''} \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'^{34}_{\tilde{k}''}} |\{s' \in S'^{34}_{\tilde{k}''}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector ($x^{S'^{34}}$, $z^{S'^{34}}$) is belong to $F$ and then to $F^{\tilde{G}_I^e}_C$ given that it is composed by $\sum_{v_k \in C} x^k_{e'} + \sum_{s=s_i+w_k-1}^{s_j} z^k_s = |C| + 1$. We have so

$$ \mu x^{S'^{32}} + \sigma z^{S'^{32}} = \mu x^{S'^{34}} + \sigma z^{S'^{34}} = \mu x^{S''^{32}} + \sigma z^{S''^{32}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E'^{32}_{\tilde{k}}} \mu_{e'}^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e'' \in E'^{34}_{\tilde{k}}} \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 $v_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$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \notin C$ s.t. we find

$$ \sigma_{s'}^k = 0, \text{ for demand } k \text{ and all slots } s' \in \{w_k, ..., \bar{s}\} \text{ with } s' \notin \{s_i + w_k - 1, ..., s_j\} \text{ if } v_k \notin C. $$

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}\} \text{ with } s \notin \{s_i + w_{k'} - 1, ..., s_j\} \text{ if } v_{k'} \notin C. $$

Consequently, we conclude that

$$ \sigma_s^k = 0, \text{ for all } k \in K \text{ and all slots } s \in \{w_k, ..., \bar{s}\} \text{ with } s \notin \{s_i + w_k - 1, ..., s_j\} \text{ if } v_k \notin C. $$

Let prove that $\sigma_s^k$ for all $v_k \in C$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$ are equivalents. Consider a demand $k'$ and a slot $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$ with $v_{k'} \in C$. For that, we consider a solution $\tilde{S}^{32} = (\tilde{E}^{32}, \tilde{S}^{32})$ in which

– a feasible path $\tilde{E}^{32}_{\tilde{k}''}$ is assigned to each demand $k \in K$ (routing constraint),

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

– {$s' - w_k + 1, ..., s'$} ∩ {$s'' - w_{k'} + 1, ..., s''$} = ∅ for each $k, k' \in K$ and each $s' \in \tilde{S}^{32}_{\tilde{k}''}$ and $s'' \in \tilde{S}^{32}_{\tilde{k}''}$ with $\tilde{E}^{32}_{\tilde{k}''} \cap \tilde{E}^{32}_{\tilde{k}''} \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}^{32}_{\tilde{k}''}} |\{s' \in \tilde{S}^{32}_{\tilde{k}''}, 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 \tilde{S}^{32}_{\tilde{k}''}$ with $\tilde{E}^{32}_{\tilde{k}''} \cap \tilde{E}^{32}_{\tilde{k}''} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $\tilde{S}^{32}_{\tilde{k}''}$ assigned to the demand $k'$ in the solution $\tilde{S}^{32}$),

– and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $\tilde{S}^{32}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in \tilde{S}^{32}_{\tilde{k}''}$ for a node $v_k \in C$, and for each $s' \in \tilde{S}^{32}_{\tilde{k}''}$ for all $v_{k'} \in C \setminus \{v_k\}$ we have $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$,

– and all the demands in $C$ pass through the edge $e$ in the solution $\tilde{S}^{32}$, i.e., $e' \in \tilde{E}^{32}_{\tilde{k}''}$ for each $k \in C$.

$\tilde{S}^{32}$ 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}^{32}}$, $z^{\tilde{S}^{32}}$) is belong to $F$ and then to $F^{\tilde{G}_I^e}_C$ given that it is composed by $\sum_{v_k \in C} x^k_{e'} + \sum_{s=s_i+w_k-1}^{s_j} z^k_s = |C| + 1$. Based on this,
- without changing the paths established in $\tilde{S}^{32}$: we derive a solution $S^{35} = (E^{35}, S^{35})$ from the solution $\tilde{S}^{32}$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $\tilde{S}^{32}$ (i.e., $E_k^{35} = \tilde{E}_k^{32}$ for each $k \in K$), and also the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{32}$ remain the same in $S^{35}$, i.e., $\tilde{S}_{k'}^{32} = S_{k''}^{35}$ for each demand $k'' \in K \setminus \{k, k'\}$, and $S_{k'}^{35} = \tilde{S}_{k'}^{32} \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^{32}$ 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 $v_k \in C$ s.t. $S_k^{35} = (\tilde{S}_k^{32} \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'}^{35}$ with $E_k^{35} \cap E_{k'}^{35} \neq \emptyset$. The solution $S^{35}$ is feasible given that

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

* a set of last-slots $S_k^{35}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{35}$ with $|S_k^{35}| \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^{35}$ and $s'' \in S_{k'}^{35}$ with $E_k^{35} \cap E_{k'}^{35} \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^{35}} |\{s' \in S_k^{35}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{\tilde{S}^{32}} + \sigma z^{\tilde{S}^{32}} = \mu x^{S^{35}} + \sigma z^{S^{35}} = \mu x^{\tilde{S}^{32}} + \sigma z^{\tilde{S}^{32}} + \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 $v_{k'} \in C$ 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 $v_k \in C$.

- with changing the paths established in $\tilde{S}^{32}$: we construct a solution $S'^{35}$ derived from the solution $\tilde{S}^{32}$ 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 $\tilde{S}^{32}$ (i.e., $E_k'^{35} = \tilde{E}_k^{32}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{35} \neq \tilde{E}_k^{32}$ for each $k \in \tilde{K}$), and also the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{32}$ remain the same in $S'^{35}$, i.e., $\tilde{S}_{k''}^{32} = S_{k''}'^{35}$ for each demand $k'' \in K \setminus \{k, k'\}$, and $S_{k'}'^{35} = \tilde{S}_{k'}^{32} \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^{32}$ 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 $v_k \in C$ s.t. $S_k'^{35} = (\tilde{S}_k^{32} \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'}'^{35}$ with $E_k'^{35} \cap E_{k'}'^{35} \neq \emptyset$. The solution $S'^{35}$ is clearly feasible given that

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

* a set of last-slots $S_k'^{35}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{35}$ with $|S_k'^{35}| \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'^{35}$ and $s'' \in S_{k'}'^{35}$ with $E_k'^{35} \cap E_{k'}'^{35} \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'^{35}} |\{s' \in S_k'^{35}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{\tilde{S}^{32}} + \sigma z^{\tilde{S}^{32}} = \mu x^{S'^{35}} + \sigma z^{S'^{35}} = \mu x^{\tilde{S}^{32}} + \sigma z^{\tilde{S}^{32}} + \sigma_{s'}^{k'} - \sigma_s^k + \sigma_{\tilde{s}}^k \\ - \sum_{k \in \tilde{K}} \sum_{e' \in \tilde{E}_k^{32}} \mu_{e'}^k + \sum_{k \in \tilde{K}} \sum_{e' \in E_k'^{35}} \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 $v_{k'} \in C$ 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 $v_k \in C$, 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 C$.

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

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all pairs } (v_k, v_{k'}) \in C $$
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 $v_k \in C$ s.t.

$$ \sigma_s^k = \sigma_{s'}^k, \text{ for all } v_k \in C \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 $v_k \in C$ are equivalents. For that, we consider a solution $S^{36} = (E^{36}, S^{36})$ defined as below

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

- a set of last-slots $S_k^{36}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{36}$ with $|S_k^{36}| \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^{36}$ and $s' \in S_{k'}^{36}$ with $E_k^{36} \cap E_{k'}^{36} \neq \emptyset$ (non-overlapping constraint),

- and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ pass through the edge $e$ in the solution $S^{36}$, i.e., $e \in E_k^{36}$ for a node $v_k \in C$, and $e \notin E_{k'}^{36}$ for all $v_{k'} \in C \setminus \{v_k\}$),

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

Obviously, $S^{36}$ 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^{36}}, z^{S^{36}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_C^{\tilde{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = |C| + 1$. Consider now a node $v_{k'}$ in $C$ s.t. $e \notin E_{k'}^{36}$. For that, we consider a solution $\tilde{S}^{36} = (\tilde{E}^{36}, \tilde{S}^{36})$ in which

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

- a set of last-slots $\tilde{S}_k^{36}$ is assigned to each demand $k \in K$ along each edge $e \in \tilde{E}_k^{36}$ with $|\tilde{S}_k^{36}| \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^{36}$ and $s'' \in \tilde{S}_{k'}^{36}$ with $\tilde{E}_k^{36} \cap \tilde{E}_{k'}^{36} \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^{36}} |\{s' \in \tilde{S}_k^{36}, 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^{36}$ with $\tilde{E}_k^{36} \cap \tilde{E}_{k'}^{36} \neq \emptyset$,

- and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ pass through the edge $e$ in the solution $\tilde{S}^{36}$, i.e., $e \in \tilde{E}_k^{36}$ for a node $v_k \in C$, and $e \notin \tilde{E}_{k'}^{36}$ for all $v_{k'} \in C \setminus \{v_k\}$),

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

$\tilde{S}^{36}$ 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}^{36}}, z^{\tilde{S}^{36}})$ is belong to $F$ and then to $F_C^{\tilde{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = |C| + 1$. Based on this, we derive a solution $S^{37} = (E^{37}, S^{37})$ from the solution $\tilde{S}^{36}$ by

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

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

- modifying the path assigned to the demand $k'$ in $\tilde{S}^{36}$ from $\tilde{E}_{k'}^{36}$ to a path $E_k^{37}$ passed through the edge $e$ (i.e., $e \in E_k^{37}$) with $v_{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 \tilde{S}_k^{36}$ and each $s \in \tilde{S}_k^{36}$ with $\tilde{E}_k^{36} \cap E_k^{37} \neq \emptyset$,

- modifying the path assigned to the demand $k$ in $\tilde{S}^{36}$ with $e \in \tilde{E}_k^{36}$ and $v_k \in C$ from $\tilde{E}_k^{36}$ to a path $E_k^{37}$ without passing through the edge $e$ (i.e., $e \notin E_k^{37}$) 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 \tilde{S}_k^{36}$ and each $s' \in \tilde{S}_{k'}^{36}$ with $\tilde{E}_{k''}^{36} \cap E_k^{37} \neq \emptyset$, and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $s \in \tilde{S}_k^{36}$ and each $s' \in \tilde{S}_{k'}^{36}$ with $E_k^{37} \cap E_k^{37} \neq \emptyset$.

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

- a feasible path $E_k^{37}$ is assigned to each demand $k \in K$ (routing constraint),
- a set of last-slots $S_k^{37}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{37}$ with $|S_k^{37}| \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^{37}$ and $s'' \in S_{k'}^{37}$ with $E_k^{37} \cap E_{k'}^{37} \ne \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^{37}} |\{s' \in S_k^{37}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

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

It follows that $\mu_e^{k'} = \mu_e^k$ for demand $k'$ and an 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 $v_k \notin C$.

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

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

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

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

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

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

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

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

- a set of last-slots $S_k^{38}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{38}$ with $|S_k^{38}| \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^{38}$ and $s'' \in S_{k'}^{38}$ with $E_k^{38} \cap E_{k'}^{38} \ne \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^{38}} |\{s' \in S_k^{38}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

- and $\sum_{v_k \in C} |E_k^{38} \cap \{e\}| + |S_k^{38} \cap \{s_i + w_k - 1, ..., s_j\}| = |C| + 1$.

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

$$ \mu x^{\tilde{S}^{36}} + \sigma z^{\tilde{S}^{36}} = \mu x^{S^{38}} + \sigma z^{S^{38}} = \mu x^{\tilde{S}^{36}} + \sigma z^{\tilde{S}^{36}} + \mu_e^{k'} - \sigma_s^{k'} + \sum_{e'' \in E_{k'}^{38} \setminus \{e\}} \mu_{e''}^{k'} - \sum_{e'' \in E_{k'}^{38}} \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 \ne e''$ if $v_k \in C$. 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 $C$, we iterate the same procedure for all $k \in C$ to show that

$$ \mu_e^k = \sigma_s^k, \text{ for all } v_k \in C \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 $v_k \in C$, and that $\sigma_s^k$ are equivalents for all $v_k \in C$ 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 C \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 C \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 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\}. \quad (48) $$

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\} \\ \rho, & \text{if } v_k \in C \text{ and } s \in \{s_i + w_k - 1, ..., s_j\}, \\ 0, & \text{otherwise.} \end{cases} $$

As a result $(\mu, \sigma) = \sum_{v_k \in C} \rho \alpha_e^k + \sum_{s=s_i+w_k-1}^{s_j} \rho \beta_s^k + \gamma Q$.
**Theorem 10.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots. Let $C$ be a clique in the conflict graph $\tilde{G}_I^e$ with $|C| \ge 3$, and $\sum_{v_k \in C} w_k \le \bar{s} - \sum_{k' \in K_e \setminus C} w_{k'}$. Let $C_e \subseteq K_e \setminus C$ be a clique in the conflict graph $\tilde{G}_I^e$ s.t. $w_k + w_{k'} \ge |I| + 1$ for each $v_k \in C$ and $v_{k'} \in C_e$. Then, the inequality (23) is facet defining for $P(G, K, \mathbb{S})$ if and only if

- there does not exist a demand $k'' \in K_e \setminus C_e$ with $w_k + w_{k''} \ge |I| + 1$ for each $v_k \in C$, and $w_{k'} + w_{k''} \ge |I| + 1$ for each $v_{k'} \in C_e$.

- and $|\{s_i + w_k - 1, ..., s_j\}| \ge w_k$ for each demand $k$ with $v_k \in C \cup C_e$.

**Proof. Necessity.**

- If there exists a demand $k'' \in K_e \setminus C_e$ with $w_k + w_{k''} \ge |I| + 1$ for each $v_k \in C$, and $w_{k'} + w_{k''} \ge |I| + 1$ for each $v_{k'} \in C_e$. Then, the inequality (23) is dominated by its lifted with $C'_e = C_e \cup \{k''\}$. Moreover, if $|\{s_i + w_k - 1, ..., s_j\}| < w_k$ for each demand $k$ with $v_k \in C \cup C_e$, then the inequality (23) is then dominated by the inequality (17) for a set of demands $\tilde{K} = \{k \in K \text{ s.t. } v_k \in C\}$ and slot $s = s_i + \min_{k \in C \cup C_e} w_k + 1$ over edge $e$. As a result, the inequality (23) is not facet defining for $P(G, K, \mathbb{S})$.

- if there exists an interval $I'$ of contiguous slots with $I \subset I'$ s.t. $C \cup C_e$ defines also a clique in the associated conflict graph $\tilde{G}_I^e$. This implies that the inequality (23) induced by the clique $C \cup C_e$ for the interval $I$ is dominated by the inequality (23) induced by the same clique $C \cup C_e$ for the interval $I'$ given that $\{s_i + w_k - 1, ..., s_j\} \subset I'$ for each $k \in C \cup C_e$. As a result, the inequality (23) is not facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let $F_C^{\tilde{G}_I^e}$ denote the face induced by the inequality (23), which is given by

$$F_C^{\tilde{G}_I^e} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} = |C| + 1\}.$$

We denote the inequality $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{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})$.

Suppose that $F_C^{\tilde{G}_I^e} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \mu x + \sigma z = \tau\}$. We use the same proof of the facial structure done for the inequality (22) in the proof of theorem ?? to prove that inequality $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} \le |C| + 1$ is facet defining for $P(G, K, \mathbb{S})$.

We first prove that $F_C^{\tilde{G}_I^e}$ is a proper face based on the solution $S^{32}$ defined in the proof of theorem ?? which stills feasible s.t. its corresponding incidence vector $(x^{S^{32}}, z^{S^{32}})$ is belong to $F$ and then to $F_C^{\tilde{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} = |C| + 1$. Furthermore, and based on the solutions $S^{32}$ to $S^{38}$ with corresponding incidence vector $(x^{S^{32}}, z^{S^{32}})$ to $(x^{S^{38}}, z^{S^{38}})$ are belong to $F$ and then to $F_C^{\tilde{G}_I^e}$ given that it is composed by $\sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} = |C| + 1$, we showed 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_0^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, ..., \bar{s}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in C \cup C_e$,

- and $\sigma_s^k$ are equivalents for all $v_k \in C \cup C_e$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$,

- 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 \neq e'$ if $v_k \in C$,

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

- and $\sigma_s^{k'}$ and $\mu_e^k$ are equivalents for all $v_k \in C$ and all $v_{k'} \in C \cup C_e$ and all $s \in \{s_i + w_{k'} - 1, ..., s_j\}$.

At the end, we found 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, \dots, w_k - 1\} \\ \rho, & \text{if } v_k \in C \cup C_e \text{ and } s \in \{s_i + w_k - 1, \dots, s_j\}, \\ 0, & \text{otherwise.} \end{cases} $$

$$ \text{As a result } (\mu, \sigma) = \sum_{v_k \in C} \rho \alpha_e^k + \sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} \rho \beta_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} \rho \beta_{s'}^{k'} + \gamma Q. $$

## 5.7 Edge-Slot-Assignment Inequalities

**Theorem 11.** Consider an edge $e \in E$, and a slot $s \in \mathbb{S}$. Let $\tilde{K}$ be a subset of demands in $K$ with $|C| \ge 3$, and $\sum_{k \in \tilde{K}} w_k \le \bar{s} - \sum_{k' \in K_e \setminus \tilde{K}} w_{k'}$. Then, the inequality (15) is facet defining for $P(G, K, \mathbb{S})$ iff $K_e \setminus \tilde{K} = \emptyset$, and there does not exist an interval of contiguous slots $I = [s_i, s_j]$ s.t.

- $|\{s_i + w_k - 1, \dots, s_j\}| \ge w_k$ for each demand $k \in \tilde{K}$,

- and $s \in \{s_i + \max_{k' \in \tilde{K}} w_k - 1, \dots, s_j - \max_{k \in \tilde{K}} w_k + 1\}$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $k, k' \in \tilde{K}$,

- and $2w_k \ge |I| + 1$ for each $k \in \tilde{K}$.

**Proof. Necessity.**

If $K_e \setminus \tilde{K} \ne \emptyset$, then the inequality (15) is dominated by the inequality (17) without changing its right hand side. Moreover, if there exists an interval of contiguous slots $I = [s_i, s_j]$ s.t.

- $|\{s_i + w_k - 1, \dots, s_j\}| \ge w_k$ for each demand $k \in \tilde{K}$,

- and $s \in \{s_i + \max_{k' \in \tilde{K}} w_k - 1, \dots, s_j - \max_{k \in \tilde{K}} w_k + 1\}$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $k, k' \in \tilde{K}$,

- and $2w_k \ge |I| + 1$ for each $k \in \tilde{K}$.

Then the inequality (15) is dominated by the inequality (22). Hence, the inequality (15) is not facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let $F_{\tilde{K}}^{e,s}$ denote the face induced by the inequality (15), which is given by

$$ F_{\tilde{K}}^{e,s} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = |\tilde{K}| + 1\}. $$

In order to prove that inequality $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k \le |\tilde{K}| + 1$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_{\tilde{K}}^{e,s}$ is a proper face, and $F_{\tilde{K}}^{e,s} \ne P(G, K, \mathbb{S})$.

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

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

- a set of last-slots $S_k^{39}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{39}$ with $|S_k^{39}| \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^{39}$ and $s' \in S_{k'}^{39}$ with $E_k^{39} \cap E_{k'}^{39} \ne \emptyset$ (non-overlapping constraint),

- and there is one demand $k$ from the set of demands $\tilde{K}$ (i.e., $k \in \tilde{K}$ s.t. the demand $k$ selects a slot $s'$ as last-slot in the solution $S^{39}$ with $s' \in \{s, \dots, s + w_k - 1\}$, i.e., $s' \in S_k^{39}$ for a demand $k \in \tilde{K}$, and for each $s' \in S_{k'}^{39}$ for all $k' \in \tilde{K} \setminus \{k\}$ we have $s' \notin \{s, \dots, s + w_{k'} - 1\}$,

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $S^{39}$, i.e., $e \in E_k^{39}$ for each $k \in \tilde{K}$.
Obviously, $S^{39}$ 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^{39}}, z^{S^{39}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. As a result, $F_{\tilde{K}}^{e,s}$ is not empty (i.e., $F_{\tilde{K}}^{e,s} \neq \emptyset$). Furthermore, given that $s \in \mathbb{S}$, this means that there exists at least one feasible slot assignment $S_k$ for each demands $k$ in $\tilde{K}$ with $S_k \cap \{s, ..., s+w_k-1\} = \emptyset$. Hence, $F_{\tilde{K}}^{e,s} \neq P(G, K, \mathbb{S})$.

We denote the inequality $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k \le |\tilde{K}| + 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})$. Suppose that $F_{\tilde{K}}^{e,s} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \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_0^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, ..., \bar{s}\}$ with $s' \notin \{s, ..., s+w_k-1\}$ if $k \in \tilde{K}$,

- and $\sigma_{s'}^k$ are equivalents for all $k \in \tilde{K}$ and all $s' \in \{s, ..., s+w_k-1\}$,

- 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 \neq e'$ if $k \in \tilde{K}$,

- and all $\mu_e^k$ are equivalents for the set of demands in $\tilde{K}$,

- and $\sigma_{s'}^k$ and $\mu_e^k$ are equivalents for all $k \in \tilde{K}$ and all $s' \in \{s, ..., s+w_k-1\}$.

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 \neq e'$ if $k \in \tilde{K}$. Consider a demand $k \in K$ and an edge $e' \in E \setminus (E_0^k \cup E_1^k)$ with $e \neq e'$ if $k \in \tilde{K}$. For that, we consider a solution $S'^{39} = (E'^{39}, S'^{39})$ in which

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

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

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k'^{39}$ and $s'' \in S_{k'}'^{39}$ with $E_k'^{39} \cap E_{k'}'^{39} \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'^{39}} |\{s' \in S_k'^{39}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

- and there is one demand $k$ from the set of demands $\tilde{K}$ (i.e., $k \in \tilde{K}$ s.t. the demand $k$ selects a slot $s'$ as last-slot in the solution $S'^{39}$ with $s' \in \{s, ..., s+w_k-1\}$, i.e., $s' \in S_k'^{39}$ for a demand $k \in \tilde{K}$, and for each $s' \in S_{k'}'^{39}$ for all $k' \in \tilde{K} \setminus \{k\}$ we have $s' \notin \{s, ..., s+w_{k'}-1\}$,

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

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $S'^{39}$, i.e., $e \in E_k'^{39}$ for each $k \in \tilde{K}$.

$S'^{39}$ 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'^{39}}, z^{S'^{39}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. Based on this, we derive a solution $S^{40}$ obtained from the solution $S'^{39}$ 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^{39}$ which means that $E_k^{40} = E_k'^{39} \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^{39}$ remain the same in the solution $S^{40}$, i.e., $S_k^{40} = S_{k'}'^{39}$ for each $k \in K$, and $E_{k'}^{40} = E_{k'}'^{39}$ for each $k' \in K \setminus \{k\}$. $S^{40}$ is clearly feasible given that

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

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

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{40}$ and $s'' \in S_{k'}^{40}$ with $E_k^{40} \cap E_{k'}^{40} \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^{40}} |\{s' \in S_k^{40}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{40}}, z^{S^{40}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. It follows that

$$ \mu x^{S'^{39}} + \sigma z^{S'^{39}} = \mu x^{S^{40}} + \sigma z^{S^{40}} = \mu x^{S'^{39}} + \mu_{e'}^k + \sigma z^{S'^{39}}. $$
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 \neq e'$ if $k \in \tilde{K}$, we iterate the same procedure for all $e \in E \setminus (E_0^k \cup E_1^k \cup \{e'\})$ with $e \neq e''$ if $k \in \tilde{K}$. 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 \neq e' \text{ if } k \in \tilde{K}. $$

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 \neq e' \text{ if } k \in \tilde{K}. $$

Let's us show that $\sigma_{s'}^k = 0$ for all $k \in K$ and all $s' \in \{w_k, ..., \bar{s}\}$ with $s' \notin \{s, ..., s + w_k - 1\}$ if $k \in \tilde{K}$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$ with $s' \notin \{s, ..., s + w_k - 1\}$ if $k \in \tilde{K}$. For that, we consider a solution $S^{39} = (E^{39}, S^{39})$ in which

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

- a set of last-slots $S_k^{39}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{39}$ with $|S_k^{39}| \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^{39}$ and $s'' \in S_{k'}^{39}$ with $E_k^{39} \cap E_{k'}^{39} \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^{39}} |\{s' \in S_k^{39}, 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'}^{39}$ with $E_k^{39} \cap E_{k'}^{39} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{39}$ assigned to the demand $k$ in the solution $S^{39}$),

- and there is one demand $k$ from the set of demands $\tilde{K}$ (i.e., $k \in \tilde{K}$ s.t. the demand $k$ selects a slot $s'$ as last-slot in the solution $S^{39}$ with $s' \in \{s, ..., s + w_k - 1\}$, i.e., $s' \in S_k^{39}$ for a demand $k \in \tilde{K}$, and for each $s' \in S_k^{39}$ for all $k' \in \tilde{K} \setminus \{k\}$ we have $s' \notin \{s, ..., s + w_{k'} - 1\}$,

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $S^{39}$, i.e., $e' \in E_k^{39}$ for each $k \in \tilde{K}$.

$S^{39}$ 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^{39}}, z^{S^{39}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. Based on this, we distinguish two cases:

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

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

• a set of last-slots $S_k^{41}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{41}$ with $|S_k^{41}| \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^{41}$ and $s'' \in S_{k'}^{41}$ with $E_k^{41} \cap E_{k'}^{41} \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^{41}} |\{s' \in S_k^{41}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{41}}, z^{S^{41}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. We then obtain that

$$ \mu x^{S^{39}} + \sigma z^{S^{39}} = \mu x^{S^{41}} + \sigma z^{S^{41}} = \mu x^{S^{39}} + \sigma z^{S^{39}} + \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, ..., s + w_k - 1\}$ if $k \in \tilde{K}$.
- with changing the paths established in $S^{39}$: we construct a solution $S'^{41}$ derived from the solution $S^{39}$ 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^{39}$ (i.e., $E_k'^{41} = E_k^{39}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{41} \neq E_k^{39}$ for each $k \in \tilde{K}$) s.t.

* a new feasible path $E_k'^{41}$ 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^{39}$ and $s'' \in S_{k'}^{39}$ with $E_k'^{41} \cap E_{k'}^{39} \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'^{41}} |\{s' \in S_k^{39}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e' \in E_k^{39}} |\{s' \in S_k^{39}, 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'}^{39}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{39}$ assigned to the demand $k$ in the solution $S^{39}$).

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

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

* a set of last-slots $S_k'^{41}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{41}$ with $|S_k'^{41}| \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'^{41}$ and $s'' \in S_{k'}'^{41}$ with $E_k'^{41} \cap E_{k'}'^{41} \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'^{41}} |\{s' \in S_k'^{41}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S'^{41}}, z^{S'^{41}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. We have so

$$ \mu x^{S^{39}} + \sigma z^{S^{39}} = \mu x^{S'^{41}} + \sigma z^{S'^{41}} = \mu x^{S^{39}} + \sigma z^{S^{39}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k^{39}} \mu_{e'}^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e'' \in E_k'^{41}} \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, ..., s + w_k - 1\}$ if $k \in \tilde{K}$ 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 \tilde{K}$.

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$ with $s' \notin \{s, ..., s + w_k - 1\}$ if $k \in \tilde{K}$ s.t. we find

$$ \sigma_{s'}^k = 0, \text{ for demand } k \text{ and all slots } s' \in \{w_k, ..., \bar{s}\} \text{ with } s' \notin \{s, ..., s + w_k - 1\} \text{ if } k \in \tilde{K}. $$

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}\} \text{ with } s' \notin \{s, ..., s + w_{k'} - 1\} \text{ if } k' \in \tilde{K}. $$

Consequently, we conclude that

$$ \sigma_{s'}^k = 0, \text{ for all } k \in K \text{ and all slots } s' \in \{w_k, ..., \bar{s}\} \text{ with } s' \notin \{s, ..., s + w_k - 1\} \text{ if } k \in \tilde{K}. $$

Let prove that $\sigma_{s'}^k$ for all $k \in \tilde{K}$ and all $s' \in \{s, ..., s + w_k - 1\}$ are equivalents. Consider a demand $k'$ and a slot $s' \in \{s, ..., s + w_{k'} - 1\}$ with $k' \in \tilde{K}$. For that, we consider a solution $\tilde{S}^{39} = (\tilde{E}^{39}, \tilde{S}^{39})$ in which

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

- a set of last-slots $\tilde{S}_k^{39}$ is assigned to each demand $k \in K$ along each edge $e' \in \tilde{E}_k^{39}$ with $|\tilde{S}_k^{39}| \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^{39}$ and $s'' \in \tilde{S}_{k'}^{39}$ with $\tilde{E}_k^{39} \cap \tilde{E}_{k'}^{39} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e' \in \tilde{E}_k^{39}} |\{s' \in \tilde{S}_k^{39}, 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^{39}$ with $\tilde{E}_k^{39} \cap \tilde{E}_{k'}^{39} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_{k'}^{39}$ assigned to the demand $k'$ in the solution $S^{39}$),

- and there is one demand $k$ from the set of demands $\tilde{K}$ (i.e., $k \in \tilde{K}$ s.t. the demand $k$ selects a slot $s'$ as last-slot in the solution $\tilde{S}^{39}$ with $s' \in \{s, ..., s + w_k - 1\}$, i.e., $s' \in \tilde{S}_k^{39}$ for a demand $k \in \tilde{K}$, and for each $s' \in \tilde{S}_{k'}^{39}$ for all $k' \in \tilde{K} \setminus \{k\}$ we have $s' \notin \{s, ..., s + w_{k'} - 1\}$,

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $\tilde{S}^{39}$, i.e., $e' \in \tilde{E}_k^{39}$ for each $k \in \tilde{K}$.

$\tilde{S}^{39}$ 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}^{39}}, z^{\tilde{S}^{39}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \tilde{s})} z_{s'}^k = 1$. Based on this, we distinguish two cases:

- without changing the paths established in $\tilde{S}^{39}$: we derive a solution $S^{42} = (E^{42}, S^{42})$ from the solution $\tilde{S}^{39}$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $\tilde{S}^{39}$ (i.e., $E_k^{42} = \tilde{E}_k^{39}$ for each $k \in K$), and also the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{39}$ remain the same in $S^{42}$, i.e., $\tilde{S}_{k''}^{39} = S_{k''}^{42}$ for each demand $k'' \in K \setminus \{k, k'\}$, and $S_{k'}^{42} = \tilde{S}_{k'}^{39} \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^{39}$ 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^{42} = (\tilde{S}_k^{39} \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'}^{42}$ with $E_k^{42} \cap E_{k'}^{42} \neq \emptyset$. The solution $S^{42}$ is feasible given that

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

* a set of last-slots $S_k^{42}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{42}$ with $|S_k^{42}| \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^{42}$ and $s'' \in S_{k'}^{42}$ with $E_k^{42} \cap E_{k'}^{42} \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^{42}} |\{s' \in S_k^{42}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{\tilde{S}^{39}} + \sigma z^{\tilde{S}^{39}} = \mu x^{S^{42}} + \sigma z^{S^{42}} = \mu x^{\tilde{S}^{39}} + \sigma z^{\tilde{S}^{39}} + \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, ..., \tilde{s}\}$ with $k' \in \tilde{K}$ and $s' \in \{s, ..., s + w_{k'} - 1\}$ given that $\sigma_{\tilde{s}}^{k} = 0$ for $\tilde{s} \notin \{s, ..., s + w_k - 1\}$ with $k \in \tilde{K}$.

- with changing the paths established in $\tilde{S}^{39}$: we construct a solution $S'^{42}$ derived from the solution $\tilde{S}^{39}$ 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 $\tilde{S}^{39}$ (i.e., $E_k'^{42} = \tilde{E}_k^{39}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{42} \neq \tilde{E}_k^{39}$ for each $k \in \tilde{K}$), and also the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{39}$ remain the same in $S'^{42}$, i.e., $\tilde{S}_{k''}^{39} = S_{k''}'^{42}$ for each demand $k'' \in K \setminus \{k, k'\}$, and $S_{k'}'^{42} = \tilde{S}_{k'}^{39} \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^{39}$ 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'^{42} = (\tilde{S}_k^{39} \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'}'^{42}$ with $E_k'^{42} \cap E_{k'}'^{42} \neq \emptyset$. The solution $S'^{42}$ is clearly feasible given that

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

* a set of last-slots $S_k'^{42}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{42}$ with $|S_k'^{42}| \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'^{42}$ and $s'' \in S_{k'}'^{42}$ with $E_k'^{42} \cap E_{k'}'^{42} \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'^{42}} |\{s' \in S_k'^{42}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).
The corresponding incidence vector $(x^{S^{42}}, z^{S^{42}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_{e'}^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. We have so

$$ \mu x^{\tilde{S}^{39}} + \sigma z^{\tilde{S}^{39}} = \mu x^{S^{42}} + \sigma z^{S^{42}} = \mu x^{\tilde{S}^{39}} + \sigma z^{\tilde{S}^{39}} + \sigma_{s''}^{k'} - \sigma_{s'}^k + \sigma_{\bar{s}}^k \\ - \sum_{k \in \tilde{K}} \sum_{e' \in \tilde{E}_k^{39}} \mu_{e'}^k + \sum_{k \in \tilde{K}} \sum_{e' \in \tilde{E}_k^{42}} \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, ..., s + w_{k'} - 1\}$ given that $\sigma_{\bar{s}}^k = 0$ for $\tilde{s} \notin \{s, ..., s + w_k - 1\}$ 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 set of demands $\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, ..., s + w_k - 1\}$ and $s' \in \{s, ..., s + w_{k'} - 1\}$. We re-do the same procedure for each two slots $s, s' \in \{s, ..., s + w_k - 1\}$ 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, ..., s + w_k - 1\}. $$

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^{43} = (E^{43}, S^{43})$ defined as below

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

- a set of last-slots $S_k^{43}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{43}$ with $|S_k^{43}| \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^{43}$ and $s' \in S_{k'}^{43}$ with $E_k^{43} \cap E_{k'}^{43} \neq \emptyset$ (non-overlapping constraint),

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

- and all the demands in $\tilde{K}$ share the slot $s$ over the edge $e$ in the solution $S^{43}$, i.e., $\{s_i + w_k + 1, ..., s_j\} \cap S_k^{43} \neq \emptyset$ for each $k \in \tilde{K}$.

Obviously, $S^{43}$ 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^{43}}, z^{S^{43}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. Consider now a demand $k'$ in $\tilde{K}$ s.t. $e \notin E_{k'}^{43}$. For that, we consider a solution $\tilde{S}^{43} = (\tilde{E}^{43}, \tilde{S}^{43})$ in which

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

- a set of last-slots $\tilde{S}_k^{43}$ is assigned to each demand $k \in K$ along each edge $e \in \tilde{E}_k^{43}$ with $|\tilde{S}_k^{43}| \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^{43}$ and $s'' \in \tilde{S}_{k'}^{43}$ with $\tilde{E}_k^{43} \cap \tilde{E}_{k'}^{43} \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^{43}} |\{s' \in \tilde{S}_k^{43}, 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^{43}$ with $\tilde{E}_k^{43} \cap \tilde{E}_{k'}^{43} \neq \emptyset$,

- and there is one demand $k$ from the set of demands $\tilde{K}$ (i.e., $k \in \tilde{K}$ s.t. the demand $k$ pass through the edge $e$ in the solution $\tilde{S}^{43}$, i.e., $e \in \tilde{E}_k^{43}$ for a demand $k \in \tilde{K}$, and $e \notin \tilde{E}_{k'}^{43}$ for all $k' \in \tilde{K} \setminus \{k\}$,

- and all the demands in $\tilde{K}$ share the slot $s$ over the edge $e$ in the solution $\tilde{S}^{43}$, i.e., $\{s, ..., s + w_k - 1\} \cap \tilde{S}_k^{43} \neq \emptyset$ for each $k \in \tilde{K}$.

$\tilde{S}^{43}$ 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}^{43}}, z^{\tilde{S}^{43}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. Based on this, we derive a solution $S^{44} = (E^{44}, S^{44})$ from the solution $\tilde{S}^{43}$ by
- the paths assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{43}$ remain the same in $S^{44}$ (i.e., $E_k^{44} = \tilde{E}_k^{43}$ for each $k'' \in K \setminus \{k, k'\}$),

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

- modifying the path assigned to the demand $k'$ in $\tilde{S}^{43}$ from $\tilde{E}_k^{43}$ to a path $E_k^{44}$ passed through the edge $e$ (i.e., $e \in E_k^{44}$) 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^{43}$ and each $s' \in \tilde{S}_k^{43}$ with $\tilde{E}_k^{43} \cap E_k^{44} \neq \emptyset$,

- modifying the path assigned to the demand $k$ in $\tilde{S}^{43}$ with $e \in \tilde{E}_k^{43}$ and $k \in \tilde{K}$ from $\tilde{E}_k^{43}$ to a path $E_k^{44}$ without passing through the edge $e$ (i.e., $e \notin E_k^{44}$) 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 \tilde{S}_k^{43}$ and each $s' \in \tilde{S}_k^{43}$ with $\tilde{E}_k^{43} \cap E_k^{44} \neq \emptyset$, and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $s' \in \tilde{S}_k^{43}$ and each $s' \in \tilde{S}_k^{43}$ with $E_k^{44} \cap E_k^{44} \neq \emptyset$.

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

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

- a set of last-slots $S_k^{44}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{44}$ with $|S_k^{44}| \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^{44}$ and $s'' \in S_k^{44}$ with $E_k^{44} \cap E_k^{44} \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^{44}} |\{s' \in S_k^{44}, s'' \in \{s' - w_k + 1, ..., s'\}| \leq 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{44}}, z^{S^{44}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k = 1$. We then obtain that

$$ \mu x^{\tilde{S}^{43}} + \sigma z^{\tilde{S}^{43}} = \mu x^{S^{44}} + \sigma z^{S^{44}} = \mu x^{\tilde{S}^{43}} + \sigma z^{\tilde{S}^{43}} + \mu_e^{k'} - \mu_e^k + \sum_{e'' \in E_k^{44} \setminus \{e\}} \mu_e^{k''} - \sum_{e'' \in E_k^{44}} \mu_e^{k''} + \sum_{e'' \in E_k^{44}} \mu_e^{k''} - \sum_{e'' \in E_k^{43} \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 \in \tilde{K}$.

Given that the pair $(k, k')$ are chosen arbitrary in the set of demands $\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, ..., s + w_k - 1\}$. For that, we consider for each demand $k'$ with $k' \in \tilde{K}$, a solution $S^{45} = (E^{45}, S^{45})$ derived from the solution $\tilde{S}^{43}$ as below

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

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

- modifying the set of last-slots assigned to the demand $k'$ in $\tilde{S}^{43}$ from $\tilde{S}_k^{43}$ to $S_k^{45}$ s.t. $S_k^{45} \cap \{s, ..., s + w_{k'} - 1\} = \emptyset$.

Hence, there are $|\tilde{K}| - 1$ demands from $\tilde{K}$ that share the slot $s$ over the edge $e$ (i.e., all the demands in $\tilde{K} \setminus \{k'\}$), and two demands $\{k, k'\}$ from $\tilde{K}$ that use the edge $e$ in the solution $S^{45}$. The solution $S^{45}$ is then feasible given that

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

- a set of last-slots $S_k^{45}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{45}$ with $|S_k^{45}| \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^{45}$ and $s'' \in S_k^{45}$ with $E_k^{45} \cap E_k^{45} \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^{45}} |\{s' \in S_k^{45}, s'' \in \{s' - w_k + 1, ..., s'\}| \leq 1$ (non-overlapping constraint),
$$ - \text{and } \sum_{k \in \tilde{K}} |E_k^{45} \cap \{e\}| + |S_k^{45} \cap \{s, \dots, s + w_k - 1\}| = |\tilde{K}| + 1. $$

The corresponding incidence vector $(x^{S^{45}}, z^{S^{45}})$ is belong to $F$ and then to $F_{\tilde{K}}^{e,s}$ given that it is composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{s'=s}^{\min(s+w_k-1, \tilde{s})} z_{s'}^k = 1$. We then obtain that

$$ \mu x^{\tilde{S}^{43}} + \sigma z^{\tilde{S}^{43}} = \mu x^{S^{45}} + \sigma z^{S^{45}} = \mu x^{\tilde{S}^{43}} + \sigma z^{\tilde{S}^{43}} + \mu_e^{k'} - \sigma_{s'}^{k'} + \sum_{e'' \in E_{k'}^{45} \setminus \{e\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_{k'}^{43}} \mu_{e''}^{k'}. $$

It follows that $\mu_e^{k'} = \sigma_{s'}^{k'}$ for demand $k'$ and slot $s' \in \{s, ..., s + w_{k'} - 1\}$ 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, ..., s + w_{k'} - 1\}$, we found that

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

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, ..., s + w_k - 1\}. $$

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, ..., s + w_{k'} - 1\}$, we obtain that

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

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, ..., s + w_{k'} - 1\}. $$

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\}. \quad (49) $$
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, \dots, s + w_k - 1\}, \\ 0, & \text{otherwise.} \end{cases} $$

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

**Theorem 12.** Consider an edge $e \in E$, and a slot $s \in \mathbb{S}$. Let $\tilde{K}$ be a subset of demands in $K$ with $|\tilde{K}| \ge 3$, and $\sum_{k \in \tilde{K}} w_k \le \bar{s} - \sum_{k' \in K_e \setminus \tilde{K}} w_{k'}$. Then, the inequality (17) is facet defining for $P(G, K, \mathbb{S})$ if and only if there does not exist an interval of contiguous slots $I = [s_i, s_j]$ s.t.

- $|\{s_i + w_k - 1, \dots, s_j\}| \ge w_k$ for each demand $k \in \tilde{K}$,

- and $s \in \{s_i + \max_{k' \in \tilde{K}} w_k - 1, \dots, s_j - \max_{k \in \tilde{K}} w_k + 1\}$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $k, k' \in \tilde{K}$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $k \in \tilde{K}$ and each $k' \in K_e \setminus \tilde{K}$,

- and $2w_k \ge |I| + 1$ for each $k \in \tilde{K}$,

- and $2w_{k'} \ge |I| + 1$ for each $k' \in K_e \setminus \tilde{K}$.

**Proof. Necessity.**

If there exists an interval of contiguous slots $I = [s_i, s_j]$ s.t.

- $|\{s_i + w_k - 1, \dots, s_j\}| \ge w_k$ for each demand $k \in \tilde{K}$,

- and $s \in \{s_i + \max_{k' \in \tilde{K}} w_k - 1, \dots, s_j - \max_{k \in \tilde{K}} w_k + 1\}$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $k, k' \in \tilde{K}$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $k \in \tilde{K}$ and each $k' \in K_e \setminus \tilde{K}$,

- and $2w_k \ge |I| + 1$ for each $k \in \tilde{K}$,

- and $2w_{k'} \ge |I| + 1$ for each $k' \in K_e \setminus \tilde{K}$.

Then the inequality (17) is dominated by the inequality (23) for a clique $C = \tilde{K}$ and clique $C_e = K_e \setminus \tilde{K}$ in the conflict graph $\tilde{G}_I^e$. As result, the inequality (17) is not facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let's us denote $F_{\tilde{K}}^{e,s}$ the face induced by the inequality (17), which is given by

$$ F_{\tilde{K}}^{e,s} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{k \in \tilde{K}} x_e^k + \sum_{k \in \tilde{K}} \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k + \sum_{K_e \setminus \tilde{K}} \sum_{s'=s}^{\min(s+w_{k'}-1, \bar{s})} z_{s'}^{k'} = |\tilde{K}| + 1\}. $$

We denote the inequality $\sum_{k \in \tilde{K}} x_e^k + \sum_{k \in \tilde{K}} \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k + \sum_{K_e \setminus \tilde{K}} \sum_{s'=s}^{\min(s+w_{k'}-1, \bar{s})} z_{s'}^{k'} \le |\tilde{K}| + 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})$. Suppose that $F_{\tilde{K}}^{e,s} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \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_0^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}\}$ with $s' \notin \{s, \dots, s + w_k - 1\}$ if $k \in \tilde{K} \cup K_e$,
- and $\sigma_{s'}^k$ are equivalents for all $k \in \tilde{K} \cup K_e$ and all $s' \in \{s, ..., s+w_k-1\}$,

- 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 \neq e'$ if $k \in \tilde{K}$,

- and all $\mu_e^k$ are equivalents for the set of demands in $\tilde{K}$,

- and $\sigma_{s'}^{k'}$ and $\mu_e^k$ are equivalents for all $k \in \tilde{K}$ and all $k' \in \tilde{K} \cup K_e$ and all $s' \in \{s, ..., s+w_{k'}-1\}$.

We re-do the same technique of proof already detailed to prove that the inequality (15) is facet defining for $P(G, K, \mathbb{S})$ s.t. the solutions $S^{39} - S^{46}$ still feasible for $F_{\tilde{K}}^{e,s}$ given that their incidence vector are composed by $\sum_{k \in \tilde{K}} x_e^k + \sum_{k \in \tilde{K}} \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k + \sum_{K_e \setminus \tilde{K}} \sum_{s'=s}^{\min(s+w_{k'}-1, \bar{s})} z_{s'}^{k'} \le |\tilde{K}| + 1$. We conclude at the end 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, ..., w_k - 1\} \\ \rho, & \text{if } k \in \tilde{K} \cup K_e \text{ and } s' \in \{s, ..., s + w_k - 1\}, \\ 0, & \text{otherwise.} \end{cases} $$

$$ \text{As a result } (\mu, \sigma) = \sum_{k \in \tilde{K}} \rho \alpha_e^k + \sum_{k \in \tilde{K}} \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} \rho \beta_{s'}^k + \sum_{k \in K_e \setminus \tilde{K}} \sum_{s'=s}^{\min(s+w_{k'}-1, \bar{s})} \rho \beta_{s'}^{k'} + \gamma Q. $$

## 5.8 Non-Compatibility-Odd-Hole Inequalities

**Theorem 13.** Let $H$ be an odd-hole in the conflict graph $\tilde{G}_E^K$ with $|H| \ge 5$. Then, the inequality (36) is facet defining for $P(G, K, \mathbb{S})$ if and only if

- for each $v_{k',e'} \notin H$, there exists a node $v_{k,e} \in H$ s.t. the induced graph $\tilde{G}_E^K(H \setminus \{v_{k,e}\} \cup \{v_{k',e'}\})$ does not contain an odd-hole $H' = (H \setminus \{v_{k,e}\}) \cup \{v_{k',e'}\}$,

- and there does not exist a node $v_{k',e'} \notin H$ s.t. all the nodes $v_{k,e}$ in $H$ are linked with this node $v_{k',e'}$ in the conflict graph $\tilde{G}_E^K$.

**Proof.** **Necessity.**

We distinguish the following cases:

- if for a node $v_{k',e'} \notin H$ in $\tilde{G}_E^K$, there exists a node $v_{k,e} \in H$ s.t. the induced graph $\tilde{G}_E^K(H \setminus \{v_{k,e}\} \cup \{v_{k',e'}\})$ contains an odd-hole $H' = (H \setminus \{v_{k,e}\}) \cup \{v_{k',e'}\}$. This implies that the inequality (36) can be dominated using some technics of lifting based on the following two inequalities $\sum_{v_{k,e} \in H} x_e^k \le \frac{|H|-1}{2}$, and $\sum_{v_{k',e'} \in H'} x_{e'}^{k'} \le \frac{|H'|-1}{2}$.

- if there exists a node $v_{k',e'} \notin H$ in $\tilde{G}_E^S$ s.t. $v_{k',e'}$ is linked with all nodes $v_{k,e} \in H$. This implies that the inequality (36) can be dominated by the following valid inequality

$$ \sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} x_{e'}^{k'} \le \frac{|H|-1}{2}. $$

If no one of these cases is verified, the inequality (36) can never be dominated by another inequality without changing its right hand side. Otherwise, the inequality (36) is not facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let $F_H^{\tilde{G}_E^K}$ denote the face induced by the inequality (36), which is given by

$$ F_H^{\tilde{G}_E^K} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}\}. $$
In order to prove that inequality $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_H^{\tilde{G}_E^K}$ is a proper face, and $F_H^{\tilde{G}_E^K} \neq P(G, K, \mathbb{S})$. We construct a solution $S^{47} = (E^{47}, S^{47})$ as below

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

- a set of last-slots $S_k^{47}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{47}$ with $|S_k^{47}| \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^{47}$ and $s' \in S_{k'}^{47}$ with $E_k^{47} \cap E_{k'}^{47} \neq \emptyset$ (non-overlapping constraint),

- and there is $\frac{|H|-1}{2}$ pairs of demands edges $(k, e)$ from the odd-hole $H$ denoted by $H_{47}$ (i.e., $v_{k,e} \in H_{47}$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S^{47}$, i.e., $e \in E_k^{47}$ for each node $v_{k,e} \in H_{47}$, and $e' \notin E_{k'}^{47}$ for all $v_{k',e'} \in H \setminus H_{47}$.

Obviously, $S^{47}$ 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^{47}}, z^{S^{47}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. As a result, $F_H^{\tilde{G}_E^K}$ is not empty (i.e., $F_H^{\tilde{G}_E^K} \neq \emptyset$). Furthermore, given that $s \in \{w_k, ..., \bar{s}\}$ for each $v_{k,s} \in H$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $H$ with $s \notin S_k$ for each $v_{k,s} \in H$. This means that $F_H^{\tilde{G}_E^K} \neq P(G, K, \mathbb{S})$.

Let denote the inequality $\sum_{v_{k,e} \in H} x_e^k \le \frac{|H|-1}{2}$ 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})$. Suppose that $F_H^{\tilde{G}_E^K} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \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_0^{k'}|, \gamma_2 \in \mathbb{R} \sum_{k \in K} |E_k^{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, ..., \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 $v_{k,e} \notin H$,

- and $\mu_e^k$ are equivalent for all $v_{k,e} \in H$.

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 $v_{k,e} \notin H$. Consider a demand $k \in K$ and an edge $e \in E \setminus (E_0^k \cup E_1^k)$. For that, we consider a solution $S'^{47} = (E'^{47}, S'^{47})$ in which

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

- a set of last-slots $S_k'^{47}$ is assigned to each demand $k \in K$ along each edge $e \in E_k'^{47}$ with $|S_k'^{47}| \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'^{47}$ and $s'' \in S_{k'}'^{47}$ with $E_k'^{47} \cap E_{k'}'^{47} \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'^{47}} |\{s' \in S_k'^{47}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

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

- and there is $\frac{|H|-1}{2}$ pairs of demand-edge $(k, e)$ from the odd-hole $H$ denoted by $H_{47}'$ (i.e., $v_{k,e} \in H_{47}'$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S'^{47}$, i.e., $e \in E_k'^{47}$ for each node $v_{k,e} \in H_{47}'$, and $e' \notin E_{k'}'^{47}$ for all $v_{k',e'} \in H \setminus H_{47}'$.

$S'^{47}$ 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'^{47}}, z^{S'^{47}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. Based on this, we derive a solution $S^{48}$ obtained from the solution $S'^{47}$ 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^{47}$ which means that $E_k^{48} = E_k'^{47} \cup \{e\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^{47}$ remain the same in the solution $S^{48}$, i.e., $S_k^{48} = S_k'^{47}$ for each $k \in K$, and $E_{k'}^{48} = E_{k'}'^{47}$ for each $k' \in K \setminus \{k\}$. $S^{48}$ is clearly feasible given that

- and a feasible path $E_k^{48}$ is assigned to each demand $k \in K$ (routing constraint),
- a set of last-slots $S_k^{48}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{48}$ with $|S_k^{48}| \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^{48}$ and $s'' \in S_k^{48}$ with $E_k^{48} \cap E_{k'}^{48} \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^{48}} |\{s' \in S_k^{48}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{48}}, z^{S^{48}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. It follows that

$$ \mu x^{S^{47}} + \sigma z^{S^{47}} = \mu x^{S^{48}} + \sigma z^{S^{48}} = \mu x^{S^{47}} + \mu_e^k + \sigma z^{S^{47}}. $$

As a result, $\mu_e^k = 0$ for demand $k$ and an edge $e$ with $v_{k,e} \notin H$.

As $e$ is chosen arbitrarily for the demand $k$ with $e \notin E_0^k \cup E_1^k$ and $v_{k,e} \notin H$, we iterate the same procedure for all $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$ with $v_{k,e'} \notin H$. 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 } v_{k,e} \notin H. $$

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)$ with $v_{k,e'} \notin H$. 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 } v_{k,e} \notin H. $$

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^{47} = (E^{47}, S^{47})$ in which

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

- a set of last-slots $S_k^{47}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{47}$ with $|S_k^{47}| \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^{47}$ and $s'' \in S_k^{47}$ with $E_k^{47} \cap E_{k'}^{47} \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^{47}} |\{s' \in S_k^{47}, 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^{47}$ with $E_k^{47} \cap E_{k'}^{47} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{47}$ assigned to the demand $k$ in the solution $S^{47}$),

- and there is $\frac{|H|-1}{2}$ pairs of demand-edge $(k, e)$ from the odd-hole $H$ denoted by $H^{47}$ (i.e., $v_{k,e} \in H^{47}$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S^{47}$, i.e., $e \in E_k^{47}$ for each node $v_{k,e} \in H^{47}$, and $e' \notin E_{k'}^{47}$ for all $v_{k',e'} \in H \setminus H^{47}$.

$S^{47}$ 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^{47}}, z^{S^{47}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. Based on this, we distinguish two cases:

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

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

* a set of last-slots $S_k^{49}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{49}$ with $|S_k^{49}| \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^{49}$ and $s'' \in S_k^{49}$ with $E_k^{49} \cap E_{k'}^{49} \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^{49}} |\{s' \in S_k^{49}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{49}}, z^{S^{49}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. We then obtain that

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

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$.
- with changing the paths established in $S^{47}$: we construct a solution $S'^{49}$ derived from the solution $S^{47}$ 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^{47}$ (i.e., $E_k'^{49} = E_k^{47}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{49} \neq E_k^{47}$ for each $k \in \tilde{K}$) s.t.

* a new feasible path $E_k'^{49}$ 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^{47}$ and $s'' \in S_{k'}^{47}$ with $E_k'^{49} \cap E_{k'}^{47} \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'^{49}} |\{s' \in S_k^{47}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e \in E_k^{47}} |\{s' \in S_k^{47}, 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^{47}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{47}$ assigned to the demand $k$ in the solution $S^{47}$).

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

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

* a set of last-slots $S_k'^{49}$ is assigned to each demand $k \in K$ along each edge $e \in E_k'^{49}$ with $|S_k'^{49}| \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'^{49}$ and $s'' \in S_{k'}'^{49}$ with $E_k'^{49} \cap E_{k'}'^{49} \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'^{49}} |\{s' \in S_k'^{49}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S'^{49}}, z^{S'^{49}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. We have so

$$ \mu x^{S^{47}} + \sigma z^{S^{47}} = \mu x^{S'^{49}} + \sigma z^{S'^{49}} = \mu x^{S^{47}} + \sigma z^{S^{47}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e \in E_k'^{47}} \tilde{\mu}_e^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k'^{49}} \tilde{\mu}_{e'}^{\tilde{k}}. $$

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ 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 $v_{k,e} \notin H$.

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$ with $v_{k,s'} \notin H$ s.t. we find

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

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}\} \text{ with } v_{k',s} \notin H. $$

Consequently, we conclude that

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

Let's prove that $\mu_e^k$ for all $v_{k,e}$ are equivalents. Consider a node $v_{k',e'}$ in $H$ s.t. $e' \notin E_k'^{47}$. For that, we consider a solution $\tilde{S}^{47} = (\tilde{E}^{47}, \tilde{S}^{47})$ in which

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

- a set of last-slots $\tilde{S}_k'^{47}$ is assigned to each demand $k \in K$ along each edge $e \in \tilde{E}_k'^{47}$ with $|\tilde{S}_k'^{47}| \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'^{47}$ and $s'' \in \tilde{S}_{k'}'^{47}$ with $\tilde{E}_k'^{47} \cap \tilde{E}_{k'}'^{47} \neq \emptyset$, i.e., for each edge $e \in E$ and each slot $s'' \in S$ we have $\sum_{k \in K, e \in \tilde{E}_k'^{47}} |\{s' \in \tilde{S}_k'^{47}, 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'^{47}$ with $\tilde{E}_k'^{47} \cap \tilde{E}_{k'}'^{47} \neq \emptyset$,

- and there is $\frac{|H|-1}{2}$ pairs of demand-edge $(k, e)$ from the odd-hole $H$ denoted by $\tilde{H}_{47}$ (i.e., $v_{k,e} \in \tilde{H}_{47}$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $\tilde{S}^{47}$, i.e., $e \in \tilde{E}_k'^{47}$ for each node $v_{k,e} \in \tilde{H}_{47}$, and $e'' \notin \tilde{E}_{k'}'^{47}$ for all $v_{k',e''} \in H \setminus \tilde{H}_{47}$.
$\tilde{S}^{47}$ 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}^{47}}, z^{\tilde{S}^{47}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. Based on this, we distinguish two cases:

- without changing the spectrum assignment established in $\tilde{S}^{47}$: we derive a solution $S^{50} = (E^{50}, S^{50})$ from the solution $\tilde{S}^{47}$ by

* modifying the path assigned to the demand $k'$ in $\tilde{S}^{47}$ from $\tilde{E}_{k'}^{47}$ to a path $E_{k'}^{50}$ passed through the edge $e'$ with $v_{k',e'} \in H$,

* and selecting a pair of demand-edge $(k, e)$ from the set of pairs of demand-edge in $\tilde{H}_{47}$ s.t. $v_{k',e'}$ is not linked with any node $v_{k''},e''$ in $\tilde{H}_{47} \setminus \{v_{k,e}\}$,

* modifying the path assigned to the demand $k$ in $\tilde{S}^{47}$ with $e \in \tilde{E}_k^{47}$ and $v_{k,e} \in H$ from $\tilde{E}_k^{47}$ to a path $E_k^{50}$ without passing through any edge $e'' \in E \setminus (E_0^k \cup E_1^k)$ s.t. $v_{k',e'}$ and $v_{k,e''}$ linked in $H$ and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k' \in K$ and each $s' \in \tilde{S}_{k'}^{47}$ with $\tilde{E}_{k'}^{47} \cap E_k^{50} \neq \emptyset$.

The paths assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{47}$ remain the same in $S^{50}$ (i.e., $E_k^{50} = \tilde{E}_{k''}^{47}$ for each $k'' \in K \setminus \{k, k'\}$), and also without modifying the last-slots assigned to the demands $K$ in $\tilde{S}^{47}$, i.e., $\tilde{S}_k^{47} = S_k^{50}$ for each demand $k \in K$. The solution $S^{50}$ is feasible given that

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

* a set of last-slots $S_k^{50}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{50}$ with $|S_k^{50}| \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^{50}$ and $s'' \in S_{k'}^{50}$ with $E_k^{50} \cap E_{k'}^{50} \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^{50}} |\{s' \in S_k^{50}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{50}}, z^{S^{50}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. We then obtain that

$$ \mu x^{\tilde{S}^{47}} + \sigma z^{\tilde{S}^{47}} = \mu x^{S^{50}} + \sigma z^{S^{50}} = \mu x^{\tilde{S}^{47}} + \sigma z^{\tilde{S}^{47}} + \mu_{e'}^{k'} - \mu_e^k + \sum_{e'' \in E_{k'}^{50} \setminus \{e'\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_k^{47}} \mu_{e''}^{k'} + \sum_{e'' \in E_k^{50}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_k^{47} \setminus \{e\}} \mu_{e''}^{k'}. $$

It follows that $\mu_{e'}^{k'} = \mu_e^k$ for demand $k'$ and an edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$ with $v_{k',e'} \in H$ 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 $v_{k,e''} \notin H$.

- with changing the spectrum assignment established in $\tilde{S}^{47}$: we construct a solution $S'^{50}$ derived from the solution $\tilde{S}^{47}$ by

* modifying the path assigned to the demand $k'$ in $\tilde{S}^{47}$ from $\tilde{E}_{k'}^{47}$ to a path $E_{k'}^{50}$ passed through the edge $e'$ with $v_{k',e'} \in H$,

* and selecting a pair of demand-edge $(k, e)$ from the set of pairs of demand-edge in $H_{47}$ s.t. $v_{k',e'}$ is not linked with any node $v_{k''},e''$ in $\tilde{H}_{47} \setminus \{v_{k,e}\}$,

* modifying the path assigned to the demand $k$ in $\tilde{S}^{47}$ with $e \in \tilde{E}_k^{47}$ and $v_{k,e} \in H$ from $\tilde{E}_k^{47}$ to a path $E_k'^{50}$ without passing through any edge $e'' \in E \setminus (E_0^k \cup E_1^k)$ s.t. $v_{k',e'}$ and $v_{k,e''}$ linked in $H$,

* modifying the last-slots assigned to some demands $\tilde{K} \subset K$ from $\tilde{S}_k^{47}$ to $S_k'^{50}$ for each $\tilde{k} \in \tilde{K}$ while satisfying non-overlapping constraint.

The paths assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{47}$ remain the same in $S'^{50}$ (i.e., $E_k'^{50} = \tilde{E}_{k''}^{47}$ for each $k'' \in K \setminus \{k, k'\}$), and also without modifying the last-slots assigned to the demands $K \setminus \tilde{K}$ in $\tilde{S}^{47}$, i.e., $\tilde{S}_k^{47} = S_k'^{50}$ for each demand $k \in K \setminus \tilde{K}$. The solution $S'^{50}$ is clearly feasible given that

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

* a set of last-slots $S_k'^{50}$ is assigned to each demand $k \in K$ along each edge $e \in E_k'^{50}$ with $|S_k'^{50}| \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'^{50}$ and $s'' \in S_{k'}'^{50}$ with $E_k'^{50} \cap E_{k'}'^{50} \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'^{50}} |\{s' \in S_k'^{50}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).
The corresponding incidence vector $(x^{S^{50}}, z^{S^{50}})$ is belong to $F$ and then to $F_H^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k = \frac{|H|-1}{2}$. We have so

$$ \mu x^{\tilde{S}^{47}} + \sigma z^{\tilde{S}^{47}} = \mu x^{S^{50}} + \sigma z^{S^{50}} = \mu x^{\tilde{S}^{47}} + \sigma z^{\tilde{S}^{47}} + \mu_{e'}^{k'} - \mu_e^k + \sum_{\tilde{k} \in \tilde{K}} \sum_{s' \in S_{\tilde{k}}^{50}} \sigma_{s'}^{\tilde{k}} - \sum_{s \in S_{\tilde{k}}^{47}} \sigma_s^{\tilde{k}} \\ + \sum_{e'' \in E_{k'}^{50} \setminus \{e'\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_{k'}^{47}} \mu_{e''}^{k'} + \sum_{e'' \in E_{k'}^{50}} \mu_e^k - \sum_{e'' \in \tilde{E}_{k'}^{47} \setminus \{e\}} \mu_{e''}^k. $$

It follows that $\mu_{e'}^{k'} = \mu_e^k$ for demand $k'$ and an edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$ with $v_{k',e'} \in H$ 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 $v_{k,e''} \notin H$, and $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$.

Given that the pair $(v_{k,e}, v_{k',e'})$ are chosen arbitrary in the odd-hole $H$, we iterate the same procedure for all pairs $(v_{k,e}, v_{k',e'})$ s.t. we find

$$ \mu_e^k = \mu_{e'}^{k'}, \text{ for all pairs } (v_{k,e}, v_{k',e'}) \in H. $$

Consequently, we obtain that $\mu_e^k = \rho$ for all $v_{k,e} \in H$.

On the other hand, we ensure that all the edges $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, $$

On the other hand, 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 (50) $$

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 } v_{k,e} \in H, \\ 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\}, \\ 0, & \text{otherwise.} \end{cases} $$

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

**Theorem 14.** Let $H$ be an odd-hole, and $C$ be a clique in the conflict graph $\tilde{G}_E^K$ with

- $|H| \ge 5$,

- and $|C| \ge 3$,

- and $H \cap C = \emptyset$,

- and the nodes $(v_{k,e}, v_{k',e'})$ are linked in $\tilde{G}_E^K$ for all $v_{k,e} \in H$ and $v_{k',e'} \in C$.

Then, the inequality (37) is facet defining for $P(G, K, \mathbb{S})$ if and only if for each node $v_{k''},e''$ in $\tilde{G}_E^K$ with $v_{k''},e'' \notin H \cup C$ and $C \cup \{v_{k''},e''\}$ is a clique in $\tilde{G}_E^K$, there exists a subset of nodes $\tilde{H} \subseteq H$ of size $\frac{|H|-1}{2}$ s.t. $\tilde{H} \cup \{v_{k''},e''\}$ is stable in $\tilde{G}_E^K$.

**Proof.** **Necessity.**

If there exists a node $v_{k''},e'' \notin H \cup C$ in $\tilde{G}_E^K$ s.t. $v_{k''},e''$ is linked with all nodes $v_{k,e} \in H$ and also with all nodes $v_{k'},e' \in C$. This implies that the inequality (37) can be dominated by the following valid inequality

$$ \sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} + \frac{|H|-1}{2} x_{e''}^{k''} \le \frac{|H|-1}{2}. $$

As a result, the inequality (37) is not facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let $F_{H,C}^{\tilde{G}_E^K}$ denote the face induced by the inequality (37), which is given by

$$ F_{H,C}^{\tilde{G}_E^K} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}\}. $$

In order to prove that inequality $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_{H,C}^{\tilde{G}_E^K}$ is a proper face, and $F_{H,C}^{\tilde{G}_E^K} \ne P(G, K, \mathbb{S})$. We construct a solution $S^{52} = (E^{52}, S^{52})$ as below

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

- a set of last-slots $S_k^{52}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{52}$ with $|S_k^{52}| \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^{52}$ and $s' \in S_{k'}^{52}$ with $E_k^{52} \cap E_{k'}^{52} \ne \emptyset$ (non-overlapping constraint),

- and there is $\frac{|H|-1}{2}$ pairs of demands edges $(k, e)$ from the odd-hole $H$ denoted by $H_{52}$ (i.e., $v_{k,e} \in H_{52}$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $S^{52}$, i.e., $e \in E_k^{52}$ for each node $v_{k,e} \in H_{52}$, and $e' \notin E_{k'}^{52}$ for all $v_{k',e'} \in H \setminus H_{52}$.

Obviously, $S^{52}$ 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^{52}}, z^{S^{52}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_{H,C}^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}$.

As a result, $F_{H,C}^{\tilde{G}_E^K}$ is not empty (i.e., $F_{H,C}^{\tilde{G}_E^K} \ne \emptyset$). Furthermore, given that $s \in \{w_k, \dots, \bar{s}\}$ for each $v_{k,s} \in H$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $H$ with $s \notin S_k$ for each $v_{k,s} \in H$. This means that $F_{H,C}^{\tilde{G}_E^K} \ne P(G, K, \mathbb{S})$.

Let denote the inequality $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} \le \frac{|H|-1}{2}$ 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})$. Suppose that $F_{H,C}^{\tilde{G}_E^K} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \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_0^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, ..., \bar{s}\}$ as done in the proof of theorem 13,

- 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 $v_{k,e} \notin H \cup C$ as done in the proof of theorem 13,

- and $\mu_e^k$ are equivalent for all $v_{k,e} \in H$ as done in the proof of theorem 13,

given that the solutions defined in the proof of theorem 13, their corresponding incidence vector are belong to $P(G, K, \mathbb{S})$ and then to $F_{H,C}^{\mathbb{G}_E^K}$ given that they are composed by $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}$.

Let us prove now that $\mu_{e'}^{k'}$ are equivalent for all $v_{k',e'} \in C$. For this, we consider a node $v_{k',e'}$ in $C$ s.t. $e' \notin E_k^{52}$. For that, we consider a solution $\tilde{S}^{52} = (\tilde{E}^{52}, \tilde{S}^{52})$ in which

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

- a set of last-slots $\tilde{S}_k^{52}$ is assigned to each demand $k \in K$ along each edge $e \in \tilde{E}_k^{52}$ with $|\tilde{S}_k^{52}| \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^{52}$ and $s'' \in \tilde{S}_{k'}^{52}$ with $\tilde{E}_k^{52} \cap \tilde{E}_{k'}^{52} \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^{52}} |\{s' \in \tilde{S}_k^{52}, 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^{52}$ with $\tilde{E}_k^{52} \cap \tilde{E}_{k'}^{52} \neq \emptyset$,

- and there is $\frac{|H|-1}{2}$ pairs of demand-edge $(k, e)$ from the odd-hole $H$ denoted by $\tilde{H}_{52}$ (i.e., $v_{k,e} \in \tilde{H}_{52}$ s.t. the demand $k$ selects the edge $e$ for its routing in the solution $\tilde{S}^{52}$, i.e., $e \in \tilde{E}_k^{52}$ for each node $v_{k,e} \in \tilde{H}_{52}$, and $e'' \notin \tilde{E}_{k'}^{52}$ for all $v_{k',e''} \in H \setminus \tilde{H}_{52}$.

$\tilde{S}^{52}$ 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^{52}}, z^{\tilde{S}^{52}})$ is belong to $F$ and then to $F_{H,C}^{\mathbb{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}$. Based on this, we distinguish two cases:

- without changing the paths established in $\tilde{S}^{52}$: we derive a solution $S^{54} = (E^{54}, S^{54})$ from the solution $\tilde{S}^{52}$ by

* modifying the path assigned to the demand $k'$ in $\tilde{S}^{52}$ from $\tilde{E}_{k'}^{52}$ to a path $E_{k'}^{54}$ passed through the edge $e'$ with $v_{k',e'} \in C$,

* modifying the path assigned to each demand $k$ with $v_{k,e} \in \tilde{H}_{52}$ in $\tilde{S}^{52}$ with $e \in \tilde{E}_k^{52}$ and $v_{k,e} \in H$ from $\tilde{E}_k^{52}$ to a path $E_k^{54}$ without passing through any edge $e'' \in E \setminus (E_0^k \cup E_1^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'}^{52}$ with $\tilde{E}_{k'}^{52} \cap E_k^{54} \neq \emptyset$.

The paths assigned to the demands $K \setminus (K(\tilde{H}_{52}) \cup \{k'\})$ in $\tilde{S}^{52}$ remain the same in $S^{54}$ (i.e., $E_k^{54} = \tilde{E}_{k'}^{52}$ for each $k' \in K \setminus \{k, k'\}$), and also without modifying the last-slots assigned to the demands $K$ in $\tilde{S}^{52}$, i.e., $\tilde{S}_k^{52} = S_k^{54}$ for each demand $k \in K$. The solution $S^{54}$ is feasible given that

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

* a set of last-slots $S_k^{54}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{54}$ with $|S_k^{54}| \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^{54}$ and $s'' \in S_{k'}^{54}$ with $E_k^{54} \cap E_{k'}^{54} \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 S_k^{54}} |\{s' \in S_k^{54}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{54}}, z^{S^{54}})$ is belong to $F$ and then to $F_{H,C}^{\mathbb{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}$. We then obtain that

$$ \mu x^{\tilde{S}^{52}} + \sigma z^{\tilde{S}^{52}} = \mu x^{S^{54}} + \sigma z^{S^{54}} = \mu x^{\tilde{S}^{52}} + \sigma z^{\tilde{S}^{52}} + \mu_{e'}^{k'} - \sum_{v_{k,e} \in \tilde{H}_{52}} \mu_e^k + \sum_{e'' \in E_{k'}^{54} \setminus \{e'\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_{k'}^{52}} \mu_{e''}^{k'} + \sum_{e'' \in E_k^{54}} \mu_{e''}^{k'} - \sum_{k \in K(\tilde{H}_{52})} \sum_{e'' \in \tilde{E}_k^{52}} \mu_{e''}^k $$
It follows that $\mu_{e'}^{k'} = \sum_{v_{k,e} \in \tilde{H}_{52}} \mu_e^k$ for demand $k'$ and an edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$ with $v_{k',e'} \in H$ 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 $v_{k,e''} \notin H \cup C$. As a result, $\mu_{e'}^{k'} = \rho \frac{|H|-1}{2}$.

– with changing the paths established in $\tilde{S}^{52}$: we construct a solution $S^{54}$ derived from the solution $\tilde{S}^{52}$ by

* modifying the path assigned to the demand $k'$ in $\tilde{S}^{52}$ from $\tilde{E}_{k'}^{52}$ to a path $E_{k'}^{54}$ passed through the edge $e'$ with $v_{k',e'} \in C$,

* and modifying the path assigned to each demand $k$ with $v_{k,e} \in H_{52}$ in $\tilde{S}^{52}$ with $e \in \tilde{E}_k^{52}$ and $v_{k,e} \in H$ from $\tilde{E}_k^{52}$ to a path $E_k^{54}$ without passing through any edge $e'' \in E \setminus (E_0^k \cup E_1^k)$,

* modifying the last-slots assigned to some demands $\tilde{K} \subset K$ from $\tilde{S}_k^{52}$ to $S_k^{54}$ for each $\tilde{k} \in \tilde{K}$ while satisfying non-overlapping constraint.

The paths assigned to the demands $K \setminus (K(H_{52}) \cup \{k'\})$ in $\tilde{S}^{52}$ remain the same in $S^{54}$ (i.e., $E_k^{54} = \tilde{E}_k^{52}$ for each $k'' \in K \setminus \{k, k'\}$), and also without modifying the last-slots assigned to the demands $K \setminus \tilde{K}$ in $\tilde{S}^{52}$, i.e., $\tilde{S}_k^{52} = S_k^{54}$ for each demand $k \in K \setminus \tilde{K}$. The solution $S^{54}$ is clearly feasible given that

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

* a set of last-slots $S_k^{54}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{54}$ with $|S_k^{54}| \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^{54}$ and $s'' \in S_{k'}^{54}$ with $E_k^{54} \cap E_{k'}^{54} \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^{54}} |\{s' \in S_k^{54}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{54}}, z^{S^{54}})$ is belong to $F$ and then to $F_{H,C}^{\tilde{G}_E^K}$ given that it is composed by $\sum_{v_{k,e} \in H} x_e^k + \frac{|H|-1}{2} \sum_{v_{k',e'} \in C} x_{e'}^{k'} = \frac{|H|-1}{2}$. We have so

$$ \mu x^{\tilde{S}^{52}} + \sigma z^{\tilde{S}^{52}} = \mu x^{S^{54}} + \sigma z^{S^{54}} = \mu x^{\tilde{S}^{52}} + \sigma z^{\tilde{S}^{52}} + \mu_{e'}^{k'} - \sum_{v_{k,e} \in H_{52}} \mu_e^k + \sum_{\tilde{k} \in \tilde{K}} \sum_{s' \in S_{\tilde{k}}^{54}} \sigma_{s'}^{\tilde{k}} - \sum_{s \in \tilde{S}_{\tilde{k}}^{52}} \sigma_s^{\tilde{k}} \\ + \sum_{e'' \in E_{k'}^{54} \setminus \{e'\}} \mu_{e''}^{k'} - \sum_{e'' \in \tilde{E}_{k'}^{52}} \mu_{e''}^{k'} + \sum_{e'' \in E_k^{54}} \mu_{e''}^{k'} - \sum_{k \in K(H_{52})} \sum_{e'' \in \tilde{E}_k^{52}} \mu_{e''}^{k'}. $$

It follows that $\mu_{e'}^{k'} = \sum_{v_{k,e} \in H_{52}} \mu_e^k$ for demand $k'$ and an edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$ with $v_{k',e'} \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 $v_{k,e''} \notin H \cup C$, and $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$. As a result, $\mu_{e'}^{k'} = \rho \frac{|H|-1}{2}$.

Given that the pair $v_{k',e'}$ is chosen arbitrary in the clique $C$, we iterate the same procedure for all pairs $v_{k',e'} \in C$ s.t. we find

$$ \mu_{e'}^{k'} = \rho \frac{|H| - 1}{2}, \text{ for all pairs } v_{k',e'} \in C. $$

As a result, all $\mu_{e'}^{k'} \in C$ are equivalents s.t.

$$ \mu_{e'}^{k'} = \mu_{e''}^{k''} = \rho \frac{|H| - 1}{2}, \text{ for all pairs } v_{k',e'}, v_{k'',e''} \in C $$

On the other hand, we ensure that all the edges $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, $$

On the other hand, 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\}. \quad (51) $$

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 } v_{k,e} \in H, \\ \rho \frac{|H| - 1}{2}, & \text{if } v_{k,e} \in C, \\ 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_{v_{k,e} \in H} \rho \alpha_e^k + \sum_{v_{k',e'} \in C} \rho \frac{|H| - 1}{2} \alpha_{e'}^{k'} + \gamma Q. $$

## 5.9 Edge-Interval-Cover Inequalities

**Theorem 15.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $j \ge i + 1$. Let $\tilde{K}$ be a subset of demands of $K$ s.t.

$$ - \sum_{k \in \tilde{K}} w_k \ge |I| + 1, $$

$$ - \sum_{k \in \tilde{K} \setminus \{k'\}} w_k \le |I| \text{ for each } k' \in \tilde{K}, $$

$$ - \sum_{k \in \tilde{K}} w_k \le \bar{s} - \sum_{k' \in K_e \setminus \tilde{K}} w_{k'}, $$

$$ - e \notin E_0^k \text{ for each demand } k \in \tilde{K}, $$

$$ - \tilde{K} \ge 3, $$

$$ - (k, k') \notin K_c^e \text{ for each pair of demands } (k, k') \text{ in } \tilde{K}. $$
Then, the inequality (20) is facet defining for the polytope $P(G, K, \mathcal{S}, \tilde{K}, I, e)$ iff there does not exist an interval of contiguous slots $I'$ in $[1, \bar{s}]$ with $I \subset I'$ s.t. $\tilde{K}$ defines a minimal cover for the interval $I'$, where

$$P(G, K, \mathcal{S}, \tilde{K}, I, e) = \{(x, z) \in P(G, K, \mathcal{S}) : \sum_{k' \in K_e \setminus \tilde{K}} \sum_{s' = s_i + w_{k'} - 1}^{s_j} z_{s'}^{k'} = 0\}.$$

### Proof. Necessity

If there exists an interval of contiguous slots $I'$ in $[1, \bar{s}]$ with $I \subset I'$ s.t. $\tilde{K}$ defines a minimal cover for the interval $I'$. This means that $\{s_i + w_k - 1, ..., s_j\} \subset I'$. As a result, the inequality (20) induced by the minimal cover $\tilde{K}$ for the interval $I$, it is dominated by another inequality (20) induced by the same minimal cover $\tilde{K}$ for the interval $I'$. Hence, the inequality (20) cannot be facet defining for the polytope $P(G, K, \mathcal{S}, \tilde{K}, I, e)$.

### Sufficiency.

Let $F_{\tilde{K}}^{\tilde{G}_I^e}$ denote the face induced by the inequality (20), which is given by

$$F_{\tilde{K}}^{\tilde{G}_I^e} = \{(x, z) \in P(G, K, \mathcal{S}, \tilde{K}, I, e) : \sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 2|\tilde{K}| - 1\}.$$

In order to prove that inequality $\sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le 2|\tilde{K}| - 1$ is facet defining for $P(G, K, \mathcal{S}, \tilde{K}, I, e)$, we start checking that $F_{\tilde{K}}^{\tilde{G}_I^e}$ is a proper face, and $F_{\tilde{K}}^{\tilde{G}_I^e} \ne P(G, K, \mathcal{S}, \tilde{K}, I, e)$.

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

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

- a set of last-slots $S_k^{55}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{55}$ with $|S_k^{55}| \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^{55}$ and $s' \in S_{k'}^{55}$ with $E_k^{55} \cap E_{k'}^{55} \ne \emptyset$ (non-overlapping constraint),

- and there is $|\tilde{K}| - 1$ demands from the minimal cover $\tilde{K}$ denoted by $\tilde{K}_{55}$ which are covered by the interval $I$ (i.e., if $k \in \tilde{K}_{55}$ means that the demand $k$ selects a slot $s$ as last-slot in the solution $S^{55}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{55}$ for each $k \in \tilde{K}_{55}$, and for each $s' \in S_{k'}^{55}$ for all $k' \in \tilde{K} \setminus \tilde{K}_{55}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $S^{55}$, i.e., $e \in E_k^{55}$ for each $k \in \tilde{K}$.

Obviously, $S^{55}$ 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^{55}}, z^{S^{55}})$ is belong to $P(G, K, \mathcal{S}, \tilde{K}, I, e)$ 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$. As a result, $F_{\tilde{K}}^{\tilde{G}_I^e}$ is not empty (i.e., $F_{\tilde{K}}^{\tilde{G}_I^e} \ne \emptyset$). Furthermore, given that $s \in \{s_i + w_k - 1, ..., s_j\}$ for each $k \in \tilde{K}$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $\tilde{K}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ for each $s \in S_k$ and each $k \in \tilde{K}$. This means that $F_{\tilde{K}}^{\tilde{G}_I^e} \ne P(G, K, \mathcal{S}, \tilde{K}, I, e)$.

We denote the inequality $\sum_{k \in \tilde{K}} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le 2|\tilde{K}| - 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, \mathcal{S}, \tilde{K}, I, e)$. Suppose that $F_{\tilde{K}}^{\tilde{G}_I^e} \subset F = \{(x, z) \in P(G, K, \mathcal{S}, \tilde{K}, I, 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_0^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, ..., \bar{s}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $k \in \tilde{K}$,

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

- 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 \tilde{K}$,

- and all $\mu_e^k$ are equivalents for the set of demands in $\tilde{K}$,

- and $\sigma_s^k$ and $\mu_e^k$ are equivalents for all $k \in \tilde{K}$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$.
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 \neq e'$ if $k \in \tilde{K}$. Consider a demand $k \in K$ and an edge $e' \in E \setminus (E_0^k \cup E_1^k)$ with $e \neq e'$ if $k \in \tilde{K}$. For that, we consider a solution $S'^{55} = (E'^{55}, S'^{55})$ in which

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

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

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k'^{55}$ and $s'' \in S_{k'}'^{55}$ with $E_k'^{55} \cap E_{k'}'^{55} \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'^{55}} |\{s' \in S_k'^{55}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint),

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

- and there is $|\tilde{K}| - 1$ demands from the minimal cover $\tilde{K}$ denoted by $\tilde{K}_55'$ which are covered by the interval $I$ (i.e., if $k \in \tilde{K}_55'$ means that the demand $k$ selects a slot $s$ as last-slot in the solution $S'^{55}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k'^{55}$ for each $k \in \tilde{K}_55'$, and for each $s' \in S_{k'}'^{55}$ for all $k' \in \tilde{K} \setminus \tilde{K}_55'$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $S'^{55}$, i.e., $e \in E_k'^{55}$ for each $k \in \tilde{K}$.

$S'^{55}$ 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'^{55}}, z^{S'^{55}})$ 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$. Based on this, we derive a solution $S^{56}$ obtained from the solution $S'^{55}$ 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^{55}$ which means that $E_k^{56} = E_k'^{55} \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^{55}$ remain the same in the solution $S^{56}$, i.e., $S_k^{56} = S_k'^{55}$ for each $k \in K$, and $E_k^{56} = E_k'^{55}$ for each $k' \in K \setminus \{k\}$. $S^{56}$ is clearly feasible given that

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

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

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k^{56}$ and $s'' \in S_{k'}^{56}$ with $E_k^{56} \cap E_{k'}^{56} \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^{56}} |\{s' \in S_k^{56}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{56}}, z^{S^{56}})$ 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$. It follows that

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

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 \neq e'$ if $k \in \tilde{K}$, we iterate the same procedure for all $e \in E \setminus (E_0^k \cup E_1^k \cup \{e'\})$ with $e \neq e''$ if $k \in \tilde{K}$. 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 \neq e' \text{ if } k \in \tilde{K}. $$

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 \neq e' \text{ if } k \in \tilde{K}. $$

Let's us show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $k \notin \tilde{K}$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $k \notin \tilde{K}$. For that, we consider a solution $S''^{55} = (E''^{55}, S''^{55})$ in which
- a feasible path $E_k^{55}$ is assigned to each demand $k \in K$ (routing constraint),

- a set of last-slots $S_k^{55}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{55}$ with $|S_k^{55}| \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^{55}$ and $s'' \in S_{k'}^{55}$ with $E_k^{55} \cap E_{k'}^{55} \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^{55}} |\{s' \in S_k^{55}, 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'}^{55}$ with $E_k^{55} \cap E_{k'}^{55} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{55}$ assigned to the demand $k$ in the solution $S^{55}$),

- and there is $|\tilde{K}| - 1$ demands from the minimal cover $\tilde{K}$ denoted by $\tilde{K}^{55}$ which are covered by the interval $I$ (i.e., if $k \in \tilde{K}^{55}$ means that the demand $k$ selects a slot $s$ as last-slot in the solution $S^{55}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{55}$ for each $k \in \tilde{K}^{55}$, and for each $s' \in S_{k'}^{55}$ for all $k' \in \tilde{K} \setminus \tilde{K}^{55}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $S^{55}$, i.e., $e' \in E_k^{55}$ for each $k \in \tilde{K}$.

$S^{55}$ 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^{55}}, z^{S^{55}})$ 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$. Based on this, we distinguish two cases:

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

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

* a set of last-slots $S_k^{57}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{57}$ with $|S_k^{57}| \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^{57}$ and $s'' \in S_{k'}^{57}$ with $E_k^{57} \cap E_{k'}^{57} \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^{57}} |\{s' \in S_k^{57}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{57}}, z^{S^{57}})$ 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^{55}} + \sigma z^{S^{55}} = \mu x^{S^{57}} + \sigma z^{S^{57}} = \mu x^{S^{55}} + \sigma z^{S^{55}} + \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 \tilde{K}$.

- with changing the paths established in $S^{55}$: we construct a solution $S'^{57}$ derived from the solution $S^{55}$ 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^{55}$ (i.e., $E_k^{57} = E_k^{55}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{57} \neq E_k^{55}$ for each $k \in \tilde{K}$) s.t.

* a new feasible path $E_k'^{57}$ 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^{55}$ and $s'' \in S_{k'}^{55}$ with $E_k'^{57} \cap E_{k'}^{57} \neq \emptyset$, i.e., for each edge $e' \in E$ and each slot $s'' \in \mathbb{S}$ we have $\sum_{k \in \tilde{K}, e' \in E_k'^{57}} |\{s' \in S_k^{55}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e' \in E_k^{55}} |\{s' \in S_k^{55}, 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^{55}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{55}$ assigned to the demand $k$ in the solution $S^{55}$).

The last-slots assigned to the demands $K \setminus \{k\}$ in $S^{55}$ remain the same in $S'^{57}$, i.e., $S_k^{55} = S_k'^{57}$ for each demand $k' \in K \setminus \{k\}$, and $S_k'^{57} = S_k^{55} \cup \{s\}$ for the demand $k$. The solution $S'^{57}$ is clearly feasible given that
• a feasible path $E_k'^{57}$ is assigned to each demand $k \in K$ (routing constraint),

• a set of last-slots $S_k'^{57}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{57}$ with $|S_k'^{57}| \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'^{57}$ and $s'' \in S_{k'}'^{57}$ with $E_k'^{57} \cap E_{k'}'^{57} \ne \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'^{57}} |\{s' \in S_k'^{57}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{57}}, z^{S^{57}})$ 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^{S^{55}} + \sigma z^{S^{55}} = \mu x^{S^{57}} + \sigma z^{S^{57}} = \mu x^{S^{55}} + \sigma z^{S^{55}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k''^{55}} \mu_{e'}^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e'' \in E_k'''^{57}} \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 \tilde{K}$ 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 \ne e'$ if $k \in \tilde{K}$.

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$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $k \notin \tilde{K}$ s.t. we find

$$\sigma_{s'}^k = 0, \text{ for demand } k \text{ and all slots } s' \in \{w_k, ..., \bar{s}\} \text{ with } s' \notin \{s_i + w_k - 1, ..., s_j\} \text{ if } k \notin \tilde{K}.$$

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}\} \text{ with } s \notin \{s_i + w_{k'} - 1, ..., s_j\} \text{ if } k' \notin \tilde{K}.$$

Consequently, we conclude that

$$\sigma_s^k = 0, \text{ for all } k \in K \text{ and all slots } s \in \{w_k, ..., \bar{s}\} \text{ with } s \notin \{s_i + w_k - 1, ..., s_j\} \text{ if } k \notin \tilde{K}.$$

Let prove that $\sigma_s^k$ for all $k \in \tilde{K}$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$ are equivalents. Consider a demand $k'$ and a slot $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$ with $k' \in \tilde{K}$. For that, we consider a solution $\tilde{S}^{55} = (\tilde{E}^{55}, \tilde{S}^{55})$ in which

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

– a set of last-slots $\tilde{S}_k^{55}$ is assigned to each demand $k \in K$ along each edge $e' \in \tilde{E}_k^{55}$ with $|\tilde{S}_k^{55}| \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^{55}$ and $s'' \in \tilde{S}_{k'}^{55}$ with $\tilde{E}_k^{55} \cap \tilde{E}_{k'}^{55} \ne \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^{55}} |\{s' \in \tilde{S}_k^{55}, 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 \tilde{S}_k^{55}$ with $\tilde{E}_k^{55} \cap \tilde{E}_{k'}^{55} \ne \emptyset$ (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 there is $|\tilde{K}| - 1$ demands from the minimal cover $\tilde{K}$ denoted by $\tilde{K}_{58'}$ which are covered by the interval $I$ (i.e., if $k \in \tilde{K}_{58'}$ means that the demand $k$ selects a slot $s$ as last-slot in the solution $\tilde{S}^{55}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in \tilde{S}_k^{55}$ for each $k \in \tilde{K}_{58'}$, and for each $s' \in \tilde{S}_{k'}^{55}$ for all $k' \in \tilde{K} \setminus \tilde{K}_{58'}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

– and all the demands in $\tilde{K}$ pass through the edge $e$ in the solution $\tilde{S}^{55}$, i.e., $e' \in \tilde{E}_k^{55}$ for each $k \in \tilde{K}$.

$\tilde{S}^{55}$ 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}^{55}}, z^{\tilde{S}^{55}})$ 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$. Based on this, we distinguish two cases: