# On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part I

Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub

<figure><img src="image_1.png" /></figure>

## To cite this version:

Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub. On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part I. 2021. hal-03287174

HAL Id: hal-03287174

https://uca.hal.science/hal-03287174

Preprint submitted on 15 Jul 2021

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On the Facial Structure of the Constrained-Routing and Spectrum Assignment Polyhedron: Part I *

Ibrahima Diarrassouba¹, Youssouf Hadhbi², and Ali Ridha Mahjoub³

¹ Le Havre Normandie University, LMAH, FR CNRS 3335, 76600 Le Havre, France
diarrasi@univ-lehavre.fr

² Clermont Auvergne University, LIMOS, UMR CNRS 6158, 63178 Clermont Ferrand, France
youssouf.hadhbi@uca.fr

³ Paris Dauphine-PSL University, LAMSADE, UMR CNRS 7243, 75775 Paris CEDEX 16, France
ridha.mahjoub@lamsade.dauphine.fr

**Abstract.** The constrained-routing and spectrum assignment (C-RSA) problem is a key issue when dimensioning and designing an optical network. Given an optical network $G$ and a multiset of traffic demand $K$, it aims at determining for each traffic demand $k \in K$ a path and an interval of contiguous slots while satisfying technological constraints and optimizing some linear objective function(s). In this paper, we first introduce an integer linear programming formulation for the C-RSA problem. We further investigate the facial structure of the associated polytope.

**Keywords:** Optical networks, constrained-routing, spectrum assignment, integer linear programming, polyhedron, dimension, valid inequality, facet.

## 1 Introduction

The global Internet Protocol (IP) traffic is expected to reach 396 exabytes per month by 2022, up from 194.4 Exabytes per month in 2020 [82]. Optical transport networks are then facing a serious challenge related to continuous growth in bandwidth capacity due to the growth of global communication services and networking: mobile internet network (e.g., 5th generation mobile network), cloud computing (e.g., data centers), Full High-definition (HD) interactive video (e.g., TV channel, social networks) [9], etc... To sustain the network operators face this trend of increase in bandwidth, a new generation of optical transport network architecture called Spectrally Flexible Optical Networks (SFONs) (called also FlexGrid Optical Networks) has been introduced as promising technology because of their flexibility, scalability, efficiency, reliability, survivability [7][9] compared with the traditional FixedGrid Optical Wavelength Division Multiplexing (WDM)[66][67]. In SFONs the optical spectrum is divided into small spectral units, called frequency slots as shown in Figure 1. They have the same frequency of 12.5 GHz where WDM uses 50 GHz as recommended by ITU-T [1]. This concept of slots was proposed firstly by Jinno et al. in 2008 [36], and later explored by the same authors in 2010 [85]. This can be seen as an improvement in resource utilization. We refer the

<figure><img src="image_3.png" /><figcaption>**Fig. 1.** Slot concept illustration in SFONs [75].</figcaption></figure>

reader to [42] for more information about the architectures, technologies, and control of SFONs.

<footnote>* This work was supported by the French National Research Agency grant ANR-17-CE25-0006, project FLEXOPTIM.</footnote>
The Routing and Spectrum Assignment (RSA) problem plays a primary role when dimensioning and designing of SFONs which is the main task for the development of this next generation of optical networks. It consists of assigning for each traffic demand, a physical optical path, and an interval of contiguous slots (called also channels) while optimizing some linear objective(s) and satisfying the following constraints [29]:

1. *spectrum contiguity*: an interval of contiguous slots should be allocated to each demand *k* with a width equal to the number of slots requested by demand *k*;

2. *spectrum continuity*: the interval of contiguous slots allocated to each traffic demand stills the same along the chosen path;

3. *non-overlapping spectrum*: the intervals of contiguous slots of demands whose paths are not edge-disjoints in the network cannot share any slot over the shared edges.

## 1.1 Related Works

The RSA is known to be an NP-hard problem [78] [81], and more complex than the historical Routing and Wavelength Assignment (RWA) problem [32]. Various integer linear programming (ILP) formulations and algorithms have been proposed to solve it. A detailed survey of spectrum management techniques for SFONs is presented in [81] where authors classified variants of the RSA problem: offline RSA which has been initiated in [61], and online or dynamic RSA which has been initiated in [86] and recently developed in [56] and [89], and an investigation of numerous aspects proposed in the tutorial [6]. This work focuses on the offline RSA problem. There exist two classes of ILP formulations used to solve the RSA problem, called edge-path and edge-node formulations. The ILP edge-path formulation is majorly used in the literature where variables are associated with all possible physical optical paths inducing an explosion of a number of variables and constraints which grow exponentially and in parallel with the growth of the instance size: number of demands, the total number of slots, and topology size: number of links and nodes [29]. To the best of our knowledge, we observe that several papers which use the edge-path formulation as an ILP formulation to solve the RSA problem, use a set of precomputed-paths without guaranty of optimality e.g. in [12], [61], [62], [84], [91], and recently in [73]. On the other hand, column generation techniques have been used by Klinkowski et al. in [71], Jaumard et al. in [34], and recently by Enoch in [19] to solve the relaxation of the RSA taking into account all the possible paths for each traffic demand. To improve the LP bounds of the RSA relaxation, Klinkowsky et al. proposed in [63] a valid inequality based on clique inequality separable using a branch-and-bound algorithm. On the other hand, Klinkowski et al. in [64] propose a branch-and-cut-and-price method based on an edge-path formulation for the RSA problem. Recently, Fayez et al. [21], and Xuan et al. [87], they proposed a decomposition approach to solve the RSA separately (i.e., R+SA) based on a recursive algorithm and an ILP edge-path formulation.

To overcome the drawbacks of the edge-path formulation usage, a compact edge-node formulation has been introduced as an alternative for it. It holds a polynomial number of variables and constraints that grow only polynomially with the size of the instance. We found just a few works in the literature that use the edge-node formulation to solve the RSA problem e.g. [4], [84], [91]. On the other front, and due to the NP-Hardness of the C-RSA problem, we found that several heuristics [16],[49],[75], and recently in [33], and greedy algorithms [44], and metaheuristics as tabu search in [25], simulated annealing in [64], genetic algorithms in [23], [31], [32], ant colony algorithms in [39], and a hybrid meta-heuristic approach in [70], have been used to solve large sized instances of the RSA problem. Furthermore, some resseraches start using some artificial intelligence algorithms, see for example [40] and [41], and some deep-learning algorithms [8], and also machine-learning algorithms in [74], and recently in [88] and [27] to get more perefermonce. Selvakumar et al. gives a survey in [77] in which they summarise the most contributions done for the RSA problem before 2019.

In this paper, we are interested in the resolution of a complex variant of the RSA problem, called the Constrained-Routing and Spectrum Assignment (C-RSA) problem. Here we suppose that the network should also satisfy the transmission-reach constraint for each traffic demand according to the actual service requirements. To the best of our knowledge a few related works on the RSA, to say the least, take into account this additional constraint such that the length of the chosen path for each traffic demand should not exceed a certain length (in kms). Recently, Hadhbi et al. in [29] and
[30] introduced a novel tractable ILP based on the cut formulation for the C-RSA problem with a polynomial number of variables and an exponential number of constraints separable in polynomial time using network flow algorithms. Computational results show that their cut formulation solves larger instances compared with those of Velasco et al. in [84] and Cai et al. [4]. It has been used also as a basic formulation in the study of Colares et al. in [15], and also by Chouman et al. in [10] and [11] to show the impact of several objective functions on the on optical network state. Bertero et al. in [3] give a comparative study between several edge-node formulations and introduce new ILP formulations adapted from the existing ILP formulations in the literature. Note that Velasco et al. in [84] and Cai et al. [4] did not take into account the transmission-reach constraint.

## 1.2 Our Contributions

However, so far the exact algorithms proposed in the literature could not solve large-sized instances. We believe that a cutting-plane-based approach could be powerful for the problem. To the best of our knowledge, such an approach has not been yet considered. For that, the main aim of our work is to investigate thoroughly the theoretical properties of the C-RSA problem. To this end, we aim to provide a deep polyhedral analysis of the C-RSA problem, and based on this, devise a branch-and-cut algorithm for solving the problem considering large-scale networks that are often used. In this Part I of our works, our contribution is to introduce a new ILP formulation for the C-RSA problem which can be seen as an improved formulation for the one introduced by Hadhbi et al. in [29] and [30]. We further investigate the facial structure of the associated polytope.

## 1.3 Organization

Following the introduction, the rest of this paper is organized as follows. In Section (2), we present the C-RSA problem (input and output). In Section (3), we provide the notation, then we introduce our ILP, called cut formulation based on the so-called cut inequalities. Furthermore, an intial polyhedral investigation is given in Section (4).

# 2 The Constrained-Routing and Spectrum Assignment Problem

The Constrained-Routing and Spectrum Assignment Problem can be stated as follows. We consider a spectrally flexible optical networks as an undirected, loopless, and connected graph $G = (V, E)$, which is specified by a set of nodes $V$, and a multiset $E$ of links (optical-fibers). Each link $e = ij \in E$ is associated with a length $l_e \in \mathbb{R}_+$ (in kms), a cost $c_e \in \mathbb{R}_+$ such that each fiber-link $e \in E$ is divided into $\bar{s} \in \mathbb{N}_+$ slots. Let $\mathcal{S} = \{1, \dots, \bar{s}\}$ be an optical spectrum of available frequency slots with $\bar{s} \le 320$ given that the maximum spectrum bandwidth of each fiber-link is 4000 GHz [35], and $K$ be a multiset of demands such that each demand $k \in K$ is specified by an origin node $o_k \in V$, a destination node $d_k \in V \setminus \{o_k\}$, a slot-width $w_k \in \mathbb{Z}_+$, and a transmission-reach $\ell_k \in \mathbb{R}_+$ (in kms). The C-RSA problem consists of determining for each demand $k \in K$, a $(o_k, d_k)$-path $p_k$ in $G$ such that $\sum_{e \in E(p_k)} l_e \le \bar{l}_k$, where $E(p_k)$ denotes the set of edges belong the path $p_k$, and a subset of contiguous frequency slots $S_k \subset \mathcal{S}$ of width equal to $w_k$ such that $S_k \cap S_{k'} = \emptyset$ for each pair of demands $k, k' \in K$ ($k \ne k'$) with $E(p_k) \cap E(p_{k'}) \ne \emptyset$ so the total length of the paths used for routing the demands (i.e., $\sum_{k \in K} \sum_{e \in E(p_k)} l_e$) is minimized.
Figure 2 shows the set of established paths and spectrums for the set of demands $\{k_1, k_2, k_3, k_4\}$ (Fig. 2(c) and Table 2(d)) of Table 2(b) in a graph $G$ of 7 nodes and 10 edges (Fig. 2(a)) s.t. each edge $e$ is characterized by a triplet $[l_e, c_e, \bar{s}]$, and optical spectrum $\mathcal{S} = \{1, 2, 3, \dots, 8, 9\}$ with $\bar{s} = 9$.

<footnote n="4">⁴ We take into account the presence of parallel fibers such that two edges $e, e'$ which have the same extremities $i$ and $j$ are independents.</footnote>

<footnote n="5">⁵ We take into account that we can have several demands between the same origin-node and destination-node.</footnote>
<figure><img src="image_4.png" /><figcaption>**Fig. 2.** Set of established paths and spectrums in graph G (Fig. 2(a)) for the set of demands {$k_1, k_2, k_3, k_4$} defined in Table 2(b).</figcaption></figure>

## 3 The C-RSA Integer Linear Programming Formulation

Let's us introduce some notations which will be useful throughout this paper to formulate some constraints. For any subset of nodes $X \subseteq V$ with $X \neq \emptyset$, let $\delta(X)$ denote the set of edges having one extremity in $X$ and the other one in $\bar{X} = V \setminus X$ which is called a cut. When $X$ is a singleton (i.e., $X = \{v\}$), we use $\delta(v)$ instead of $\delta(\{v\})$ to denote the set of edges incidents with a node $v \in V$. The cardinality of a set $K$ is denoted by $|K|$.

Here we introduce our integer linear programming formulation based on cut formulation for the C-RSA problem which can be seen as a reformulation of the one introduced by Hadhbi et al. in [29]. For $k \in K$ and $e \in E$, let $x_e^k$ be a variable which takes 1 if demand $k$ goes through the edge $e$ and 0 if not, and for $k \in K$ and $s \in S$, let $z_s^k$ be a variable which takes 1 if slot $s$ is the last-slot allocated for the routing of demand $k$ and 0 if not. The contiguous slots $s' \in \{s - w_k + 1, ..., s\}$ should be assigned to demand $k$ whenever $z_s^k = 1$.

Before introducing our ILP, we proceeded to some pre-processing techniques to determine some zero-one variables s.t. we are able to determine them in polynomial time using shortest-path and network flows algorithms as follows.

For each demand $k$ and each node $v$, one can compute a shortest path between each of the pair of nodes $(o_k, v)$, $(v, d_k)$. If the lengths of the $(o_k, d_k)$-paths formed by the shortest paths $(o_k, v)$ and $(v, d_k)$ are both greater than $\bar{l}_k$ then node $v$ cannot be in a path routing demand $k$, and we then say that $v$ is a *forbidden node* for demand $k$ due to the transmission-reach constraint. Let $V_0^k$ denote the set of forbidden nodes for demand $k \in K$. Note that using Dijkstra's algorithm, one can identify in polynomial time the forbidden nodes $V_0^k$ for each demand $k \in K$. On the other hand and regarding the edges, for each demand $k$ and each edge $e = ij$, one can compute a shortest path between each of the pair of nodes $(o_k, i)$, $(j, d_k)$, $(o_k, j)$ and $(i, d_k)$. If the lengths of the $(o_k, d_k)$-paths formed by $e$ together with the shortest $(o_k, i)$ and $(j, d_k)$ (resp. $(o_k, j)$ and $(i, d_k)$) paths are both greater than $\bar{l}_k$ then edge $ij$ cannot be in a path routing demand $k$, and we then say that $ij$ is a *forbidden edge* for demand $k$ due to the transmission-reach constraint. Let $E_t^k$ denote the set of forbidden edges due to the transmission-reach constraint for demand $k \in K$. Note that using Dijkstra's algorithm, one can identify in polynomial time the forbidden edges $E_t^k$ for each demand $k \in K$. This allows us to create in polynomial time a proper topology $G_k$ for each demand $k$ by deleting the forbidden nodes $V_0^k$ and forbidden edges $E_t^k$ from the original graph $G$ (i.e., $G_k = G(V \setminus V_0^k, E \setminus E_t^k)$). As a result, there may exist some forbidden-nodes due to the
elementary-path constraint which means that all the $(o_k, d_k)$-paths passed through a node $v$ are not elementary-paths. This can be done in polynomial time using Breadth First Search (BFS) algorithm of complexity $O(|E \setminus E_0^k| + |V \setminus V_0^k|)$ for each demand $k$. Note that we did not take into account this case in our study. Table 1 below shows the set of forbidden edges $E_0^k$ and forbidden nodes $V_0^k$ for each demand $k$ in $K$ already given in Fig. 2(b).

<table><caption>**Table 1.** Topology pre-processing for the set of demands $K$ given in Fig. 2(b).</caption><thead><tr><th>k</th><th>o<sub>k</sub> → d<sub>k</sub></th><th>w<sub>k</sub></th><th>l&#773;<sub>k</sub></th><th>V<sub>0</sub><sup>k</sup></th><th>E<sub>0</sub><sup>k</sup></th></tr></thead><tbody><tr><td>1</td><td>a → c</td><td>2</td><td>4</td><td>{e, d, g}</td><td>{cg, dg, de, df, cd, ef}</td></tr><tr><td>2</td><td>a → d</td><td>1</td><td>4</td><td>{g}</td><td>{cg, dg, df}</td></tr><tr><td>3</td><td>b → f</td><td>2</td><td>4</td><td>{e, d, g}</td><td>{cg, dg, de, df, cd, ef}</td></tr><tr><td>4</td><td>b → e</td><td>1</td><td>4</td><td>{g}</td><td>{cg, dg, df}</td></tr></tbody></table>

Let $\delta_{G_k}(v)$ denote the set of edges incident with a node $v$ for the demand $k$ in $G_k$. Let $\delta^k(W)$ denote a cut for demand $k \in K$ in $G_k$ s.t. $o_k \in W$ and $d_k \in V \setminus W$ where $W$ is a subset of nodes in $V$ of $G_k$. Let $f$ be an edge in $\delta(W)$ s.t. all the edges $e \in \delta(W) \setminus \{f\}$ are forbidden for demand $k$. As a consequence, edge $f$ is an essential edge for demand $k$. As the forbidden edges, the essential edges can be determined in polynomial time using network flows as follows.

1. we create a proper topology $G_k = G(V \setminus V_0^k, E \setminus E_t^k)$ for the demand $k$

2. we fix a weight equals to 1 for all the edges $e$ in $E \setminus E_t^k$ for the demand $k$ in $G_k$

3. we calculate $o_k - d_k$ min-cut which separates $o_k$ from $d_k$.

4. if $\delta_{G_k}(W) = \{e\}$ then the edge $e$ is an essential edge for the demand $k$ s.t. $o_k \in W$ and $d_k \in V \setminus W$. We increase the weight of the edge $e$ by 1. Go to (3).

5. if $|\delta_{G_k}(W)| > 1$ then end of algorithm.

Let $E_1^k$ denote the set of essential edges of demand $k$, and $K_e$ denote a subset of demands in $K$ s.t. edge $e$ is an essential edge for each demand $k \in K_e$.

In addition to the forbidden edges thus obtained due to the transmission-reach constraints, there may exist edges that may be forbidden because of lack of resources for demand $k$. This is the case when, for instance, the residual capacity of the edge in question does not allow a demand to use this edge for its routing, i.e., $w_k > \bar{s} - \sum_{k' \in K_e} w_{k'}$. Let $E_c^k$ denote the set of forbidden edges for demand $k$, $k \in K$, due to the resource constraints. Note that the forbidden edges $E_c^k$ and forbidden nodes $v$ in $V$ with $\delta(v) \subseteq E_t^k$, should also be deleted from the proper graph $G_k$ of demand $k$, which means that $G_k$ contains $|E| \setminus |E_t^k|$ edges and $|V| \setminus \{|v \in V, \delta(v) \subseteq E_t^k|}$ nodes. Let $E_0^k = E_t^k$ denote the set of all forbidden edges for demand $k$ that can be determined due to the transmission reach and resources constraints.

As a result of the pre-processing stage, some non-compatibility between demands may appear due to a lack of resources as follows.

**Definition 1.** For an edge $e$, two demands $k$ and $k'$ with $e = ij \notin E_0^k \cup E_1^k \cup E_0^{k'} \cup E_1^{k'}$, are said non-compatible demands because of lack of resources over the edge $e$ if and only if the residual capacity of the edge $e$ does not allow to route the two demands $k, k'$ together through $e$, i.e., $w_k + w_{k'} > \bar{s} - \sum_{k'' \in K_e} w_{k''}$.

Let $K_e^c$ denote the set of pair of demands $(k, k')$ in $K$ that are non-compatibles for the edge $e$. The C-RSA problem can hence be formulated as follows.

$$ \min \sum_{k \in K} \sum_{e \in E} l_e x_e^k, \qquad (1) $$
subject to

$$ \sum_{e \in \delta(X)} x_e^k \geq 1, \forall k \in K, \forall X \subseteq V \text{ s.t. } |X \cap \{o_k, d_k\}| = 1, \quad (2) $$

$$ \sum_{e \in E} l_e x_e^k \leq \bar{l}_k, \forall k \in K, \quad (3) $$

$$ x_e^k = 0, \forall k \in K, \forall e \in E_0^k, \quad (4) $$

$$ x_e^k = 1, \forall k \in K, \forall e \in E_1^k, \quad (5) $$

$$ z_s^k = 0, \forall k \in K, \forall s \in \{1, \dots, w_k - 1\}, \quad (6) $$

$$ \sum_{s=w_k}^{\bar{s}} z_s^k \geq 1, \forall k \in K, \quad (7) $$

$$ x_e^k + x_e^{k'} + \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k + \sum_{s'=s}^{\min(s+w_{k'}-1, \bar{s})} z_{s'}^{k'} \leq 3, \forall (e, k, k', s) \in Q, \quad (8) $$

$$ 0 \leq x_e^k \leq 1, \forall k \in K, \forall e \in E, \quad (9) $$

$$ z_s^k \geq 0, \forall k \in K, \forall s \in \mathbb{S}, \quad (10) $$

$$ x_e^k \in \{0, 1\}, \forall k \in K, \forall e \in E, \quad (11) $$

$$ z_s^k \in \{0, 1\}, \forall k \in K, \forall s \in \mathbb{S}. \quad (12) $$

where $Q$ denotes the set of all the quadruples $(e, k, k', s)$ for all $e \in E, k \in K, k' \in K$, and $s \in \mathbb{S}$ with $(k, k') \notin K_c^e$.

Inequalities (2) ensure that there is an $(o_k, d_k)$-path between $o_k$ and $d_k$ for each demand $k$, and guarantee that all the demands should be routed. They are called cut inequalities. By optimizing the objective function (1), and given that the capacities of all edges are strictly positives, this ensures that there is exactly one $(o_k, d_k)$-path between $o_k$ and $d_k$ which will be selected as optimal path for each demand $k$. We suppose that we have sufficient capacity in the network so that all the demands can be routed. This means that we have at least one feasible solution for the problem. Inequalities (3) express the length limit on the routing paths which is called "the transmission-reach constraint". Equations (4) ensure that the variables associated to the forbidden edges for demand $k$ are always equal to 0, and those of the essential edges are always equal to 1 for demand $k$. Equations (6) express the fact that a demand $k$ cannot use slot $s \leq w_k - 1$ as the last-slot. The slots $s \in \{1, ..., w_k - 1\}$ are called forbidden last-slots for demand $k$. Inequalities (7) should normally be an equation form ensuring that exactly one slot $s \in \{w_k, ..., \bar{s}\}$ must be assigned to demand $k$ as last-slot. Here we relax this constraint. By a choice of the objective function, the equality is guaranteed at the optimum (e.g. $\min \sum_{k \in K} \sum_{s=w_k}^{\bar{s}} s \cdot z_s^k$ or $\min \sum_{k \in K} \sum_{s=w_k}^{\bar{s}} s \cdot w_k \cdot z_s^k$). Inequalities (8) express the contiguity and non-overlapping constraints. Inequalities (9)-(10) are the trivial inequalities, and constraints (11)-(12) are the integrality constraints.

Note that the linear relaxation of the C-RSA can be solved in polynomial time given that inequalities (2) can be separated in polynomial time using network flows, see e.g. preflow algorithm of Goldberg and Tarjan introduced in [24] which can be run in $O(|V \setminus V_0^k|^3)$ time for each demand $k \in K$.

**Proposition 1.** *The formulation (2)-(12) is valid for the C-RSA problem.*

*Proof.* It is trivial given the definition of each constraint of the formulation (2)-(12) such that any feasible solution for this formulation is necessary a feasible solution for the C-RSA problem.

Let $P(G, K, \mathbb{S})$ be the polytope, convex hull of the solutions for the cut formulation (2)-(12).

# 4 Polyhedral Analysis

In this section we discuss the facial structure of the C-RSA.
## 4.1 Polyhedron $P(G, K, \mathbb{S})$ Dimension

In what follows, we describe some structural properties. These will be used for determining the dimension of $P(G, K, \mathbb{S})$.

**Proposition 2.** *The follows equation system (13) is of full rank*

$$ \left\{ \begin{array}{l} x_e^k = 0, \text{ for all } k \in K \text{ and } e \in E_0^k, \\ x_e^k = 1, \text{ for all } k \in K \text{ and } e \in E_1^k, \\ z_s^k = 0, \text{ for all } k \in K \text{ and } s \in \{1, \dots, w_k - 1\}. \end{array} \right. \qquad (13) $$

The rank of system (13) is given by

$$ r = \sum_{k \in K} (|E_0^k| + |E_1^k| + (w_k - 1)). $$

Let $Q$ denote a matrix associated with the system (13) which contains $r$ lines linear independents. We distinguish 4 blocks of lines in $Q$ as below

- block $Q^1$ corresponds to the equations $x_e^k = 0$ for all $k \in K$ and all $e \in E_0^k$,

- block $Q^2$ corresponds to the equations $x_e^k = 1$ for all $k \in K$ and all $e \in E_1^k$,

- block $Q^3$ corresponds to the equations $z_s^k = 0$ for all $k \in K$ and all $s \in \{1, \dots, w_k - 1\}$.

Note that the 4 blocks of the matrix $Q$ are independents.

A solution of the C-RSA problem is given by two sets $E_k$ and $S_k$ for each demand $k \in K$ where $E_k$ is a set of edges used for the routing of demand $k$ which contains a path $p_k$ satisfying the continuity of $(o_k, d_k)$-path $p_k$ for the demand $k$ (i.e., $E(p_k) \subseteq E_k$) such that $\sum_{e \in E_k} l_e \le \bar{l}_k$ and $E_1^k \subseteq E_k$, and $S_k$ is a set of slots which represent the set of last-slot selected for the demand $k$ which forms a set of channels such that each channel contains $w_k$ contiguous slots.

Figure 3 shows the routing solutions for a demand $k$ that are feasible for our problem throughout our proofs.

<figure><img src="image_5.png" /><figcaption>**Fig. 3.** A set of edges $E_k$ for a demand $k$ containing an $(o_k, d_k)$-path $P_k$ together with: isolated-edge, isolated-cycle, two isolated-edges, and linked-cycle.</figcaption></figure>

**Proposition 3.** *Consider an equation $\mu x + \sigma z = \lambda$ of $P(G, K, \mathbb{S})$. The C-RSA equation system (13) defines a minimal equation system for $P(G, K, \mathbb{S})$. As a consequence, we obtain that for each demand $k$*

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

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

- $\mu_e^k = 0$ for all $e \in E \setminus (E_0^k \cup E_1^k)$,

and $\mu x + \sigma z = \lambda$ of $P(G, K, \mathbb{S})$ is a linear combination of equation system (13).
Proof. To prove that $\mu x + \sigma z$ is a linear combination of equations system (13), it is sufficient to prove that for each demand $k \in K$, there exists $\gamma_1^k \in \mathbb{R}^{|E_0^k|}, \gamma_2^k \in \mathbb{R}^{|E_1^k|}, \gamma_3^k \in \mathbb{R}^{w_k-1}$ (given that the matrix $Q$ has 3 blocks) s.t. $(\mu, \sigma) = \gamma Q$.

Let $x^S$ and $z^S$ denote the incidence vector of a solution $S$ of the C-RSA problem.

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

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

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

$S^0$ 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, z^S)$ belongs to $P(G, K, S)$. Based on this, we derive a solution $S^1 = (E^1, S^1)$ from the solution $S^0$ by adding the slot $s$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S^0$ (i.e., $E_k^1 = E_1^0$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S^0$ remain the same in the solution $S^1$ i.e., $S_{k'}^0 = S_k^1$ for each demand $k' \in K \setminus \{k\}$, and $S_k^1 = S_k^0 \cup \{s\}$ for the demand $k$. The solution $S^1$ is feasible given that

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

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

The corresponding incidence vector $(x^S, z^S)$ belongs to $P(G, K, S)$. We then obtain that

$$ \mu x^S + \sigma z^S = \mu x^S + \sigma z^S = \mu x^S + \sigma z^S + \sigma_s^k. $$

It follows that $\sigma_s^k = 0$ for demand $k$ and a slot $s \in \{w_k, ..., \bar{s}\}$. The slot $s$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ s.t. we find

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

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

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

Consequently, we conclude that

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

Next we will show that $\mu_e^k = 0$ for all the demands $k \in K$ and all $e \in E \setminus (E_0^k \cup E_1^k)$. 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'^0 = (E'^0, S'^0)$ in which

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

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

- $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$ for each $k' \in K$ and $s \in S_k'^0$ and $s' \in S_{k'}'^0$ with $(E_k'^0 \cup \{e\}) \cap E_{k'}'^0 \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the edge $e$ in the set of edges $E_k'^0$ selected to route the demand $k$ in the solution $S'^0$),

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

$S'^0$ 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'^0}, z^{S'^0})$ belongs to $P(G, K, \mathbb{S})$. Based on this, we distinguish two cases:

- without changing the spectrum assignment established in $S'^0$: we derive a solution $S^2$ obtained from the solution $S'^0$ 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'^0$ which means that $E_k^2 = E_k'^0 \cup \{e\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S'^0$ remain the same in the solution $S^2$, i.e., $S_k^2 = S_k'^0$ for each $k \in K$, and $E_{k'}^2 = E_{k'}'^0$ for each $k' \in K \setminus \{k\}$. $S^2$ is clearly feasible given that

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

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

* and $\sum_{e' \in E_k'^2 \setminus \{e\}} l_{e'} + l_e \le \bar{l}_k$.

The corresponding incidence vector $(x^{S^2}, z^{S^2})$ is belong to $P(G, K, \mathbb{S})$. It follows that

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

As a result, $\mu_e^k = 0$ for demand $k$ and an edge $e$.

- with changing the spectrum assignment established in $S'^0$: let $S'^2$ be a solution obtained from the solution $S'^0$ 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'^0$ which means that $E_k'^2 = E_k'^0 \cup \{e\}$, and removing slot $s$ selected for the demand $k$ in $S'^0$ and replaced it by a new slot $s' \in \{w_k, ..., \mathbb{S}\}$ (i.e., $S_k'^2 = (S_k'^0 \setminus \{s'\}) \cup \{s'\}$ s.t. $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k' \in K$ and $s'' \in S_{k'}'^0$ with $E_k'^2 \cap E_{k'}'^0 \neq \emptyset$. The last-slots and paths assigned the set of demands $K \setminus \{k\}$ in $S'^0$ remain the same in the solution $S'^2$, i.e., $S_{k'}'^2 = S_{k'}'^0$ and $E_{k'}'^2 = E_{k'}'^0$ for each $k' \in K \setminus \{k\}$. $S'^2$ is clearly feasible given that

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

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

The corresponding incidence vector $(x^{S'^2}, z^{S'^2})$ is belong to $P(G, K, \mathbb{S})$. It follows that

$$ \mu x^{S'^0} + \sigma z^{S'^0} = \mu x^{S'^2} + \sigma z^{S'^2} = \mu x^{S'^0} + \mu_e^k + \sigma z^{S'^0} - \sigma_s^k + \sigma_{s'}^k $$

which gives that $\mu_e^k = 0$ for demand $k$ and an edge $e$ given that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$.

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

Therefore all the equations of the polytope $P(G, K, \mathbb{S})$ are given only in terms of the variables $x_e^k$ with $e \in E_0^k \cup E_1^k$ and $z_s^k$ with $s \in \{1, ..., w_k\}$. Let $Q^k = \begin{pmatrix} Q_1^k \\ Q_2^k \\ Q_3^k \end{pmatrix}$ be the submatrix of matrix $Q$ associated to the equations (4) and (5) and involving variables $x_e^k$ for all $e \in E_0^k \cup E_1^k$ and variables $z_s^k$ with $s \in \{1, ..., w_k\}$ for demand $k$. Note that a forbidden edge can never be an essential edge at the same time. Otherwise, the problem is infeasible. We want to show that $\mu^k = \gamma_1^k Q_1^k + \gamma_2^k Q_2^k$ and $\sigma^k = \gamma_3^k Q_3^k$. For that, we first 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, note that 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 (14) $$

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 \\ 0, & \text{otherwise} \end{cases} $$

yielding

$$ \mu^k = \gamma_1^k Q_k^1 + \gamma_2^k Q_k^2 \text{ for each } k \in K. $$

Moreover, 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} $$

i.e., $\sigma^k = \gamma_3^k Q_k^3$.

As a result $(\mu, \sigma) = \gamma Q$ with $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ which ends our proof.
**Theorem 1.** The dimension of $P(G, K, \mathbb{S})$ is given by

$$dim(P(G, K, \mathbb{S})) = |K| * (|E| + |\mathbb{S}|) - r.$$

*Proof.* Given the rank of the C-RSA equation system (13) and the proposition (3).

## 4.2 Facets

In this section, we investigate the facial structure of our polytope $P(G, K, \mathbb{S})$ by characterizing when the basic inequalities (2)-(12) of our cut formulation are facets defining for $P(G, K, \mathbb{S})$.

**Theorem 2.** Consider a demand $k \in K$, and an edge $e \in E \setminus (E_0^k, E_1^k)$. Then, the inequality $x_e^k \ge 0$ is facet defining for $P(G, K, \mathbb{S})$.

*Proof.* Let's us denote $F_e^k$ the face induced by the inequality $x_e^k \ge 0$, which is given by

$$F_e^k = \{(x, z) \in P(G, K, \mathbb{S}) : x_e^k = 0\}.$$

In order to prove that the inequality $x_e^k \ge 0$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_e^k$ is a proper face which means that it is not empty, and $F_e^k \ne P(G, K, \mathbb{S})$. We construct a solution $\mathcal{S}^3 = (E^3, S^3)$ as below

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

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

- and the edge $e$ is not chosen to route the demand $k$ in the solution $\mathcal{S}^3$, i.e., $e \notin E_k^3$.

Obviously, $\mathcal{S}^3$ is feasible solution for the problem given that it satisfies all the constraints of our cut formulation (2)-(12). Moreover, the corresponding incidence vector $(x^{\mathcal{S}^3}, z^{\mathcal{S}^3})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_e^k$ given that it is composed by $x_e^k = 0$. As a result, $F_e^k$ is not empty ($F_e^k \ne \emptyset$). Furthermore, given that $e \in E \setminus (E_0^k \cup E_1^k)$ for the demand $k$, this means that there exists at least one feasible path $E_k$ for the demand $k$ passed through the edge $e$ which means that $F_e^k \ne P(G, K, \mathbb{S})$.

On another hand, we know that all the solutions of $F_e^k$ are in $P(G, K, \mathbb{S})$ which means that they verify the equations system (13) s.t. the new equations system (15) associated with $F_e^k$ is written as below

$$ \left\{ \begin{array}{l} x_e^k = 0, \text{ s.t. } k \text{ and } e \text{ are chosen arbitrarily} \\ x_e^k = 0, \text{ for all } k \in K \text{ and all } e \in E_0^k \\ x_e^k = 1, \text{ for all } k \in K \text{ and all } e \in E_1^k \\ z_s^k = 0, \text{ for all } k \in K \text{ and all } s \in \{1, ..., w_k - 1\}. \end{array} \right. \qquad (15) $$

Given that the $e \in E \setminus (E_0^k \cup E_1^k)$, the system (15) shows that the equation $x_e^k = 0$ is not a result of equations of system (13) which means that the equation $x_e^k = 0$ is not redundant in the system (15). As a result, the system is of full rank. As a result, the dimension of the face $F_e^k$ is equal to

$$dim(F_e^k) = |K| * (|E| + |\mathbb{S}|) - rank(Q') = |K| * (|E| + |\mathbb{S}|) - (1 + r) = dim(P(G, K, \mathbb{S})) - 1,$$

where $Q'$ is the matrix associated with the equation system (15). As a result, the face $F_e^k$ is facet defining for $P(G, K, \mathbb{S})$. Furthermore, we strengthened our proof as follows using a technique called "proof by maximality". We denote the inequality $x_e^k \ge 0$ 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_e^k \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$ with $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (with $\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$. We will show that
- $\mu_{e'}^k = 0$ for the demand $k$ and all $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$,

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

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

First, let's show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$. Consider a demand $k$ and a slot $s$ in $\{w_k, ..., \bar{s}\}$. Based on this, we consider a solution $S'^3 = (E'^3, S'^3)$ in which

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

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

- and the edge $e$ is not chosen to route the demand $k$ in the solution $S'^3$, i.e., $e \notin E_k'^3$.

$S'^3$ 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'^3}, z^{S'^3})$ is belong to $F$ and then to $F_e^k$ given that it is also composed by $x_e^k = 0$. Based on this, we derive a solution $S^4 = (E^4, S^4)$ from the solution $S'^3$ by adding the slot $s$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S'^3$ (i.e., $E_k^4 = E_1^4$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S'^3$ remain the same in the solution $S^4$ i.e., $S_{k'}^4 = S_k^4$ for each demand $k' \in K \setminus \{k\}$, and $S_k^4 = S_{k'}^4 \cup \{s\}$ for the demand $k$. The solution $S^4$ is feasible given that

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

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

- and the edge $e$ is not chosen to route the demand $k$ in the solution $S^4$, i.e., $e \notin E_k^4$.

The corresponding incidence vector $(x^{S^4}, z^{S^4})$ is belong to $F$ and then to $F_e^k$ given that it is also composed by $x_e^k = 0$. We then obtain that

$$\mu x^{S'^3} + \sigma z^{S'^3} = \mu x^{S^4} + \sigma z^{S^4} = \mu x^{S'^3} + \sigma z^{S'^3} + \sigma_s^k.$$

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

The slot $s$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ s.t. we find

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

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

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

Consequently, we conclude that

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

Next, we will show that $\mu_{e'}^k = 0$ for all the demands $k' \in K \setminus \{k\}$ and all $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$, and $\mu_{e'}^k = 0$ for the demand $k$ and all $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$. Consider the demand $k \in K$ and an edge $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$ chosen arbitrarily. For that, we consider a solution $S''^3 = (E''^3, S''^3)$ in which
- a feasible path $E_k''^3$ is assigned to each demand $k \in K$ (routing constraint),

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

- and the edge $e$ is not chosen to route the demand $k$ in the solution $S''^3$, i.e., $e \notin E_k''^3$.

$S''^3$ 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''^3}, z^{S''^3})$ is belong to $F$ and then to $F_e^k$ given that it is also composed by $x_e^k = 0$. Based on this, we distinguish two cases:

- without changing the spectrum assignment established in $S''^3$: we derive a solution $S^5$ obtained from the solution $S''^3$ 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^3$ which means that $E_k''^5 = E_k''^3 \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S''^3$ remain the same in the solution $S^5$, i.e., $S_k''^5 = S_k''^3$ for each $k \in K$, and $E_{k'}''^5 = E_{k'}''^3$ for each $k' \in K \setminus \{k\}$. $S^5$ is clearly feasible given that

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

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

* and the edge $e$ is not chosen to route the demand $k$ in the solution $S^5$, i.e., $e \notin E_k''^5$.

The corresponding incidence vector $(x^{S^5}, z^{S^5})$ is belong to $F$ and then to $F_e^k$ given that it is also composed by $x_e^k = 0$. It follows that

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

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

- with changing the spectrum assignment established in $S''^3$: let $S^5$ be a solution obtained from the solution $S''^3$ 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''^3$ which means that $E_k''^5 = E_k''^3 \cup \{e'\}$, and removing slot $s$ selected for the demand $k$ in $S''^3$ and replaced it by a new slot $s' \in \{w_k, ..., \mathbb{S}\}$ (i.e., $S_k''^5 = (S_k''^3 \setminus \{s'\}) \cup \{s'\}$ s.t. $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k' \in K$ and $s'' \in S_{k'}''^3$ with $E_k''^5 \cap E_{k'}''^5 \ne \emptyset$. The last-slots and paths assigned the set of demands $K \setminus \{k\}$ in $S''^3$ remain the same in the solution $S''^5$, i.e., $S_k''^5 = S_k''^3$ and $E_{k'}''^5 = E_{k'}''^3$ for each $k' \in K \setminus \{k\}$. $S''^5$ is clearly feasible given that

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

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

* and the edge $e$ is not chosen to route the demand $k$ in the solution $S''^5$, i.e., $e \notin E_k''^5$.

The corresponding incidence vector $(x^{S''^5}, z^{S''^5})$ is belong to $F$ and then to $F_e^k$ given that it is also composed by $x_e^k = 0$. It follows that

$$ \mu x^{S''^3} + \sigma z^{S''^3} = \mu x^{S''^5} + \sigma z^{S''^5} = \mu x^{S''^3} + \mu_{e'}^k + \sigma z^{S''^3} - \sigma_s^k + \sigma_{s'}^k $$

which gives that $\mu_{e'}^k = 0$ for demand $k$ and an edge $e'$ given that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$.
As $e'$ is chosen arbitrarily for the demand $k$ with $e' \notin E_0^k \cup E_1^k \cup \{e\}$, we iterate the same procedure for all $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$. 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 \cup \{e\}). $$

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 \setminus \{k\} \text{ and all } e' \in E \setminus (E_0^{k'} \cup E_1^{k'}), $$

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

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 (16) $$

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' = k \text{ and } e' = e, \\ 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) = \rho\alpha_e^k + \gamma Q$ which ends our proof.
**Theorem 3.** Consider a demand $k \in K$, and a slot $s \in \{w_k, ..., \bar{s}\}$. Then, the inequality $z_s^k \ge 0$ is facet defining for $P(G, K, \mathbb{S})$.

*Proof.* Let $F_s^k$ denote the face induced by inequality $z_s^k \ge 0$, which is given by

$$F_s^k = \{(x, z) \in P(G, K, \mathbb{S}) : z_s^k = 0\}.$$

In order to prove that inequality $z_s^k \ge 0$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_s^k$ is a proper face, and $F_s^k \ne P(G, K, \mathbb{S})$. We construct a solution $S^6 = (E^6, S^6)$ as below

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

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

- and the slot $s$ is not chosen to route the demand $k$ in the solution $S^6$, i.e., $s \notin S_k^6$.

Obviously, $S^6$ is 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^6}, z^{S^6})$ is belong to $F$ and then to $F_s^k$ given that it is composed by $z_s^k = 0$. As a result, $F_s^k$ is not empty ($F_s^k \ne \emptyset$). Furthermore, given that $s \in \{w_k, ..., \bar{s}\}$ for the demand $k$, this means that there exists at least one feasible solution for the problem in which $s \in S_k$ for the demand $k$. As a result, $F_s^k \ne P(G, K, \mathbb{S})$. On another hand, we know that all the solutions of $F_s^k$ are in $P(G, K, \mathbb{S})$ which means that they verify the equations system (13) s.t. the new equations system (17) associated with $F_s^k$ is written as below

$$\left\{
\begin{array}{l}
z_s^k = 0, \text{ s.t. } k \text{ and } s \text{ are chosen arbitrarily} \\
x_e^k = 0, \text{ for all } k \in K \text{ and all } e \in E_0^k \\
x_e^k = 1, \text{ for all } k \in K \text{ and all } e \in E_1^k \\
z_s^k = 0, \text{ for all } k \in K \text{ and all } s \in \{1, ..., w_k - 1\}.
\end{array}
\right.
\qquad (17)$$

The equation $z_s^k = 0$ is not result of equations of system (13) which means that the equation $z_s^k = 0$ is not redundant in the system (17). As a result, the system (17) is of full rank. As a result, the dimension of the face $F_s^k$ is equal to

$$\dim(F_s^k) = |K| * (|E| + |\mathbb{S}|) - \mathrm{rank}(Q) = |K| * (|E| + |\mathbb{S}|) - (1+r) = \dim(P(G, K, \mathbb{S})) - 1,$$

where $Q$” denotes the matrix associated with the equation system (17). As a result, the face $F_s^k$ is facet defining for $P(G, K, \mathbb{S})$. Furthermore, we strengthen our proof as follows. We denote the inequality $z_s^k \ge 0$ 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_s^k \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$ with $\gamma = (\gamma_1, \gamma_2, ..., \gamma_4)$ ($\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 demand $k$ and all slots $s' \in \{w_k, ..., \bar{s}\} \setminus \{s\}$,

- and $\sigma_{s'}^k = 0$ for all demands $k' \in K \setminus \{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)$.

First, let's show that $\mu_e^k = 0$ for all the demands $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$. 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'^6 = (E'^6, S'^6)$ in which

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

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

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

- and the slot $s$ is not chosen to route the demand $k$ in the solution $S'^6$, i.e., $s \notin S_k'^6$.

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

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

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

- and the slot $s$ is not chosen to route the demand $k$ in the solution $S^7$, i.e., $s \notin S_k^7$.

The corresponding incidence vector $(x^{S^7}, z^{S^7})$ is belong to $F$ and then to $F_s^k$ given that it is composed by $z_s^k = 0$. It follows that

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

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

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). $$

Next, we will show that, $\sigma_{s'}^{k'} = 0$ for all $k' \in K \setminus \{k\}$ and all $s' \in \{w_{k'}, ..., \bar{s}\}$, and $\sigma_{s'}^k = 0$ for all slots $s' \in \{w_k, ..., \bar{s}\} - \{s\}$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\} - \{s\}$. For that, we consider a solution $S'^6 = (E'^6, S'^6)$ in which

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

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

- and the slot $s$ is not chosen to route the demand $k$ in the solution $S'^6$, i.e., $s \notin S_k'^6$.
$\mathcal{S}^{\mathfrak{S}^6}$ 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}^6}, z^{\mathcal{S}^6})$ is belong to $F$ and then to $F_s^k$ given that it is composed by $z_s^k = 0$. Based on this, we distinguish two cases:

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

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

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

* and the slot $s$ is not chosen to route the demand $k$ in the solution $\mathcal{S}^8$, i.e., $s \notin S_k^8$.

The corresponding incidence vector $(x^{\mathcal{S}^8}, z^{\mathcal{S}^8})$ is belong to $F$ and then to $F_s^k$ given that it is composed by $z_s^k = 0$. We then obtain that

$$ \mu x^{\mathcal{S}^{\mathfrak{S}^6}} + \sigma z^{\mathcal{S}^{\mathfrak{S}^6}} = \mu x^{\mathcal{S}^8} + \sigma z^{\mathcal{S}^8} = \mu x^{\mathcal{S}^{\mathfrak{S}^6}} + \sigma z^{\mathcal{S}^{\mathfrak{S}^6}} + \sigma_{s'}^k. $$

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

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

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

* and the slot $s$ is not chosen to route the demand $k$ in the solution $\mathcal{S}^{\mathfrak{S}^6}$, i.e., $s \notin S_k^{\mathfrak{S}^6}$.

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

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

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

* and the slot $s$ is not chosen to route the demand $k$ in the solution $\mathcal{S}^{\mathfrak{S}^6}$, i.e., $s \notin S_k^{\mathfrak{S}^6}$.

The corresponding incidence vector $(x^{\mathcal{S}^{\mathfrak{S}^6}}, z^{\mathcal{S}^{\mathfrak{S}^6}})$ is belong to $F$ and then to $F_s^k$ given that it is composed by $z_s^k = 0$. We have so

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

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\} \setminus \{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)$.
The slot $s'$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\} \setminus \{s\}$ of demand $k$ s.t. we find

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

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

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

Consequently, we conclude that

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

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 (18) $$

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, ..., w_{k'} - 1\}, \\ 0, & \text{if } s' \in \{w_{k'}, ..., \bar{s}\} \text{ and } k' \neq k, \\ 0, & \text{if } s' \in \{w_{k'}, ..., \bar{s}\} \setminus \{s\} \text{ and } k' = k, \\ \rho, & \text{if } s' = s \text{ and } k' = k. \end{cases} $$

As a result $(\mu, \sigma) = \rho\beta_s^k + \gamma Q$ which ends our strengthening of proof.
**Definition 2.** For a demand k, two edges e = ij / ∈ E₀ᵏ ∩ E₁ᵏ, e' = lm / ∈ E₀ᵏ ∩ E₁ᵏ are said non-compatible edges iff the lengths of (oₖ, dₖ)-paths formed by e = ij and e' = lm together are greater that l̅ₖ.

Note that we are able to determine the non-compatible edges for each demand k in polynomial time using shortest-path algorithms by verifying if the length of the following (oₖ, dₖ)-paths

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, i), (j, l) and (m, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, i), (j, m) and (l, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, j), (i, l) and (m, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, j), (i, m) and (l, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, l), (m, i) and (j, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, l), (m, j) and (i, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, m), (l, i) and (j, dₖ) paths,

- (oₖ, dₖ)-path formed by e and e' together with the shortest (oₖ, m), (l, j) and (i, dₖ) paths,

are greater that l̅ₖ.

**Proposition 4.** Consider a demand k ∈ K. Let (e, e') be a pair of non-compatible edges for the demand k. Then, the inequality

$$
x_e^k + x_{e'}^k \le 1, \tag{19}
$$

is valid for P(G, K, S).

*Proof.* It is trivial due to the transmission-reach constraint and given the definition of non-compatible edges for the demand k.

Based on the definition of a non-compatible demands for an edge e, we introduce the following inequality.

**Proposition 5.** *Consider an edge* *e* ∈ *E*. Let (*k*, *k*′) be a pair of non-compatible demands for the edge *e* with *e* / ∈ *E*<sub>0</sub><sup>*k*</sup> ∪ *E*<sub>1</sub><sup>*k*</sup> ∪ *E*<sub>0</sub><sup>*k*′</sup> ∪ *E*<sub>1</sub><sup>*k*′</sup>. Then, the inequality

$$
x_e^k + x_e^{k'} \le 1, \tag{20}
$$

is valid for P(G, K, S).

*Proof.* It is trivial given the definition of non-compatible demands for the edge *e*.

Based on the inequalities (20) and (19), we introduce the following conflict graph.

**Definition 3.** Let $\tilde{G}_E^K$ be a conflict graph defined as follows. For each demand k and edge e / ∈ $E_0^k \cup E_1^k$, consider a node $v_e^k$ in $\tilde{G}_E^K$. Two nodes $v_e^k$ and $v_{e'}^{k'}$ are linked by an edge in $\tilde{G}_E^K$

- if k = k': e and e' are non compatible edges for demand k.

- if k ≠ k': k and k' are non compatible demands for edge e.

**Theorem 4.** Consider a demand $k \in K$, and an edge $e \in E \setminus (E_0^k \cup E_1^k)$. Then, the inequality $x_e^k \le 1$ is facet defining for $P(G, K, S)$ if and only if $N(v_{k,e}) = \emptyset$ in $\tilde{G}_E^K$.

*Proof. Neccessity.*

For demand k and an edge e ∈ E \ (E₀ᵏ ∪ E₁ᵏ), if N(vₖ, e) ≠ ∅ in G̃Eₖ, the inequality xₑᵏ ≤ 1 is dominated by the inequality (20) or (19) s.t. there exists at least one clique of cardinality at least equals to 2 in the conflict graph G̃E_S that contains the node vₖ, e. As a result, the inequality xₑᵏ ≤ 1 is not facet defining for P(G, K, S).

**Sufficiency.**

Let $F_e'^k$ denote the face induced by inequality $x_e^k \le 1$, which is given by

$$
F_e'^k = \{(x, z) \in P(G, K, \mathbb{S}) : x_e^k = 1\}.
$$

In order to prove that inequality $x_e^k \le 1$ is a facet defining for $P(G, K, S)$, we start checking that $F_e'^k$ is a proper face, and $F_e'^k \ne P(G, K, S)$. We construct a solution $S^9 = (E^9, S^9)$ as below
- a feasible path $E_k^9$ is assigned to each demand $k \in K$ (routing constraint),

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

- and the edge $e$ is chosen to route the demand $k$ in the solution $S^9$, i.e., $e \in E_k^9$.

Obviously, $S^9$ is 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^9}, z^{S^9})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_e^{\prime k}$ given that it is composed by $x_e^k = 1$. As a result, $F_e^{\prime k}$ is not empty ($F_e^{\prime k} \neq \emptyset$). Furthermore, given that $e \in E \setminus (E_0^k \cup E_1^k)$ for the demand $k$, this means that there exists at least one feasible path $E_k$ for the demand $k$ passed through the edge $e$ which means that $F_e^{\prime k} \neq P(G, K, \mathbb{S})$.

On another hand, we know that all the solutions of $F_e^{\prime k}$ are in $P(G, K, \mathbb{S})$ which means that they verify the equations system (13) s.t. the new equations system (21) associated with $F_e^{\prime k}$ is written as below

$$ \left\{ \begin{array}{l} x_e^k = 1, \text{ s.t. } k \text{ and } e \text{ are chosen arbitrarily} \\ x_e^k = 0, \text{ for all } k \in K \text{ and all } e \in E_0^k \\ x_e^k = 1, \text{ for all } k \in K \text{ and all } e \in E_1^k \\ z_s^k = 0, \text{ for all } k \in K \text{ and all } s \in \{1, \dots, w_k - 1\}. \end{array} \right. \qquad (21) $$

Given that the $e \in E \setminus (E_0^k \cup E_1^k)$, the system (21) shows that the equation $x_e^k = 1$ is not a result of equations of system (13) which means that the equation $x_e^k = 1$ is not redundant in the system (21). As a result, the system is of full rank. As a result, the dimension of the face $F_e^{\prime k}$ is equal to

$$ \dim(F_e^{\prime k}) = |K| * (|E| + |\mathbb{S}|) - \mathrm{rank}(\tilde{Q}') = |K| * (|E| + |\mathbb{S}|) - (1+r) = \dim(P(G, K, \mathbb{S})) - 1, $$

where $\tilde{Q}'$ is the matrix associated with the equation system (21). As a result, the face $F_e^{\prime k}$ is facet defining for $P(G, K, \mathbb{S})$. Furthermore, we strengthened our proof as follows. We denote the inequality $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_e^{\prime k} \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$ with $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (with $\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$. We will show that

- $\mu_e^k = 0$ for the demand $k$ and all $e' \in E \setminus (E_0^k \cup E_1^k \cup \{e\})$,

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

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

First, let's show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$. Consider a demand $k$ and a slot $s$ in $\{w_k, ..., \bar{s}\}$. To do so, we consider a solution $S^{\prime 9} = (E^{\prime 9}, S^{\prime 9})$ in which

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

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

- and the edge $e$ is chosen to route the demand $k$ in the solution $S^{\prime 9}$, i.e., $e \in E_k^{\prime 9}$.

$S^{\prime 9}$ 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^{\prime 9}}, z^{S^{\prime 9}})$ is belong to $P(G, K, \mathbb{S})$. Based on
this, we derive a solution $S^{10} = (E^{10}, S^{10})$ from the solution $S^{19}$ by adding the slot $s$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S^{19}$ (i.e., $E_k^{10} = E_1^{19}$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S^{19}$ remain the same in the solution $S^{10}$ i.e., $S_{k'}^{19} = S_k^{10}$ for each demand $k' \in K \setminus \{k\}$, and $S_k^{10} = S_k^{19} \cup \{s\}$ for the demand $k$. The solution $S^{10}$ is feasible given that

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

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

The corresponding incidence vector $(x^{S^{10}}, z^{S^{10}})$ is belong to $F$ and then to $F_e^{k'}$ given that it is also composed by $x_e^k = 1$. We then obtain that

$$ \mu x^{S^{19}} + \sigma z^{S^{19}} = \mu x^{S^{10}} + \sigma z^{S^{10}} = \mu x^{S^{19}} + \sigma z^{S^{19}} + \sigma_s^k. $$

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

The slot $s$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ s.t. we find

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

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

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

Consequently, we conclude that

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

Next, we will show that $\mu_{e'}^k = 0$ for all the demands $k' \in K \setminus \{k\}$ and all $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$, and $\mu_{e'}^k = 0$ for the demand $k$ and all $e' \in E \setminus (E_0^{k'} \cup E_1^{k'} \cup \{e\})$. Consider the demand $k \in K$ and an edge $e' \in E \setminus (E_0^{k'} \cup E_1^{k'} \cup \{e\})$ chosen arbitrarily. For that, we consider a solution $S^{19} = (E^{19}, S^{19})$ in which

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

- a set of last-slots $S_k^{19}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{19}$ with $|S_k^{19}| \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^{19}$ and $s'' \in S_{k'}^{19}$ with $E_k^{19} \cap E_{k'}^{19} \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^{19}} |\{s' \in S_k^{19}, 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^{19}$ of demand $k$ in the solution $S^{19}$, i.e., $\sum_{e'' \in E_k^{19}} l_{e''} + l_{e'} \le \bar{l}_k$. As a result, $E_k^{19} \cup \{e'\}$ is a feasible path for the demand $k$,

- and the edge $e$ is chosen to route the demand $k$ in the solution $S^{19}$, i.e., $e \in E_k^{19}$.

$S^{19}$ 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^{19}}, z^{S^{19}})$ is belong to $F$ and then to $F_e^{k'}$ given that it is also composed by $x_e^k = 1$. Based on this, we distinguish two cases:

- without changing the spectrum assignment established in $S^{19}$: we derive a solution $S^{11}$ obtained from the solution $S^{19}$ 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^{19}$ which means that $E_k^{2'} = E_k^{9'} \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S^{19}$ remain the same in the solution $S^{11}$, i.e., $S_k^{2'} = S_k^{9'}$ for each $k \in K$, and $E_{k'}^{2'} = E_{k'}^{9'}$ for each $k' \in K \setminus \{k\}$. $S^{11}$ is clearly feasible given that
* and a feasible path $E_k''^2$ is assigned to each demand $k \in K$ (routing constraint),

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

The corresponding incidence vector $(x^{S''^{11}}, z^{S''^{11}})$ is belong to $F$ and then to $F_e'^k$ given that it is also composed by $x_e^k = 1$. It follows that

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

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

- with changing the spectrum assignment established in $S''^9$: let $S''^{11}$ be a solution obtained from the solution $S''^9$ 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''^9$ which means that $E_k''^{11} = E_k''^9 \cup \{e\}$ s.t. $\{s - w_k + 1, ..., s\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k' \in K \setminus \{k\}$ and $s'' \in S_k''^9$ with $E_k''^{11} \cap E_{k'}''^9 \neq \emptyset$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S''^9$ remain the same in the solution $S''^{11}$, i.e., $S_k''^{11} = S_k''^9$ for each $k \in K$, and $E_{k'}''^{11} = E_{k'}''^9$ for each $k' \in K \setminus \{k\}$. $S''^{11}$ is clearly feasible given that

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

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

The corresponding incidence vector $(x^{S''^{11}}, z^{S''^{11}})$ is belong to $F$ and then to $F_e'^k$ given that it is also composed by $x_e^k = 1$. It follows that

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

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

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 \setminus \{k\} \text{ and all } e' \in E \setminus (E_0^{k'} \cup E_1^{k'}), $$

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

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 (22) $$

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' = 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\}, \\ 0, & \text{otherwise.} \end{cases} $$

As a result $(\mu, \sigma) = \rho\alpha_e^k + \gamma Q$ which ends our proof.

**Theorem 5.** Consider a demand $k$ and a subset of node $X \subset V$, with $|X \cap \{o_k, d_k\}| = 1$ and $X \cap V_0^k = \emptyset$. Then, the inequality (2), $\sum_{e \in \delta(X)} x_e^k \ge 1$, is facet defining for $P(G, K, \mathbb{S})$ if and only if $\delta(X) \not\subset E_1^k$.

*Proof.* Let $F_X^k$ denote the face induced by inequality $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k \ge 1$, which is given by

$$ F_X^k = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1\} $$

Let $X = \{o_k\}$. In order to prove that inequality $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k \ge 1$ is facet defining for $P(G, K, \mathbb{S})$,

we start checking that $F_X^k$ is a proper face which means that it is not empty, and $F_X^k \neq P(G, K, \mathbb{S})$. We construct a solution $S^{12} = (E^{12}, S^{12})$ as below

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

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

- and one edge $e$ from $(\delta(X) \setminus E_0^k)$ is chosen to route the demand $k$ in the solution $S^{12}$, i.e., $| (\delta(X) \setminus E_0^k) \cap E_k^{12} | = 1$.

Obviously, $S^{12}$ is 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^{12}}, z^{S^{12}})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_X^k$ given that it is composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. As a result, $F_X^k$ is
not empty ($F_X^k \neq \emptyset$). Furthermore, given that $e \in E \setminus (E_0^k \cup E_1^k)$ for the demand $k$, this means that there exists at least one feasible path $E_k$ for the demand $k$ passed through the edge $e$ which means that $F_X^k \neq P(G, K, \mathbb{S})$.

Let denote the inequality $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k \geq 1$ by $\alpha x + \beta z \leq \lambda$. Let $\mu x + \sigma z \leq \tau$ be a valid inequality that is facet defining $F$ of $P(G, K, \mathbb{S})$. Suppose that $F_X^k \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$ with $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (with $\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$. We will show that

- $\mu_{e'}^k = 0$ for the demand $k$ and all $e' \in E \setminus (E_0^k \cup E_1^k \cup (\delta(X) \setminus E_0^k))$,

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

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

- and that $\mu_e^k$ are equivalent for all $e \in (\delta(X) \setminus E_0^k)$.

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

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

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

- and one edge $e$ from $(\delta(X) \setminus E_0^k)$ is chosen to route the demand $k$ in the solution $S'^{12}$, i.e., $|(\delta(X) \setminus E_0^k) \cap E_k'^{12}| = 1$.

$S'^{12}$ 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'^{12}}, z^{S'^{12}})$ is belong to $P(G, K, \mathbb{S})$. Based on this, we derive a solution $S^{13} = (E^{13}, S^{13})$ from the solution $S'^{12}$ by adding the slot $s$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S'^{12}$ (i.e., $E_k'^{13} = E_1'^{12}$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S'^{12}$ remain the same in the solution $S^{13}$ i.e., $S_{k'}'^{12} = S_k'^{13}$ for each demand $k' \in K \setminus \{k\}$, and $S_k'^{13} = S_{k'}'^{12} \cup \{s\}$ for the demand $k$. The solution $S^{13}$ is feasible given that

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

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

The corresponding incidence vector $(x^{S^{13}}, z^{S^{13}})$ is belong to $F$ and then to $F_X^k$ given that it is also composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. We then obtain that

$$ \mu x^{S'^{12}} + \sigma z^{S'^{12}} = \mu x^{S^{13}} + \sigma z^{S^{13}} = \mu x^{S'^{12}} + \sigma z^{S'^{12}} + \sigma_s^k. $$

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

The slot $s$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ s.t. we find

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

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

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

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

Next, we will show that $\mu_{e'}^k = 0$ for all the demands $k' \in K \setminus \{k\}$ and all $e' \in E \setminus (E_0^{k'} \cup E_1^{k'})$, and $\mu_{e'}^k = 0$ for the demand $k$ and all $e' \in E \setminus (E_0^k \cup E_1^k \cup (\delta(X) \setminus E_0^k))$. Consider the demand $k \in K$ and an edge $e' \in E \setminus (E_0^k \cup E_1^k \cup (\delta(X) \setminus E_0^k))$ chosen arbitrarily. For that, we consider a solution $S^{12} = (E^{12}, S^{12})$ in which

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

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

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

- and one edge $e$ from $(\delta(X) \setminus E_0^k)$ is chosen to route the demand $k$ in the solution $S^{12}$, i.e., $|\delta(X) \setminus E_0^k \cap E_k^{12}| = 1$.

$S^{12}$ 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^{12}}, z^{S^{12}})$ is belong to $F$ and then to $F_X^k$ given that it is also composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. Based on this,

- without changing the spectrum assignment established in $S^{12}$: we derive a solution $S^{14}$ obtained from the solution $S^{12}$ 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^{12}$ which means that $E_k^{22} = E_k^{12} \cup \{e'\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S^{12}$ remain the same in the solution $S^{14}$, i.e., $S_k^{22} = S_k^{12}$ for each $k \in K$, and $E_k^{22} = E_k^{12}$ for each $k' \in K \setminus \{k\}$. $S^{14}$ is clearly feasible given that

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

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

The corresponding incidence vector $(x^{S^{14}}, z^{S^{14}})$ is belong to $F$ and then to $F_X^k$ given that it is also composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. It follows that

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

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

- with changing the spectrum assignment established in $S^{12}$: let $S^{14}$ be a solution obtained from the solution $S^{12}$ 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^{12}$ which means that $E_k^{14} = E_k^{12} \cup \{e'\}$, and removing slot $s$ selected for the demand $k$ in $S^{12}$ and replaced it by a new slot $s' \in \{w_k, \dots, S\}$ (i.e., $S_k^{14} = (S_k^{12} \setminus \{s'\}) \cup \{s'\}$ s.t. $\{s' - w_k + 1, \dots, s'\} \cap \{s'' - w_{k'} + 1, \dots, s''\} = \emptyset$ for each $k' \in K$ and $s'' \in S_k^{12}$ with $E_k^{14} \cap E_{k'}^{12} \neq \emptyset$. The last-slots and paths assigned the set of demands $K \setminus \{k\}$ in $S^{12}$ remain the same in the solution $S^{14}$, i.e., $S_k^{14} = S_k^{12}$ and $E_k^{14} = E_k^{12}$ for each $k' \in K \setminus \{k\}$. $S^{14}$ is clearly feasible given that

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

• a set of last-slots $S_k^{14}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k^{14}$ with $|S_k^{14}| \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^{14}$ and $s' \in S_{k'}^{14}$ with $E_k^{14} \cap E_{k'}^{14} \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^{14}} |\{s \in S_k^{14}, s'' \in \{s - w_k + 1, \dots, s'\}| \le 1$ (non-overlapping constraint).
The corresponding incidence vector $(x^{S^{14}}, z^{S^{14}})$ is belong to $F$ and then to $F_X^k$ given that it is also composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. It follows that

$$ \mu x^{S^{12}} + \sigma z^{S^{12}} = \mu x^{S^{14}} + \sigma z^{S^{14}} = \mu x^{S^{12}} + \mu_{e'}^k + \sigma z^{S^{12}} - \sigma_s^k + \sigma_{s'}^k $$

which gives that $\mu_{e'}^k = 0$ for demand $k$ and an edge $e'$ given that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$.

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

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

Let's us prove that the $\mu_e^k$ for a demand $k$ and edges $e \in (\delta(X) \setminus E_0^k)$ are equivalent. Consider an edge $e' \in (\delta(X) \setminus E_0^k)$ s.t. $e' \notin E_k^{12}$. For that, we consider a solution $\tilde{S}^{12} = (\tilde{E}^{12}, \tilde{S}^{12})$ in which

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

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

- and there is one edge $e$ from $(\delta(X) \setminus E_0^k)$ selected for the routing of demand $k$ in the solution $\tilde{S}^{12}$, i.e., $|(\delta(X) \setminus E_0^k) \cap \tilde{E}_k^{12}| = 1$.

$\tilde{S}^{12}$ 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^{12}}, z^{S^{12}})$ is belong to $F$ and then to $F_X^k$ given that it is composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. Based on this, we distinguish two cases:

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

• modifying the path assigned to the demand $k$ in $\tilde{S}^{12}$ from $\tilde{E}_k^{12}$ to a path $E_k^{15}$ passed through the edge $e'$ with $|(\delta(X) \setminus E_0^k) \cap \tilde{E}_k^{12}| = 1$.

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

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

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

• and $|(\delta(X) \setminus E_0^k) \cap \tilde{E}_k^{12}| = 1$.

The corresponding incidence vector $(x^{S^{15}}, z^{S^{15}})$ is belong to $F$ and then to $F_X^k$ given that it is composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. We then obtain that

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

It follows that $\mu_{e'}^k = \mu_e^k$ for demand $k$ and an edge $e' \in (\delta(X) \setminus E_0^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 $e'' \notin (\delta(X) \setminus E_0^k)$.
- with changing the spectrum assignment established in $\tilde{S}^{12}$: we construct a solution $S'^{15}$ derived from the solution $\tilde{S}^{12}$ by

* modifying the path assigned to the demand $k$ in $\tilde{E}_k^{12}$ to a path $E_k'^{15}$ passed through the edge $e'$ with $|\langle\delta(X) \setminus E_0^k\rangle \cap E_k'^{15}| = 1$,

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

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

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

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

* $|(\delta(X) \setminus E_0^k) \cap E_k'^{15}| = 1$.

The corresponding incidence vector $(x^{S'^{15}}, z^{S'^{15}})$ is belong to $F$ and then to $F_X^k$ given that it is composed by $\sum_{e \in (\delta(X) \setminus E_0^k)} x_e^k = 1$. We have so

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

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

Given that the pair of edges $(e, e')$ are chosen arbitrary in $(\delta(X) \setminus E_0^k)$, we iterate the same procedure for all pairs $(e, e') \in (\delta(X) \setminus E_0^k)$ s.t. we find

$$ \mu_e^k = \mu_{e'}^k, \text{ for all pairs } e, e' \in (\delta(X) \setminus E_0^k). $$

Consequently, we obtain that $\mu_e^k = \rho$ for all $e \in (\delta(X) \setminus E_0^k)$.

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 independents s.t. for each demand $k \in K$, we have

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

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

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

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 = k' \text{ and } e \in (\delta(X) \setminus E_0^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, ..., w_k - 1\}, \\ 0, & \text{otherwise.} \end{cases} $$

$$ \text{We conclude that } (\mu, \sigma) = \rho \sum_{e \in (\delta(X) \setminus E_0^k)} \alpha_e^k + \gamma Q. $$

**Theorem 6.** Consider a demand $k \in K$. Then, the inequality (7), $\sum_{s=w_k}^{\bar{s}} z_s^k \ge 1$, is facet defining for $P(G, K, \mathbb{S})$.

*Proof.* Let $F_{\mathbb{S}}^k$ denote the face induced by inequality $\sum_{s=w_k}^{\bar{s}} z_s^k \ge 1$, which is given by

$$ F_{\mathbb{S}}^k = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{s=w_k}^{\bar{s}} z_s^k = 1\} $$

In order to prove that inequality $\sum_{s=w_k}^{\bar{s}} z_s^k \ge 1$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_{\mathbb{S}}^k$ is a proper face which means that it is not empty, and $F_{\mathbb{S}}^k \ne P(G, K, \mathbb{S})$. We construct a solution $S^{16} = (E^{16}, S^{16})$ as below

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

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

- and one slot $s$ from the set $\{w_k, ..., \bar{s}\}$ is chosen to route the demand $k$ in the solution $S^{16}$, i.e., $|S_k^{16}| = 1$.

Obviously, $S^{16}$ is 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^{16}}, z^{S^{16}})$ is belong to $F$ and then to $F_{\mathbb{S}}^k$ given that it is composed by $\sum_{s=w_k}^{\bar{s}} z_s^k = 1$. As a result, $F_{\mathbb{S}}^k$ is not empty ($F_{\mathbb{S}}^k \ne \emptyset$). Furthermore, given that $s \in \{w_k, ..., \bar{s}\}$ for the demand $k$, this means that there exists at least one feasible solution for the problem in which $|S_k| \ge 2$ for the demand $k$. As a result, $F_{\mathbb{S}}^k \ne P(G, K, \mathbb{S})$. On another hand, we know that all the solutions of $F_{\mathbb{S}}^k$ are in $P(G, K, \mathbb{S})$ which means that they verify the equations system (13) s.t. the following equations system (24) associated with $F_{\mathbb{S}}^k$ is written as below
$$
\left\{
\begin{array}{l}
\displaystyle \sum_{s=w_k}^{\bar{s}} z_s^k = 1, \text{ s.t. } k \text{ is chosen arbitrarily,} \\
\\
\displaystyle x_e^k = 0, \text{ for all } k \in K \text{ and all } e \in E_0^k, \\
\\
\displaystyle x_e^k = 0, \text{ for all } k \in K \text{ and all } e \in E_c^k, \\
\\
\displaystyle x_e^k = 1, \text{ for all } k \in K \text{ and all } e \in E_1^k, \\
\\
\displaystyle z_s^k = 0, \text{ for all } k \in K \text{ and all } s \in \{1, \dots, w_k - 1\}.
\end{array}
\right.
\qquad (24)
$$

The system (24) shows that the equation $\sum_{s=w_k}^{\bar{s}} z_s^k = 1$ is not result of equations of system (13)
which means that the equation $\sum_{s=w_k}^{\bar{s}} z_s^k = 1$ is not redundant in the system (24). As a result, the
system (24) is in full rank which implies that the dimension of the face $F_S^k$ is equal to

$$
dim(F_{\mathbb{S}}^{k}) = |K| * (|E| + |\mathbb{S}|) - rank(M'') = |K| * (|E| + |\mathbb{S}|) - (1+r) = dim(P(G, K, \mathbb{S})) - 1,
$$

where $M''$ denotes the matrix associated with the equation system (24). As a result, the face $F_{\mathbb{S}}^k$ is facet defining for $P(G, K, \mathbb{S})$.

We strengthen our proof as follows. We denote the inequality $\sum_{s=w_k}^{\bar{s}} z_s^k \ge 1$ by $\alpha x + \beta z \le \lambda$. Let $\mu x + \sigma z \le \tau$ be a valid inequality that defines a facet $F$ of $P(G, K, \mathbb{S})$. Suppose that $F_{\mathbb{S}}^k \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$ with $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ $(\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)$, and that

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

- and $\mu_e^k = 0$ for all demands $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$,

- and all $\sigma_s^k$ are equivalents for demand $k$ and slots $s \in \{w_k, \dots, \bar{s}\}$ for the demand $k$.

First, let's us show that $\mu_e^k = 0$ for all the demands $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$. 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'^{16} = (E'^{16}, S'^{16})$ in which

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

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

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

- and one slot $s$ from the set $\{w_k, \dots, \bar{s}\}$ is chosen to route the demand $k$ in the solution $S^{16}$, i.e., $|S_k^{16}| = 1$.

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

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

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

The corresponding incidence vector ($x^{S^{17}}, z^{S^{17}}$) is belong to $F$ and then to $F_S^k$ given that it is composed by $\sum_{s=w_k}^S z_s^k = 1$. It follows that

$$\mu x^{S^{16}} + \sigma z^{S^{16}} = \mu x^{S^{17}} + \sigma z^{S^{17}} = \mu x^{S^{16}} + \mu_e^k + \sigma z^{S^{16}}.$$

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

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).$$

Next, we will show that, $\sigma_{s'}^{k'} = 0$ for all $k' \in K \setminus \{k\}$ and all $s' \in \{w_{k'}, ..., \bar{s}\}$. Consider the demand $k'$ in $K \setminus \{k\}$ and a slot $s'$ in $\{w_{k'}, ..., \bar{s}\} \setminus \{s\}$. For that, we consider a solution $S^{16} = (E^{16}, S^{16})$ in which

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

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

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

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

- and $|S_k^{16}| = 1$ for the demand $k$.

$S^{16}$ 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^{16}}, z^{S^{16}}$) is belong to $F$ and then to $F_S^k$ given that it is composed by $\sum_{s=w_k}^S z_s^k = 1$. Based on this, we distinguish two cases:

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

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

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

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

* and $|S_k^{18}| = 1$ for the demand $k$.

The corresponding incidence vector ($x^{S^{18}}, z^{S^{18}}$) is belong to $F$ and then to $F_S^k$ given that it is composed by $\sum_{s=w_k}^S z_s^k = 1$. We obtain that

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

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

* and $|S_k'^{18}|$ for the demand $k$.

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

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

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

* and $|S_k'^{18}|$ for the demand $k$.

The corresponding incidence vector $(x^{S'^{18}}, z^{S'^{18}})$ is belong to $F$ and then to $F_S^k$ given that it is composed by $\sum_{s=w_k}^{\bar{s}} z_s^k = 1$. We have so

$$ \mu x^{S^{16}} + \sigma z^{S^{16}} = \mu x^{S'^{18}} + \sigma z^{S'^{18}} = \mu x^{S^{16}} + \sigma z^{S^{16}} + \sigma k' - \sum_{\tilde{k} \in \tilde{K}} \sum_{e \in E_k'^{16}} \mu_{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k'^{18}} \mu_{\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)$.

The slot $s'$ is chosen arbitrarily for the demand $k'$, we iterate the same procedure for all feasible slots in $\{w_{k'}, ..., \bar{s}\}$ of demand $k'$ s.t. we find

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

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

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

Consequently, we conclude that

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

Let's prove now that $\sigma_s^k$ for demand $k$ and slots $s$ in $\{w_k, ..., \bar{s}\}$ are equivalent. Consider a slot $s' \in \{w_k, ..., \bar{s}\}$ s.t. $s' \notin S_k^{16}$. For that, we consider a solution $\tilde{S}^{16} = (\tilde{E}^{16}, \tilde{S}^{16})$ in which

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

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

- and $|\tilde{S}_k^{16}| = 1$ for the demand $k$.
$\tilde{S}^{16}$ 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^{16}}, z^{S^{16}})$ is belong to $F$ and then to $F_{\tilde{S}}^k$ given that it is composed by $\sum_{s=w_k}^{\tilde{s}} z_s^k = 1$. Based on this,

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

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

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

- and $|S_k^{19}| = 1$.

The corresponding incidence vector $(x^{S^{19}}, z^{S^{19}})$ is belong to $F$ and then to $F_{\tilde{S}}^k$ given that it is composed by $\sum_{s=w_k}^{\tilde{s}} z_s^k = 1$. We then obtain that

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

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

- with changing the paths established in $\tilde{S}^{16}$: we construct a solution $S^{19}$ derived from the solution $\tilde{S}^{16}$ by adding the slot $s'$ as last-slot to the demand $k'$ in $S_k^{19}$ and removing the last slot $s$ assigned to $k$ in $\tilde{S}_k^{16}$ (i.e., $S_k^{19} = (\tilde{S}_k^{16} \setminus \{s\}) \cup \{s'\}$ for the demand $k$) with modifying the paths assigned to a subset of demands $\tilde{K} \subset K$ in $\tilde{S}^{16}$ (i.e., $E_k^{19} = \tilde{E}_k^{16}$ for each $k \in K \setminus \tilde{K}$, and $E_k^{19} \neq \tilde{E}_k^{16}$ for each $k \in \tilde{K}$), and also the last-slots assigned to the demands $K \setminus \{k\}$ in $\tilde{S}^{16}$ remain the same in $S^{19}$. The solution $S^{19}$ is clearly feasible given that

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

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

- and $|S_k^{19}| = 1$.

The corresponding incidence vector $(x^{S^{19}}, z^{S^{19}})$ is belong to $F$ and then to $F_{\tilde{S}}^k$ given that it is composed by $\sum_{s=w_k}^{\tilde{s}} z_s^k = 1$. We have so

$$ \mu x^{\tilde{S}^{16}} + \sigma z^{\tilde{S}^{16}} = \mu x^{S^{19}} + \sigma z^{S^{19}} = \mu x^{\tilde{S}^{16}} + \sigma z^{\tilde{S}^{16}} + \sigma_{s'}^k - \sigma_s^k + \sigma_{\bar{s}}^k \\ - \sum_{k \in \tilde{K}} \sum_{e \in E_k^{16}} \mu x^{\tilde{S}^{16}} + \sum_{k \in \tilde{K}} \sum_{e \in E_k^{19}} \mu x^{S^{19}}. $$

It follows that $\sigma_{s'}^k = \sigma_s^k$ for demand $k$ and a slots $s, s' \in \{w_k, ..., \bar{s}\}$ given that $\mu_e^k = 0$ for all $k \in K$ and all $e \in E \setminus (E_0^k \cup E_1^k)$.

The slot $s$ is chosen arbitrarily for the demand $k$ in $\{w_k, ..., \bar{s}\}$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ s.t. we find

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

Consequently, we obtain that $\sigma_s^k = \rho$ for demand $k$ and slots $s$ in $\{w_k, ..., \bar{s}\}$.

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 (25) $$

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, ..., w_{k'} - 1\} \\ \rho, & \text{if } k' = k \text{ and } s \in \{w_{k'}, ..., \bar{s}\} \\ 0, & \text{otherwise.} \end{cases} $$

As a result $(\mu, \sigma) = \sum_{s=w_k}^{\bar{s}} \rho \beta_s^k + \gamma Q$ for the demand $k$ which ends our strengthening of proof.

**Proposition 6.** Consider an edge $e \in E$, and an interval of contiguous slots $I = [s_i, s_j] \subset \mathbb{S}$. Let $k, k' \in K$ be pair of demands with $e \notin (E_0^k \cup E_0^{k'})$, $2w_k > |I|$, $2w_{k'} > |I|$, $w_{k'} + w_{k'} > |I|$, and $k, k'$ are not non-compatible demands for the edge $e$. Then, the following inequality is valid for $P(G, K, \mathbb{S})$

$$ x_e^k + x_e^{k'} + \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{s=s_i+w_{k'}-1}^{s_j} z_s^k \le 3. \quad (26) $$

*Proof.* For each edge $e \in E$ and interval of contiguous slots $I \subseteq \mathbb{S}$, the inequality (26) ensures that if the two demands $k, k'$ pass through edge $e$, they cannot share the interval $I = [s_i, s_j]$ over edge $e$.
**Theorem 7.** Consider an edge $e \in E$, and a slot $s \in \mathbb{S}$. Let $k, k'$ be two demands in $K$ with $k, k'$ are not non-compatible demands for the edge $e$. Then, the inequality (8) is facet defining for $P(G, K, \mathbb{S})$ iff $K_e \setminus \{k, k'\} = \emptyset$, and there does not exist an interval of contiguous slots $I = [s_i, s_j]$ s.t.

$$- |\{s_i + w_k - 1, ..., s_j\}| \geq w_k,$$

$$- \text{and } |\{s_i + w_{k'} - 1, ..., s_j\}| \geq w_{k'}$$

$$- \text{and } s \in \{s_i + \max(w_k, w_{k'}) - 1, ..., s_j - \max(w_k, w_{k'}) + 1\},$$

$$- \text{and } w_k + w_{k'} \geq |I| + 1,$$

$$- \text{and } 2w_k \geq |I| + 1,$$

$$- \text{and } 2w_{k'} \geq |I| + 1.$$

*Proof.* Let $\tilde{K} = \{k, k'\}$.

**Necessity.**

If $K_e \setminus \tilde{K} \neq \emptyset$, then the inequality (8) is dominated by the inequality (26) 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, ..., s_j\}| \geq w_k \text{ for each demand } k \in \tilde{K},$$

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

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

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

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

**Sufficiency.**

Let $F_{\tilde{K}}^{e,s}$ denote the face induced by the inequality (8), 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 \leq |\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} \neq P(G, K, \mathbb{S})$.

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

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

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

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

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

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

Obviously, $S^{20}$ 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^{20}}, z^{S^{20}})$ 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 \leq |\tilde{K}| + 1$ by $\alpha x + \beta z \leq \lambda$. Let $\mu x + \sigma z \leq \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_k^k|, \gamma_2 \in \mathbb{R} \sum_{k \in K} |E_1^k|, \gamma_3 \in \mathbb{R} \sum_{k \in K} (w_k - 1)$ s.t. $(\mu, \sigma) = \rho(\alpha, \beta) + \gamma Q$, and that
- $\sigma_{s'}^k = 0$ for all demands $k \in K$ and all slots $s' \in \{w_k, ..., \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'^{20} = (E'^{20}, S'^{20})$ in which

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

- and a set of last-slots $S_k'^{20}$ is assigned to each demand $k \in K$ along each edge $e' \in E_k'^{20}$ with $|S_k'^{20}| \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'^{20}$ and $s'' \in S_{k'}'^{20}$ with $E_k'^{20} \cap E_{k'}'^{20} \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'^{20}} |\{s' \in S_k'^{20}, 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'^{20}$ with $s' \in \{s, ..., s + w_k - 1\}$, i.e., $s' \in S_k'^{20}$ for a demand $k \in \tilde{K}$, and for each $s' \in S_{k'}'^{20}$ 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'^{20}$ of demand $k$ in the solution $S'^{20}$, i.e., $\sum_{e'' \in E_k'^{20}} l_{e''} + l_{e'} \le \bar{l}_k$. As a result, $E_k'^{20} \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'^{20}$, i.e., $e \in E_k'^{20}$ for each $k \in \tilde{K}$.

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

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

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

The corresponding incidence vector $(x^{S^{21}}, z^{S^{21}})$ 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'^{20}} + \sigma z^{S'^{20}} = \mu x^{S^{21}} + \sigma z^{S^{21}} = \mu x^{S'^{20}} + \mu_{e'}^k + \sigma z^{S'^{20}}. $$

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

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

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

- 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^{20}$ with $s' \in \{s, ..., s + w_k - 1\}$, i.e., $s' \in S_k^{20}$ for a demand $k \in \tilde{K}$, and for each $s' \in S_k^{20}$ 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^{20}$, i.e., $e' \in E_k^{20}$ for each $k \in \tilde{K}$.

$S^{20}$ 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^{20}}, z^{S^{20}})$ 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^{20}$: we derive a solution $S^{22} = (E^{22}, S^{22})$ from the solution $S^{20}$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S^{20}$ (i.e., $E_k^{22} = E_k^{20}$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S^{20}$ remain the same in the solution $S^{22}$ i.e., $S_{k'}^{22} = S_k^{22}$ for each demand $k' \in K \setminus \{k\}$, and $S_k^{22} = S_k^{20} \cup \{s'\}$ for the demand $k$. The solution $S^{22}$ is feasible given that

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

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

The corresponding incidence vector $(x^{S^{22}}, z^{S^{22}})$ 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^{20}} + \sigma z^{S^{20}} = \mu x^{S^{22}} + \sigma z^{S^{22}} = \mu x^{S^{20}} + \sigma z^{S^{20}} + \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^{20}$: we construct a solution $S'^{22}$ derived from the solution $S^{20}$ 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^{20}$ (i.e., $E_k^{22} = E_k^{20}$ for each $k \in K \setminus \tilde{K}$, and $E_k'^{22} \neq E_k^{20}$ for each $k \in \tilde{K}$) s.t.

* a new feasible path $E_k'^{22}$ 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^{20}$ and $s'' \in S_{k'}^{20}$ with $E_k'^{22} \cap E_{k'}^{20} \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'^{22}} |\{s' \in S_k^{20}, s'' \in \{s' - w_k + 1, ..., s'\}| + \sum_{k \in K \setminus \tilde{K}, e' \in E_k'^{20}} |\{s' \in S_k^{20}, 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^{20}$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k^{20}$ assigned to the demand $k$ in the solution $S^{20}$).
The last-slots assigned to the demands $K \setminus \{k\}$ in $S^{20}$ remain the same in $S'^{22}$, i.e., $S_k^{20} = S_{k'}'^{22}$ for each demand $k' \in K \setminus \{k\}$, and $S_k'^{22} = S_k^{20} \cup \{s\}$ for the demand $k$. The solution $S'^{22}$ is clearly feasible given that

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

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

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

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

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

* 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}^{20}$ with $s' \in \{s, ..., s + w_k - 1\}$, i.e., $s' \in \tilde{S}_k^{20}$ for a demand $k \in \tilde{K}$, and for each $s' \in \tilde{S}_{k'}^{20}$ 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}^{20}$, i.e., $e' \in \tilde{E}_k^{20}$ for each $k \in \tilde{K}$.

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

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

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

The corresponding incidence vector $(x^{S^{23}}, z^{S^{23}})$ 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}^{20}} + \sigma z^{\tilde{S}^{20}} = \mu x^{S^{23}} + \sigma z^{S^{23}} = \mu x^{\tilde{S}^{20}} + \sigma z^{\tilde{S}^{20}} + \sigma_{s''}^{k'} - \sigma_{s'}^{k} + \sigma_{\tilde{s}}^{k}. $$

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

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

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

The corresponding incidence vector $(x^{S'^{23}}, z^{S'^{23}})$ 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}^{20}} + \sigma z^{\tilde{S}^{20}} = \mu x^{S'^{23}} + \sigma z^{S'^{23}} = \mu x^{\tilde{S}^{20}} + \sigma z^{\tilde{S}^{20}} + \sigma_{s''}^{k'} - \sigma_{s'}^{k} + \sigma_{\tilde{s}}^{k} \\ - \sum_{k \in \tilde{K}} \sum_{e' \in \tilde{E}_k^{20}} \mu_{e'}^{k} + \sum_{k \in \tilde{K}} \sum_{e' \in \tilde{E}_k^{23}} \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_{\tilde{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^{24} = (E^{24}, S^{24})$ defined 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} \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^{24}$, i.e., $e \in E_k^{24}$ for a demand $k \in \tilde{K}$, and $e \notin E_{k'}^{24}$ 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^{24}$, i.e., $\{s_i + w_k + 1, ..., s_j\} \cap S_k^{24} \neq \emptyset$ for each $k \in \tilde{K}$.

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^{\tilde{S}^{24}}, z^{\tilde{S}^{24}})$ 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'}^{24}$. For that, we consider a solution $\tilde{S}^{24} = (\tilde{E}^{24}, \tilde{S}^{24})$ in which

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

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

$\tilde{S}^{24}$ 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}^{24}}, z^{\tilde{S}^{24}})$ 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 $\tilde{S}^{25} = (\tilde{E}^{25}, \tilde{S}^{25})$ from the solution $\tilde{S}^{24}$ by

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

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

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

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

The solution $\tilde{S}^{25}$ is feasible given that
- 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} \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^{25}} |\{s' \in S_k^{25}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{25}}, z^{S^{25}})$ 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}^{24}} + \sigma z^{\tilde{S}^{24}} = \mu x^{S^{25}} + \sigma z^{S^{25}} = \mu x^{\tilde{S}^{24}} + \sigma z^{\tilde{S}^{24}} + \mu_e^{k'} - \mu_e^k + \sum_{e'' \in E_k^{25} \setminus \{e\}} \mu_{e''}^{k'} - \sum_{e'' \in E_k^{25}} \mu_{e''}^{k'} + \sum_{e'' \in E_k^{25}} \mu_e^k - \sum_{e'' \in E_k^{25}} \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 \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^{26} = (E^{26}, S^{26})$ derived from the solution $\tilde{S}^{24}$ as below

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

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

- modifying the set of last-slots assigned to the demand $k'$ in $\tilde{S}^{24}$ from $\tilde{S}_{k'}^{24}$ to $S_{k'}^{26}$ s.t. $S_{k'}^{26} \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^{26}$. The solution $S^{26}$ is then 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, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., 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 \mathbb{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),

- and $\sum_{k \in \tilde{K}} |E_k^{26} \cap \{e\}| + |S_k^{26} \cap \{s, ..., s+w_k-1\}| = |\tilde{K}| + 1$.

The corresponding incidence vector $(x^{S^{26}}, z^{S^{26}})$ 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}^{24}} + \sigma z^{\tilde{S}^{24}} = \mu x^{S^{26}} + \sigma z^{S^{26}} = \mu x^{\tilde{S}^{24}} + \sigma z^{\tilde{S}^{24}} + \mu_e^{k'} - \sigma_{s'}^{k'} + \sum_{e'' \in E_k^{26} \setminus \{e\}} \mu_{e''}^{k'} - \sum_{e'' \in E_k^{26}} \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, \dots, 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, \dots, 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, \dots, 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, \dots, 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, \dots, 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, \dots, 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, \dots, w_k - 1\}. \quad (27) $$

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, \tilde{s})} \rho \beta_{s'}^k + \gamma Q. $$
## 5 Conclusion

In this paper, we studied the Constrained-Routing and Spectrum Assignment problem. We first introduced an integer linear programming based on the so-called cut formulation for the problem. We investigated the facial structure of the associated polyhedron by showing that some basic inequalities of the cut formulation are facet-defining under certain conditions.

## References

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21. Fayez, M., and Katib, I., and George, N.R., and Gharib, T.F., and Khaleed H., and Faheem, H.M. : Recursive algorithm for selecting optimum routing tables to solve offline routing and spectrum assignment problem. In: Ain Shams Engineering Journal 2020, pp. 273-280.
22. Ford, L. R., and Fulkerson, D. R. : Maximal flow through a network. In: Canadian Journal of Mathematics 8, pp. 399404, 1956.

23. Gong, L., and Zhou, X., and Lu, W., and Zhu, Z. : A Two-Population Based Evolutionary Approach for Optimizing Routing, Modulation and Spectrum Assignments (RMSA) in O-OFDM Networks. In: IEEE Communications Letters 2012, pp. 1520-1523.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

47. Margot, F. : Exploiting orbits in symmetric ilp. In: Mathematical Programming 2003, pp. 3-21.
48. Méndez-Díaz, I. and Zabala, P. : A Branch-and-Cut algorithm for graph coloring. In: Discrete Applied Mathematics Journal 2006, pp. 826-847.

49. Mesquita, L.A.J., and Assis, K., and Santos, A.F., and Alencar, M., and Almeida, R.C. : A Routing and Spectrum Assignment Heuristic for Elastic Optical Networks under Incremental Traffic. In: SBFoton International Optics and Photonics Conference (SBFoton IOPC) 2018, pp. 1-5.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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