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

HAL
open science

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

Ibrahima Diarrassouba, Youssouf Hadhbi, Ali Ridha Mahjoub

► To cite this version:

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

HAL Id: hal-03287205

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

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 II*

Ibrahima Diarrassouba<fnref n="1" />, Youssouf Hadhbi<fnref n="2" />, and Ali Ridha Mahjoub<fnref n="3" />

**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 introduce an integer linear programming formulation based on the so-called cut formulation for the C-RSA problem. We describe several valid inequalities for the associated polytope, and further give necessary and sufficient conditions under which these inequalities are facet defining. Based on these results, we develop a branch-and-cut algorithm to solve the problem.

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

## 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 [84]. 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)[68][69]. 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]. The concept of slots was proposed initially by Jinno et al. in 2008 [38], and later explored by the same authors in 2010 [87]. This can be seen as an improvement in resource utilization. We refer the reader to [44] for more information about the architectures, technologies, and control of SFONs.

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 [31]:

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;

<footnote n="1">¹ Le Havre Normandie University, LMAH, FR CNRS 3335, 76600 Le Havre, France
diarrasi@univ-lehavre.fr</footnote>

<footnote n="2">² Clermont Auvergne University, LIMOS, UMR CNRS 6158, 63178 Clermont Ferrand, France
youssouf.hadhbi@uca.fr</footnote>

<footnote n="3">³ Paris Dauphine-PSL University, LAMSADE, UMR CNRS 7243, 75775 Paris CEDEX 16, France
ridha.mahjoub@lamsade.dauphine.fr</footnote>

<footnote>* This work was supported by the French National Research Agency grant ANR-17-CE25-0006, project FLEXOPTIM.</footnote>
<figure><img src="image_3.png" /><figcaption>Fig. 1. Slot concept illustration in SFONs [77].</figcaption></figure>

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

Numerous research studies have been conducted on the RSA problem since its first appearance. The RSA is known to be an NP-hard problem [80] [83], and is more complex than the historical Routing and Wavelength Assignment (RWA) problem [34]. Various (mixed) 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 [83] where authors classified variants of the RSA problem: offline RSA which has been initiated in [63], and online or dynamic RSA which has been initiated in [88] and recently developed in [58] and [91], 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 a huge 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 [31]. 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], [63], [64], [86], [93], and recently in [75]. On the other hand, column generation techniques have been used by Klinkowski et al. in [73], Jaumard et al. in [36], and recently by Enoch in [21] 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 [65] a valid inequality based on clique inequality separable using a branch-and-bound algorithm. On the other hand, Klinkowski et al. in [66] propose a branch-and-cut-and-price method based on an edge-path formulation for the RSA problem. Recently, Fayez et al. [23], and Xuan et al. [89], 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], [86], [93]. On the other front, and due to the NP-Hardness of the C-RSA problem, we found that several heuristics [18], [51], [77], and recently in [35], and greedy algorithms [46], and metaheuristics as tabu search in [27], simulated annealing in [66], genetic algorithms in [25], [33], [34], ant colony algorithms in [41], and a hybrid meta-heuristic approach in [72], have been used to solve large sized instances of the RSA problem. Furthermore, some resseraches start using some artificial intelligence algorithms, see for example [42] and [43], and some deep-learning algorithms [8], and also machine-learning algorithms in [76], and recently in [90] and [29] to get more perefermonce. Selvakumar et al. gives a survey in [79] 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 [31] and [32] 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 [86] 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 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 [86] 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. Our contribution is then 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 [31] and [32]. We investigate the facial structure of the associated polytope. We further identify several classes of valid inequalities to obtain tighter LP bounds. Some of these inequalities are obtained by using conflict graphs related to the problem: clique inequalities, odd-hole, and lifted odd-hole inequalities. We also use the Chvatal-Gomory procedure to generate larger classes of inequalities. We then give sufficient conditions under which these inequalities are facet defining. Based on these results, we develop a Branch-and-Cut (B&C) algorithm to solve the problem [16].

## 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. In Section (4), we thoroughly investigate the theoretical properties of the C-RSA problem by providing several valid inequalities. Furthermore, a detailed polyhedral investigation is given in Section (5). We close with a brief summary of results and future outlook.

# 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 $^4 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 [37], and $K$ be a multiset $^5$ 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 $\bar{l}_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

<footnote>$^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>$^5$ We take into account that we can have several demands between the same origin-node and destination-node.</footnote>
subset of contiguous frequency slots $S_k \subset \mathbb{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 \neq k'$) with $E(p_k) \cap E(p_{k'}) \neq \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 $\mathbb{S} = \{1, 2, 3, ..., 8, 9\}$ with $\bar{s} = 9$.

<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. 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 [31]. 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 \mathbb{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 $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̄<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_c^e$ 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, \qquad (2) $$

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

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

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

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

$$ \sum_{s=w_k}^{\bar{s}} z_s^k \geq 1, \forall k \in K, \qquad (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, \qquad (8) $$

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

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

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

$$ z_s^k \in \{0, 1\}, \forall k \in K, \forall s \in \mathbb{S}. \qquad (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 \setminus \{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, \dots, 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, \dots, \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 [26] 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.
# 4 Valid Inequalities

An instance of the C-RSA is defined by a triplet $(G, K, \mathbb{S})$. Let $P(G, K, \mathbb{S})$ be the polytope, convex hull of the solutions for our cut formulation (1)-(12). In this section we provide several valid inequalities to obtain tighter LP bounds.

Throughout our proofs, we take into account that $x_e^k \le 1$ for each demand $k \in K$ and edge $e \in E$, and $z_s^k \ge 0$ for each demand $k \in K$ and slot $s \in \mathbb{S}$. Note that a slot $s \in \mathbb{S}$ is assigned to a demand $k \in K$ if and only if $\sum_{s'=s}^{\min(\bar{s}, s+w_k-1)} z_{s'}^k = 1$.

In what follows, we present several valid inequalities for $P(G, K, \mathbb{S})$. Note that some proof of validity necessitates more details that may generate an overrun of the number of authorized pages. Please feel free to contact the authors for more details about each proof.

We start this section by introducing the classes of valid inequalities that can be found using Chvatal-Gomory procedures.

## 4.1 Edge-Slot-Assignment Inequalities

**Proposition 2.** Consider an edge $e \in E$ with $K_e \neq \emptyset$. Let $s$ be a slot in $\mathbb{S}$. Then, the inequality

$$ \sum_{k'' \in K_e} \sum_{s''=s}^{\min(s+w_{k''}-1, \bar{s})} z_{s''}^{k''} \le 1, \quad (13) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Based on the non-overlapping inequality (8) and using the Chvatal-Gomory procedure, we define the following inequality.

**Proposition 3.** Consider an edge $e \in E$. Let $s$ be a slot in $\mathbb{S}$. Consider a triplet of demands $k, k', k'' \in K$ with $e \notin E_0^k \cap E_0^{k'} \cap E_0^{k''}$. Then, the inequality

$$ x_e^k + 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'} + \sum_{s''=s}^{\min(s+w_{k''}-1, \bar{s})} z_{s''}^{k''} \le 4, \quad (14) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

The inequality (14) can then be generalized for any subset of demand $\tilde{K} \subseteq K$ under certain conditions.

**Proposition 4.** Consider an edge $e \in E$, and a slot $s$ in $\mathbb{S}$. Let $\tilde{K}$ be a subset of demands of $K$ with $e \notin E_0^k$ for each demand $k \in \tilde{K}$, $(k, k') \notin K_c^e$ for each pair of demands $(k, k')$ in $\tilde{K}$, and $\sum_{k \in \tilde{K}} w_k \le \bar{s} - \sum_{k'' \in K_e \setminus \tilde{K}} w_{k''}$. Then, the inequality

$$ \sum_{k \in \tilde{K}} x_e^k + \sum_{k' \in \tilde{K}} \sum_{s'=s}^{\min(s+w_{k'}-1, \bar{s})} z_{s'}^{k'} \le |\tilde{K}| + 1, \quad (15) $$

is valid for $P(G, K, \mathbb{S})^6$.

*Proof.* See the detailed report in [16] for more information.

The inequality (15) can be strengthened as follows. Based on the inequalities (13) and (8), we strengthen the inequality (8) without modifying its right hand side as follows.

<footnote n="6">⁶ Thanks to Prof. Hervé Kerivin for its support to have an initial idea in order to define inequalities (15) and (20).</footnote>
**Proposition 5.** Consider an edge $e \in E$. Let $s$ be a slot in $\mathbb{S}$. Consider a pair of demands $k, k' \in K$ with $e \notin E_0^k \cap E_0^{k'}$ and $(k, k') \notin K_c^e$. Then, the inequality

$$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'} + \sum_{k'' \in K_e \setminus \{k, k'\}} \sum_{s'=s}^{\min(s+w_{k''}-1, \bar{s})} z_{s''}^{k''} \le 3, \quad (16)$$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Let's us generalize the inequality (16) for each edge $e$ and all slot $s \in \mathbb{S}$ and any subset of demand $\tilde{K} \subseteq K$ under certain conditions.

**Proposition 6.** Consider an edge $e \in E$, and a slot $s$ in $\mathbb{S}$. Let $\tilde{K}$ be a subset of demands of $K$ with $e \notin E_0^k$ for each demand $k \in \tilde{K}$, $(k, k') \notin K_c^e$ for each pair of demands $(k, k')$ in $\tilde{K}$, and $\sum_{k \in \tilde{K}} w_k \le \bar{s} - \sum_{k'' \in K_e \setminus \tilde{K}} w_k$.

$$\sum_{k \in \tilde{K}} x_e^k + \sum_{k \in \tilde{K}} \sum_{s'=s}^{\min(s+w_k-1, \bar{s})} z_{s'}^k + \sum_{k' \in K_e \setminus \tilde{K}} \sum_{s''=s}^{\min(s+w_{k'}-1, \bar{s})} z_{s''}^{k'} \le |\tilde{K}| + 1, \quad (17)$$

is valid for $P(G, K, \mathbb{S})$.

*Proof.*

## 4.2 Edge-Interval-Cover Inequalities

Let's now introduce some valid inequalities that can be seen as cover inequalities using some notions of cover related to our problem.

**Definition 2.** An interval $I = [s_i, s_j]$ represents a set of contiguous slots situated between the two slots $s_i$ and $s_j$ with $j \ge i + 1$ and $s_j \le \bar{s}$.

**Definition 3.** For an interval of contiguous slots $I = [s_i, s_j]$, a subset of demands $K' \subseteq K$ is said a cover for the interval $I = [s_i, s_j]$ if and only if $\sum_{k \in \tilde{K}} w_k > |I|$ and $w_k < |I|$ for each $k \in \tilde{K}$.

**Definition 4.** For an interval of contiguous slots $I = [s_i, s_j]$, a cover $\tilde{K}$ is said a minimal cover if $\tilde{K} \setminus \{k\}$ is not a cover for interval $I = [s_i, s_j]$ for each demand $k \in \tilde{K}$, i.e., $\sum_{k' \in \tilde{K} \setminus \{k\}} w_{k'} \le |I|$ for each demand $k \in \tilde{K}$.

Based on these definitions, we introduce the following inequalities.

**Proposition 7.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $j \ge i + 1$. Let $K' \subseteq K_e$ be a minimal cover for interval $I = [s_i, s_j]$ over edge $e$ with $e \notin E_0^k$ for each demand $k \in K'$. Then, the inequality

$$\sum_{k \in K'} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le |K'| - 1, \quad (18)$$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

The inequality (18) can be strengthened using an extension of each minimal cover $K' \subset K_e$ for an interval $I$ over edge $e$ as follows.
**Proposition 8.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$. Let $K' \subseteq K_e$ be a minimal cover for interval $I = [s_i, s_j]$ over edge $e$ with $e \notin E_0^k$ for each demand $k \in K'$, and $\Xi(K')$ be a subset of demands in $K_e \setminus K'$ s.t. $\Xi(K') = \{k \in K_e \setminus K' \text{ s.t. } w_k \ge w_{k'} \ \forall k' \in K'\}$. Then, the inequality

$$ \sum_{k \in K'} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{k' \in \Xi(K')} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} \le |K'| - 1, \quad (19) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Moreover, the inequality (18) can be strengthened using lifting procedures proposed by Nemhauser and Wolsey in [52] without modifying its right-hand side.

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

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

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

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

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

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

$$ - (k, k') \notin K_c^e \text{ for each pair of demands } (k, k') \text{ in } \tilde{K}. $$

Then, the inequality

$$ \sum_{k \in \tilde{K}} x_e^k + \sum_{k \in \tilde{K}} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le |\tilde{K}| - 1, \quad (20) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

As we did before for the inequality (18), the inequality (20) can be strengthened by introducing the extended version of the minimal cover $K'$ for the interval $I$ over edge $e$ as follows.

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

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

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

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

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

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

$$ - (k, k') \notin K_c^e \text{ for each pair of demands } (k, k') \text{ in } \tilde{K}, $$

$$ - w_{k'} \ge w_k \text{ for each } k \in \tilde{K} \text{ and each } k' \in \tilde{K}_e. $$
Then, the inequality

$$ \sum_{k \in \tilde{K}} x_e^k + \sum_{k \in \tilde{K}} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{k' \in \tilde{K}_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} \le 2|\tilde{K}| - 1, \quad (21) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

More general, the inequality (20) can be strengthened using lifting procedures proposed by Nemhauser and Wolsey in [52] without modifying its right-hand side.

**Remark 1.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots with $s_i + 1 \le s_j, s''$ be a slot in $\mathbb{S}$, and $\tilde{K}$ be a subset of demands in $K$ satisfying the conditions of the two inequalities (17) and (20). We ensure that the inequality (17) can never dominate the inequality (20).

## 4.3 Edge-Interval-Clique Inequalities

In what follows, we need to introduce some notions of graph theory to provide some valid inequalities for $P(G, K, \mathbb{S})$.

**Definition 5.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $s_i \le s_j - 1$. Consider the conflict graph $\tilde{G}_I^e$ defined as follows. For each demand $k \in K$ with $w_k \le |I|$ and $e \notin E_0^k$, consider a node $v_k$ in $\tilde{G}_I^e$. Two nodes $v_k$ and $v_{k'}$ are linked by an edge in $\tilde{G}_I^e$ if $w_k + w_{k'} > |I|$ and $(k, k') \notin K_c^e$. This is equivalent to say that two linked nodes $v_k$ and $v_{k'}$ means that the two demands $k, k'$ define a minimal cover for the interval $I$ over edge $e$.

For an edge $e \in E$, the conflict graph $\tilde{G}^e$ is a threshold graph with threshold value equals to $t = \bar{s} - \sum_{k'' \in K_e} w_{k''}$ s.t. for eachnode $v_k$ with $e \notin E_0^k \cup E_1^k$, we associate a positive weight $\tilde{w}_{v_k} = w_k$ s.t. all two nodes $v_k$ and $v_{k'}$ are linked by an edge if and only if $\tilde{w}_{v_k} + \tilde{w}_{v_{k'}} > t$ which is equivalent to the conflict graph $\tilde{G}^e$.

**Proposition 11.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots. Let $C$ be a clique in the conflict graph $\tilde{G}_I^e$ with $|C| \ge 3$, and $\sum_{v_k \in C} w_k \le \bar{s} - \sum_{k' \in K_e \setminus C} w_{k'}$. Then, the inequality

$$ \sum_{v_k \in C} x_e^k + \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le |C| + 1, \quad (22) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

**Remark 2.** Consider an edge $e$ and an interval of contiguous slots $I = [s_i, s_j]$. Let $\tilde{K}$ be a subset of demands in $K$ satisfying the conditions of validity of the inequalities (17) and (22). Then, the inequality (22) is dominated by the inequality (17) associated with slot $s'' = s_i + \min_{k \in \tilde{K}} w_k + 1$ if and only if $|\{s_i + w_k, \dots, s_j\}| \le w_k$ for each demand $k \in \tilde{K}$.

**Remark 3.** Consider an edge $e$ and an interval of contiguous slots $I = [s_i, s_j]$. Let $\tilde{K}$ be a subset of demands in $K$ satisfying the conditions of validity of the inequalities (17) and (22). Then, the inequality (22) dominates the inequality (17) associated with each slot $s'' \in I$ if and only if $|\{s_i + w_k - 1, \dots, s_j\}| \ge w_k$ for each demand $k \in \tilde{K}$ and $s'' \in \{s_i + \max_{k' \in \tilde{K}} w_k - 1, \dots, s_j - \max_{k' \in \tilde{K}} w_k + 1\}$.

Moreover, the inequality (22) can be strengthened as follows.
**Proposition 12.** Consider an edge $e \in E$. Let $I = [s_i, s_j]$ be an interval of contiguous slots. Let $C$ be a clique in the conflict graph $\tilde{G}_I^e$ with $|C| \ge 3$, and $\sum_{v_k \in C} w_k \le \bar{s} - \sum_{k' \in K_e \setminus C} w_{k'}$. Let $C_e \subseteq K_e \setminus C$ be a clique in the conflict graph $\tilde{G}_I^e$ s.t. $w_k + w_{k'} \ge |I| + 1$ for each $v_k \in C$ and $v_{k'} \in C_e$. Then, the inequality

$$ \sum_{v_k \in C} x_e^k + \sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \sum_{v_{k'} \in C_e} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} \le |C| + 1, \quad (23) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Looking to the definition of the inequality (22), we detected that there may exist some cases that we can face that are not covered by the inequality (22). For this, we provide the following inequality and its generalization.

## 4.4 Interval-Clique Inequalities

**Proposition 13.** Consider an interval of contiguous slots $I = [s_i, s_j]$ in $\mathbb{S}$ with $s_i \le s_j - 1$. Let $k, k'$ be a pair of demands in $K$ with $E_1^k \cap E_1^{k'} \ne \emptyset$, and $w_k \le |I|$, and $w_{k'} \le |I|$, and $w_k + w_{k'} > |I|$. Then, the inequality

$$ \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 1, \quad (24) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

**Definition 6.** Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $s_i \le s_j - 1$. Consider the conflict graph $\tilde{G}_I^E$ defined as follows. For each demand $k \in K$ with $w_k \le |I|$, consider a node $v_k$ in $\tilde{G}_I^E$. Two nodes $v_k$ and $v_{k'}$ are linked by an edge in $\tilde{G}_I^E$ if $w_k + w_{k'} > |I|$ and $E_1^k \cap E_1^{k'} \ne \emptyset$.

**Proposition 14.** Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $s_i \le s_j - 1$, and $C$ be a clique in the conflict graph $\tilde{G}_I^E$ with $|C| \ge 3$. Then, the inequality

$$ \sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le 1, \quad (25) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

## 4.5 Interval-Odd-Hole Inequalities

**Proposition 15.** Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $s_i \le s_j - 1$, and $H$ be an odd-hole $H$ in the conflict graph $\tilde{G}_I^E$ with $|H| \ge 5$. Then, the inequality

$$ \sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le \frac{|H| - 1}{2}, \quad (26) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

The inequality (26) can be strengthened without modifying its right-hand side by combining the inequality (25) and (26) as follows.
**Proposition 16.** Consider an interval of contiguous slots $I = [s_i, s_j] \subseteq \mathbb{S}$ with $s_i \le s_j - 1$. Let $H$ be an odd-hole $H$ in the conflict graph $\tilde{G}_I^E$, and $C$ be a clique in the conflict graph $\tilde{G}_I^E$ with

- $|H| \ge 5$,

- and $|C| \ge 3$,

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

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

Then, the inequality

$$ \sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \frac{|H|-1}{2} \sum_{v_{k'} \in C} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} \le \frac{|H|-1}{2}, \quad (27) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

## 4.6 Edge-Slot-Assignment-Clique Inequalities

Taking into account the non-overlapping inequalities (8), we define another conflict graph totally different compared with the conflict graphs introduced previously.

**Definition 7.** Let $\tilde{G}_S^e$ be a conflict graph defined as follows. For each slot $s \in \{w_k, ..., \bar{s}\}$ and demand $k \in K$ with $e \notin E_0^k$, consider a node $v_{k,s}$ in $\tilde{G}_S^e$. Two nodes $v_{k,s}$ and $v_{k',s'}$ are linked by an edge in $\tilde{G}_S^e$ if and only if

- $k = k'$,

- or $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} \ne \emptyset$ if $k \ne k'$ and $(k, k') \notin K_c^e$.

The conflict graph $\tilde{G}_S^e$ is not a perfect graph given that some nodes $v_{k,s}$ and $v_{k',s'}$ are linked even if the $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} = \emptyset$, i.e., when $k = k'$.

**Proposition 17.** Consider an edge $e \in E$. Let $C$ be a clique in the conflict graph $\tilde{G}_S^e$ with $|C| \ge 3$, and $\sum_{k \in C} w_k \le \bar{s} - \sum_{k' \in K_c \setminus C} w_{k'}$. Then, the inequality

$$ \sum_{v_{k,s} \in C} (x_e^k + z_s^k) \le |C| + 1, \quad (28) $$

is valid for $P'(G, K, \mathbb{S}) = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{s=w_k}^{\bar{s}} z_s^k = 1 \text{ for all } k \in K\}$.

*Proof.* See the detailed report in [16] for more information.

This gives us an idea about new non-overlapping inequalities defined as follows.

**Proposition 18.** Consider an edge $e$, and a pair of demands $k, k' \in K$ with $e \notin E_0^k \cup E_0^{k'}$. Let $s$ be a slot in $\{w_k, ..., \bar{s}\}$. Then, the inequality

$$ x_e^k + x_e^{k'} + z_s^k + \sum_{s''=s-w_k+1}^{\min(s+w_{k'}-1, \bar{s})} z_{s''}^{k'} \le 3, \quad (29) $$

is valid for $P''(G, K, \mathbb{S}) = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{s=w_k}^{\bar{s}} z_s^k = 1 \ \& \ \sum_{s=w_{k'}}^{\bar{s}} z_{s'}^{k'} = 1\}$.

*Proof.* See the detailed report in [16] for more information.

**Remark 4.** The inequality (29) is a particular case of inequality (28) for a clique $C = \{v_{k,s}\} \cup \{v_{k',s'} \in \tilde{G}_S^e \text{ s.t. } \{s' - w_k + 1, ..., s'\} \cap \{s - w_k + 1, ..., s\} \ne \emptyset\}$.

**Remark 5.** The inequality (28) associated with a clique $C$ over edge $e$, it is dominated by the inequality (22) associated with an interval $I = [s_i, s_j]$ and the subset of demands $\tilde{K}$ over edge $e$ iff

- $\tilde{s} \in \{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\}$ for each pair of nodes $(v_{k,s}, v_{k',s'})$ in $C$,

- and $\min_{v_{k,s} \in C} (s - w_k + 1), \max_{v_{k,s} \in C} s \} \subset I$.

*Proof.* See the detailed report in [16] for more information.
## 4.7 Slot-Assignment-Clique Inequalities

On the other hand, we detected that there may exist some cases that are not covered by the inequalities (17) and (28). For this, we provide the following definition of a conflict graph and its associated inequality.

**Definition 8.** Let $\tilde{G}_S^E$ be a conflict graph defined as follows. For all slot $s \in \{w_k, ..., \bar{s}\}$ and demand $k \in K$, consider a node $v_{k,s}$ in $\tilde{G}_S^E$. Two nodes $v_{k,s}$ and $v_{k',s'}$ are linked by an edge in $\tilde{G}_S^E$ iff $E_1^k \cap E_{k'}^{k'} \neq \emptyset$ and $\{s - w_k + 1, ..., s\} \cap \{s' - w_{k'} + 1, ..., s'\} \neq \emptyset$.

**Proposition 19.** Let $C$ be a clique in conflict graph $\tilde{G}_S^E$ with $|C| \ge 3$. Then, the inequality

$$ \sum_{v_{k,s} \in C} z_s^k \le 1, \qquad (30) $$

is valid for $P(G, K, \mathcal{S})$.

*Proof.* See the detailed report in [16] for more information.

**Remark 6.** The inequality (30) associated with a clique $C$, it is dominated by the inequality (25) associated with an interval $I = [s_i, s_j]$ and the subset of demands $\tilde{K}$ if and only if $[\min_{v_{k,s} \in C}(s - w_k + 1), \max_{v_{k,s} \in C}s] \subset I$ and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'}) \in C$, and $2w_k \ge |I| + 1$ and $w_k \le |I|$ for each $v_k \in C$.

*Proof.* See the detailed report in [16] for more information.

## 4.8 Slot-Assignment-Odd-Hole Inequalities

**Proposition 20.** Let $H$ be an odd-hole in the conflict graph $\tilde{G}_S^E$ with $|H| \ge 5$. Then, the inequality

$$ \sum_{v_{k,s} \in H} z_s^k \le \frac{|H| - 1}{2}, \qquad (31) $$

is valid for $P(G, K, \mathcal{S})$.

*Proof.* See the detailed report in [16] for more information.

**Remark 7.** The inequality (31) is dominated by the inequality (26) if and only if there exists an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

$$ - [ \min_{v_{k,s} \in H \cup C} (s - w_k + 1), \max_{v_{k,s} \in H \cup C} ] \subset I, $$

$$ - \text{and } w_k + w_{k'} \ge |I| + 1 \text{ for each } (v_k, v_{k'}) \text{ linked in } H, $$

$$ - \text{and } 2w_k \ge |I| + 1 \text{ and } w_k \le |I| \text{ for each } v_k \in H. $$

The inequality (31) can be strengthened without modifying its right hand side by combining the inequality (31) and (30) as follows.

**Proposition 21.** Let $H$ be an odd-hole, and $C$ be a clique in the conflict graph $\tilde{G}_S^E$ with

$$ - |H| \ge 5, $$

$$ - \text{and } |C| \ge 3, $$

$$ - \text{and } H \cap C = \emptyset, $$

$$ - \text{and the nodes } (v_{k,s}, v_{k',s'}) \text{ are linked in } \tilde{G}_S^E \text{ for all } v_{k,s} \in H \text{ and } v_{k',s'} \in C. $$

Then, the inequality

$$ \sum_{v_{k,s} \in H} z_s^k + \frac{|H| - 1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} \le \frac{|H| - 1}{2}, \qquad (32) $$

is valid for $P(G, K, \mathcal{S})$.
*Proof.* See the detailed report in [16] for more information.

**Remark 8.** The inequality (32) is dominated by the inequality (27) if and only if there exists an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

$$- [ \min_{v_{k,s} \in H \cup C} (s - w_k + 1), \max_{v_{k,s} \in H \cup C} ] \subset I,$$

- and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'})$ linked in $H$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'})$ linked in $C$,

- and $w_k + w_{k'} \ge |I| + 1$ for each $v_k \in H$ and $v_{k'} \in C$,

- and $2w_k \ge |I| + 1$ and $w_k \le |I|$ for each $v_k \in H$,

- and $2w_{k'} \ge |I| + 1$ and $w_{k'} \le |I|$ for each $v_{k'} \in C$.

## 4.9 Non-Compatibility-Clique Inequalities

Let us now introduce some valid inequalities that are related to the routing sub-problem due to the transmission-reach constraint.

**Definition 9.** For a demand $k$, two edges $e = ij \notin E_0^k \cap E_1^k$, $e' = lm \notin E_0^k \cap E_1^k$ are said non-compatible edges if and only if the lengths of $(o_k, d_k)$-paths formed by $e = ij$ and $e' = lm$ together are greater than $\bar{l}_k$.

Note that we are able to determine the non-compatible edges for each demand $k$ in polynomial time using shortest-path algorithms.

**Proposition 22.** Consider an edge $e \in E$. Let $(k, k')$ be a pair of non-compatible demands for the edge $e$. Then, the inequality

$$x_e^k + x_{e'}^{k'} \le 1, \qquad (33)$$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

**Proposition 23.** Consider a demand $k \in 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, \qquad (34)$$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Based on the inequalities (33) and (34), we introduce the following conflict graph.

**Definition 10.** Let $\tilde{G}_E^K$ be a conflict graph defined as follows. For each demand $k$ and edge $e \notin 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 \neq k'$: $k$ and $k'$ are non compatible demands for edge $e$.

**Proposition 24.** Let $C$ be a clique in $\tilde{G}_E^K$. Then, the inequality

$$\sum_{v_e^k \in C} x_e^k \le 1, \qquad (35)$$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.
## 4.10 Non-Compatibility-Odd-Hole Inequalities

**Proposition 25.** Let $H$ be an odd-hole in the conflict graph $\tilde{G}_E^K$ with $|H| \ge 3$. Then, the inequality

$$ \sum_{v_e^k \in H} x_e^k \le \frac{|H| - 1}{2}, \qquad (36) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

The inequality (36) can be strengthened without modifying its right hand side by combining the inequality (36) and (35) as follows.

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

- $|H| \ge 5$,

- and $|C| \ge 3$,

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

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

Then, the inequality

$$ \sum_{v_e^k \in H} x_e^k + \frac{|H| - 1}{2} \sum_{v_{e'}^{k'} \in C} x_{e'}^{k'} \le \frac{|H| - 1}{2}, \qquad (37) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

On the other hand, let's now provide some inequalities related to the capacity constraint.

## 4.11 Edge-Capacity-Cover Inequalities

**Proposition 27.** Consider an edge $e$ in $E$. Then, the inequality

$$ \sum_{k \in K \setminus K_e} w_k x_e^k \le \bar{s} - \sum_{k' \in K_e} w_{k'}, \qquad (38) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Based on this, we introduce the following definitions.

**Definition 11.** For an edge $e \in E$, a subset of demands $C \subseteq K$ with $e \notin E_0^k \cap E_1^k$. For each demand $k \in C$, is said a cover for the edge $e$ if $\sum_{k \in C} w_k > \bar{s} - \sum_{k' \in K_e} w_{k'}$.

**Definition 12.** For an edge $e$ in $E$, a cover $C$ is said a minimal cover if $C \setminus \{k\}$ is not a cover for all $k \in C$, i.e., $\sum_{k' \in C \setminus \{k\}} w_{k'} \le \bar{s} - \sum_{k'' \in K_e} w_{k''}$.

**Proposition 28.** Consider an edge $e$ in $E$. Let $C$ be a minimal cover in $K$ for the edge $e$. Then, the inequality

$$ \sum_{k \in C} x_e^k \le |C| - 1, \qquad (39) $$

is valid for $P(G, K, \mathbb{S})$.
*Proof.* See the detailed report in [16] for more information.

We verified that the inequality (39) can be easily strengthened by using its extended format which we call extended minimal cover for an edge e as follows.

**Proposition 29.** Consider an edge e in E. Let C be a minimal cover in K for the edge e, and $\Xi(C)$ be a subset of demands in $K \setminus C \cup K_e$ where $\Xi = \{k \in K \setminus C \cup K_e : e \notin E_0^k \text{ and } w_k \ge w_{k'} \ \forall k' \in C\}$. Then, the inequality

$$ \sum_{k \in C} x_e^k + \sum_{k' \in \Xi(C)} x_e^{k'} \le |C| - 1, \quad (40) $$

is valid for $P(G, K, \mathbb{S})$.

*Proof.* See the detailed report in [16] for more information.

Furthermore, the inequality (39) can have a more generalized strengthening format using lifting procedures proposed by Nemhauser and Wolsey in [52].

In what follows, 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>

# 5 Facial Investigation

In this section, we investigate the facial structure of our polytope $P(G, K, \mathbb{S})$ by characterizing when the valid inequalities already introduced in the Section (4), are facets defining for $P(G, K, \mathbb{S})$. We refer the reader to the first part of our polyhedral study detailed in [17] (polytope dimension, and facial structure of the trivial inequalities).

## 5.1 Slot-Assignment-Clique Inequalities

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

- C is a maximal clique in the conflict graph $\tilde{G}_S^E$,

- and there does not exist an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with
• $[\min_{v_{k,s} \in C} (s - w_k + 1), \max_{v_{k,s} \in C} s] \subset I,$

• and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'}) \in C,$

• and $2w_k \ge |I| + 1$ and $w_k \le |I|$ for each $v_k \in C.$

**Proof. Necessity.**

If $C$ is a not maximal clique in the conflict graph $\tilde{G}_S^E$, this means that the inequality (30) can be dominated by another inequality associated with a clique $C'$ s.t. $C \subset C'$ without changing its right hand side. Moreover, if there exists an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

- $[\min_{v_{k,s} \in C} (s - w_k + 1), \max_{v_{k,s} \in C} s] \subset I,$

- and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'}) \in C,$

- and $2w_k \ge |I| + 1$ and $w_k \le |I|$ for each $v_k \in C.$

Then, the inequality (30) is dominated by the inequality (25). As a result, the inequality (30) cannot be facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

Let $F_C^{\tilde{G}_S^E}$ denote the face induced by the inequality (30), which is given by

$$F_C^{\tilde{G}_S^E} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_{k,s} \in C} z_s^k = 1\}.$$

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

- 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 \ne \emptyset$ (non-overlapping constraint),

- and there is one pair of demand $k$ and slot $s$ from the clique $C$ (i.e., $v_{k,s} \in C$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S^1$, i.e., $s \in S_k^1$ for a node $v_{k,s} \in C$, and $s' \notin S_{k'}^1$ for all $v_{k',s'} \in C \setminus \{v_{k,s}\}$.

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

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

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

- 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 $\sigma_s^k$ are equivalents for all $v_{k,s} \in C.$

We first show that $\mu_e^k = 0$ for each edge $e \in E \setminus (E_0^k \cup E_1^k)$ for each demand $k \in K$. 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'^1 = (E'^1, S'^1)$ in which

- 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 \mathbb{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),

- $\{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 \cup \{e\}) \cap E_{k'}'^1 \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the edge $e$ in the set of edges $E_k'^1$ selected to route the demand $k$ in the solution $S'^1$),

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

- and there is one pair of demand $k$ and slot $s$ from the clique $C$ (i.e., $v_{k,s} \in C$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S'^1$, i.e., $s \in S_k'^1$ for a node $v_{k,s} \in C$, and $s' \notin S_{k'}'^1$ for all $v_{k',s'} \in C \setminus \{v_{k,s}\}$).

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

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

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

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

- 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 \mathbb{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),

- and $\{s' - w_k + 1, ..., s'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k' \in K$ and $s'' \in S_{k'}''^1$ with $E_k''^1 \cap E_{k'}''^1 \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $S_k''^1$ assigned to the demand $k$ in the solution $S''^1$),
- and there is one pair of demand k and slot s from the clique C (i.e., $v_{k,s} \in C$ s.t. the demand k selects the slot s as last-slot in the solution $S^{\text{last}}$, i.e., $s \in S_k^{\text{last}}$ for a node $v_{k,s} \in C$, and $s' \notin S_k^{\text{last}}$ for all $v_{k',s'} \in C \setminus \{v_{k,s}\}$.

$S^{\text{last}}$ is clearly feasible for the problem given that it satisfies all the constraints of cut formulation (2)-(12). Hence, the corresponding incidence vector $(x^{\text{last}}, z^{\text{last}})$ is belong to $F$ and then to $F_C^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in C} z_s^k = 1$. Based on this, we distinguish two cases:

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

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

The corresponding incidence vector $(x^{\text{last}}, z^{\text{last}})$ is belong to $F$ and then to $F_C^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in C} z_s^k = 1$. We then obtain that

$$ \mu x^{\text{last}} + \sigma z^{\text{last}} = \mu x^{\text{last}} + \sigma z^{\text{last}} = \mu x^{\text{last}} + \sigma z^{\text{last}} + \sigma_{s'}^k. $$

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

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

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

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

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

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

The corresponding incidence vector $(x^{\text{last}}, z^{\text{last}})$ is belong to $F$ and then to $F_C^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in C} z_s^k = 1$. We have so

$$ \mu x^{\text{last}} + \sigma z^{\text{last}} = \mu x^{\text{last}} + \sigma z^{\text{last}} = \mu x^{\text{last}} + \sigma z^{\text{last}} + \sigma_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e \in E_k^{\text{last}}} \mu_{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k^{\text{last}}} \mu_{e'} $$

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $v_{k,s'} \notin C$ given that $\mu_k^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$ with $v_{k,s'} \notin C$ s.t. we find

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

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

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

Consequently, we conclude that

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

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

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

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

- and there is one pair of demand $k$ and slot $s$ from the clique $C$ (i.e., $v_{k,s} \in C$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $\tilde{S}^1$, i.e., $s \in S_k^1$ for a node $v_{k,s} \in C$, and $s'' \notin S_{k'}^1$ for all $v_{k',s''} \in C \setminus \{v_{k,s}\}$.

$\tilde{S}^1$ 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}^1}, z^{\tilde{S}^1})$ is belong to $F$ and then to $F_C^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in C} z_s^k = 1$. Based on this,

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

The corresponding incidence vector $(x^{S^4}, z^{S^4})$ is belong to $F$ and then to $F_C^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in C} z_s^k = 1$. We then obtain that

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

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

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

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

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

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

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all pairs } (v_{k,s}, v_{k',s'}) \in C. $$

Consequently, we obtain that $\sigma_s^k = \rho$ for all pairs $v_{k,s} \in C$.

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

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

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

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

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

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

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

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

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

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

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

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 } v_{k,s} \in C, \\ 0, & \text{if } v_{k,s} \notin C. \end{cases} $$

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

## 5.2 Interval-Clique Inequalities

**Theorem 2.** Let $I = [s_i, s_j]$ be an interval of contiguous slots in $[1, \bar{s}]$ with $s_i \le s_j - 1$, and $C$ be a clique in the conflict graph $\tilde{G}_I^E$ with $|C| \ge 3$. Then, the inequality (25) is facet defining for $P(G, K, \mathbb{S})$ if and only if

- $C$ is a maximal clique in the conflict graph $\tilde{G}_I^E$,

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

• $w_k + w_{k'} \ge |I'|$ for each $k, k' \in C$,

• $w_k \le |I'|$ and $2w_k \ge |I'| + 1$ for each $k \in C$.

**Proof. Necessity.**

We distinguish two cases

- if there exists a clique $C'$ that contains all the demands $k \in C$. Then, the inequality (25) induced by the clique $C$ is dominated by another inequality (25) induced by the clique $C'$. Hence, the inequality (25) cannot be facet defining for $P(G, K, \mathbb{S})$.

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

• $w_k + w_{k'} \ge |I'|$ for each $k, k' \in C$,

• $w_k \le |I'|$ and $2w_k \ge |I'| + 1$ for each $k \in C$.

This means that the inequality (25) induced by the clique $C$ for the interval $I$ is dominated by the inequality (25) induced by the clique $C$ for the interval $I'$. Hence, the inequality (25) cannot be facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

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

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

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

- 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 \neq \emptyset$ (non-overlapping constraint),

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

Obviously, $S^5$ 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^5}, z^{S^5})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_C^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 1$. As a result, $F_C^{\tilde{G}_I^E}$ is not empty (i.e., $F_{C'}^{\tilde{G}_I^E} \neq \emptyset$). Furthermore, given that $s \in \{s_i + w_k - 1, ..., s_j\}$ for each $v_k \in C$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $C$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ for each $s \in S_k$ and each $v_k \in C$. This means that $F_C^{\tilde{G}_I^E} \neq P(G, K, \mathbb{S})$. We denote the inequality $\sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le 1$ by $\alpha x + \beta z \le \lambda$. Let $\mu x + \sigma z \le \tau$ be a valid inequality that is facet defining $F$ of $P(G, K, \mathbb{S})$. Suppose that $F_C^{\tilde{G}_I^E} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \mu x + \sigma z = \tau\}$. We show that there exist $\rho \in \mathbb{R}$ and $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (s.t. $\gamma_1 \in \mathbb{R}, \sum_{k \in K} |E_0^k|, \gamma_2 \in \mathbb{R}, \sum_{k \in K} |E_1^k|, \gamma_3 \in \mathbb{R}, \sum_{k \in K} (w_k - 1)$) s.t. $(\mu, \sigma) = \rho(\alpha, \beta) + \gamma Q$, and that

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

- 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 $\sigma_s^k$ are equivalents for all $v_k \in C$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$.

We first show that $\mu_e^k = 0$ for each edge $e \in E \setminus (E_0^k \cup E_1^k)$ for each demand $k \in K$. 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'^5 = (E'^5, S'^5)$ in which

- 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 \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'^5} |\{s' \in S_k'^5, 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'^5$ of demand $k$ in the solution $S'^5$, i.e., $\sum_{e' \in E_k'^5} l_{e'} + l_e \le \bar{l}_k$. As a result, $E_k'^5 \cup \{e\}$ is a feasible path for the demand $k$,

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

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

- and 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).
The corresponding incidence vector $(x^{S^6}, z^{S^6})$ is belong to $F$ and then to $F_C^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = 1$. It follows that

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

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

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

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

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

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

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

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

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

$$ \mu x^{S^{\#5}} + \sigma z^{S^{\#5}} = \mu x^{S^7} + \sigma z^{S^7} = \mu x^{S^{\#5}} + \sigma z^{S^{\#5}} + \sigma_{s'}^k. $$

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

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

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

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

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

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

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in C$ given that $\mu_e^k = 0$ for all the demand $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$.

The slot $s'$ is chosen arbitrarily for the demand $k$, we iterate the same procedure for all feasible slots in $\{w_k, ..., \bar{s}\}$ of demand $k$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in C$ s.t. we find

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

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

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

Consequently, we conclude that

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

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

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

- a set of last-slots $\tilde{S}_k^5$ is assigned to each demand $k \in K$ along each edge $e \in \tilde{E}_k^5$ with $|\tilde{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 \tilde{S}_k^5$ and $s'' \in \tilde{S}_{k'}^5$ with $\tilde{E}_k^5 \cap \tilde{E}_{k'}^5 \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^5} |\{s' \in \tilde{S}_k^5, 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^5$ with $\tilde{E}_k^5 \cap \tilde{E}_{k'}^5 \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $\tilde{S}_{k'}^5$ assigned to the demand $k'$ in the solution $\tilde{S}^5$),
- and there is one demand $k$ from the clique $C$ (i.e., $v_k \in C$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $\tilde{S}^5$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in \tilde{S}_k^5$ for a node $v_k \in C$, and for each $s' \in \tilde{S}_{k'}^5$ for all $v_{k'} \in C \setminus \{v_k\}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$.

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

- without changing the paths established in $\tilde{S}^5$: we derive a solution $S^8 = (E^8, S^8)$ from the solution $\tilde{S}^5$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $\tilde{S}^5$ (i.e., $E_k^8 = \tilde{E}_k^5$ for each $k \in K$), and also the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^5$ remain the same in $S^8$, i.e., $\tilde{S}_{k'}^5 = S_k^8$ for each demand $k'' \in K \setminus \{k, k'\}$, and $S_{k'}^8 = \tilde{S}_{k'}^5 \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^5$ with $s \in \{s_i + w_k + 1, ..., s_j\}$ and $\tilde{s} \notin \{s_i + w_k + 1, ..., s_j\}$ for the demand $k$ with $v_k \in C$ s.t. $S_k^8 = (\tilde{S}_k^5 \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'}^8$ with $E_k^8 \cap E_{k'}^8 \neq \emptyset$. The solution $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 \mathbb{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).

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

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

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

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

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

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

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

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all pairs } (v_k, v_{k'}) \in C $$

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

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

Consequently, we obtain that $\sigma_s^k = \rho$ for all $v_k \in C$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$.

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

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

$$ \text{As a result } (\mu, \sigma) = \sum_{v_k \in C} \sum_{s=s_i+w_k-1}^{s_j} \rho \beta_s^k + \gamma Q. $$
## 5.3 Interval-Odd-Hole Inequalities

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

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

- and there does not exist a node $v_{k'} \notin H$ in $\tilde{G}_I^E$ s.t. $v_{k'}$ is linked with all nodes $v_k \in H$,

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

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

We distinguish the following cases:

- if for a node $v_{k'} \notin H$ in $\tilde{G}_I^E$, there exists a node $v_k \in H$ s.t. the induced graph $\tilde{G}_I^E((H \setminus \{v_k\}) \cup \{v_{k'}\})$ contains an odd-hole $H' = (H \setminus \{v_k\}) \cup \{v_{k'}\}$. This implies that the inequality (26) can be dominated by doing some lifting procedures using the following valid inequalities

$$ \sum_{v_k \in H} \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^k \le \frac{|H|-1}{2}, \\ \sum_{v_{k'} \in H'} \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} \le \frac{|H|-1}{2}, $$

as follows

$$ \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^k + \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} + 2 \sum_{v_{k''} \in H \setminus \{k,k'\}} \sum_{s''=s_i+w_{k''}-1}^{s_j} z_{s''}^{k''} \le |H|-1. $$

By adding the sum $\sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'}$ to the previous inequality, we obtain

$$ \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^k + 2 \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} + 2 \sum_{v_{k''} \in H \setminus \{k,k'\}} \sum_{s''=s_i+w_{k''}-1}^{s_j} z_{s''}^{k''} \le |H|-1 + \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} $$

We know that $\sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} \le 1$, it follows that

$$ \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^k + 2 \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} + 2 \sum_{v_{k''} \in H \setminus \{k,k'\}} \sum_{s''=s_i+w_{k''}-1}^{s_j} z_{s''}^{k''} \le |H|. $$

By dividing the last inequality by 2, we obtain that

$$ \sum_{s'=s_i+w_{k'-1}}^{s_j} \frac{1}{2} z_{s'}^k + \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} + \sum_{v_{k''} \in H \setminus \{k,k'\}} \sum_{s''=s_i+w_{k''}-1}^{s_j} z_{s''}^{k''} \le \lfloor \frac{|H'|}{2} \rfloor. $$

Given that $H' = (H \setminus \{k\}) \cup \{k'\}$ s.t. $|H'| = |H|$, and $|H|$ is an odd number which implies that

$$ \lfloor \frac{|H|}{2} \rfloor = \frac{|H|-1}{2}. $$

$$ \sum_{s'=s_i+w_{k'-1}}^{s_j} \frac{1}{2} z_{s'}^k + \sum_{v_{k'} \in H'} \sum_{s''=s_i+w_{k''}-1}^{s_j} z_{s''}^{k'} \le \frac{|H'|-1}{2}. $$

That which was to be demonstrated.

- if there exists a node $v_{k'} \in H$ in $\tilde{G}_I^E$ s.t. $v_{k'}$ is linked with all nodes $v_k \in H$. As a result, the inequality (26) is dominated by the following inequality

$$ \sum_{v_k \in H} \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^k + \frac{|H|-1}{2} \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s''}^{k'} \le \frac{|H|-1}{2}. $$
- if there exists an interval $I'$ of contiguous slots with $I \subset I'$ s.t. $H$ defines also an odd-hole in the associated conflict graph $\tilde{G}_I^E$. This implies that the inequality (26) induced by the odd-hole $H$ for the interval $I$ is dominated by the inequality (26) induced by the same odd-hole $H$ for the interval $I'$ given that $\{s_i + w_k - 1, ..., s_j\} \subset I'$ for each $k \in H$. As a result, the inequality (26) is not facet defining for $P(G, K, \mathbb{S})$.

If no one of these two cases, the inequality (26) can never be dominated by another inequality without changing its right-hand side.

**Sufficiency.**

Let $F_H^{\tilde{G}_I^E}$ denote the face induced by the inequality (26), which is given by

$$F_H^{\tilde{G}_I^E} = \{(x, z) \in P(G, K, \mathbb{S}) : \sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}\}.$$

In order to prove that inequality $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le \frac{|H|-1}{2}$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_H^{\tilde{G}_I^E}$ is a proper face, and $F_H^{\tilde{G}_I^E} \ne P(G, K, \mathbb{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 \ne \emptyset$ (non-overlapping constraint),

- and there is $\frac{|H|-1}{2}$ demands $\tilde{H}$ from the odd-hole $H$ (i.e., $v_k \in \tilde{H} \subset H$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^9$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^9$ for each node $v_k \in \tilde{H}$, and for each $s' \in S_{k'}^9$ for all $v_{k'} \in H \setminus \tilde{H}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$.

Obviously, $S^9$ 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^9}, z^{S^9})$ is belong to $P(G, K, \mathbb{S})$ and then to $F_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. As a result, $F_H^{\tilde{G}_I^E}$ is not empty (i.e., $F_H^{\tilde{G}_I^E} \ne \emptyset$). Furthermore, given that $s \in \{s_i + w_k - 1, ..., s_j\}$ for each $v_k \in H$, this means that there exists at least one feasible slot assignment $S_k$ for the demands $k$ in $H$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ for each $s \in S_k$ and each $v_k \in H$. This means that $F_H^{\tilde{G}_I^E} \ne P(G, K, \mathbb{S})$. We denote the inequality $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le \frac{|H|-1}{2}$ by $\alpha x + \beta z \le \lambda$. Let $\mu x + \sigma z \le \tau$ be a valid inequality that is facet defining $F$ of $P(G, K, \mathbb{S})$. Suppose that $F_H^{\tilde{G}_I^E} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \mu x + \sigma z = \tau\}$. We show that there exist $\rho \in \mathbb{R}$ and $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (s.t. $\gamma_1 \in \mathbb{R}^{\sum_{k \in K} |E_k^k|}$, $\gamma_2 \in \mathbb{R}^{\sum_{k \in K} |E_k^{\prime 9}|}$, $\gamma_3 \in \mathbb{R}^{\sum_{k \in K} (w_k - 1)}$) s.t. $(\mu, \sigma) = \rho(\alpha, \beta) + \gamma Q$, and that

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

- 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 $\sigma_s^k$ are equivalents for all $v_k \in H$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$.

We first show that $\mu_e^k = 0$ for each edge $e \in E \setminus (E_0^k \cup E_1^k)$ for each demand $k \in K$. 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'^9 = (E'^9, S'^9)$ in which

- 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 \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'^9} |\{s' \in S_k'^9, 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'^9$ of demand $k$ in the solution $S'^9$, i.e., $\sum_{e' \in E_k'^9} l_{e'} + l_e \le \bar{l}_k$. As a result, $E_k'^9 \cup \{e\}$ is a feasible path for the demand $k$,
- and there is $\frac{|H|-1}{2}$ demands $\tilde{H}$ from the odd-hole $H$ (i.e., $v_k \in \tilde{H} \subset H$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{\prime 9}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{\prime 9}$ for each node $v_k \in \tilde{H}$, and for each $s' \in S_{k'}^{\prime 9}$ for all $v_{k'} \in H \setminus \tilde{H}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$.

$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 $F$ and then to $F_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. Based on this, we derive a solution $S^{10}$ obtained from the solution $S^{\prime 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^{10} = E_k^{\prime 9} \cup \{e\}$. The last-slots assigned to the demands $K$, and paths assigned the set of demands $K \setminus \{k\}$ in $S^{\prime 9}$ remain the same in the solution $S^{10}$, i.e., $S_k^{10} = S_k^{\prime 9}$ for each $k \in K$, and $E_{k'}^{10} = E_{k'}^{\prime 9}$ for each $k' \in K \setminus \{k\}$. $S^{10}$ is clearly feasible given that

- and 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_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. It follows that

$$\mu x^{S^{\prime 9}} + \sigma z^{S^{\prime 9}} = \mu x^{S^{10}} + \sigma z^{S^{10}} = \mu x^{S^{\prime 9}} + \mu_e^k + \sigma z^{S^{\prime 9}}.$$

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

Let's us show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in H$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in H$. For that, 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 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 there is $\frac{|H|-1}{2}$ demands $\tilde{H}$ from the odd-hole $H$ (i.e., $v_k \in \tilde{H} \subset H$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{\prime 9}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{\prime 9}$ for each node $v_k \in \tilde{H}$, and for each $s' \in S_{k'}^{\prime 9}$ for all $v_{k'} \in H \setminus \tilde{H}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$.

$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 $F$ and then to $F_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. Based on this, we distinguish two cases:
- without changing the paths established in $S^{\text{9}}$: we derive a solution $S^{11} = (E^{11}, S^{11})$ from the solution $S^{\text{9}}$ by adding the slot $s'$ as last-slot to the demand $k$ without modifying the paths assigned to the demands $K$ in $S^{\text{9}}$ (i.e., $E_k^{11} = E_k^{\text{9}}$ for each $k \in K$), and the last-slots assigned to the demands $K \setminus \{k\}$ in $S^{\text{9}}$ remain the same in the solution $S^{11}$ i.e., $S_{k'}^{\text{9}} = S_{k'}^{11}$ for each demand $k' \in K \setminus \{k\}$, and $S_k^{11} = S_k^{\text{9}} \cup \{s'\}$ for the demand $k$. The solution $S^{11}$ is feasible given that

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

* a set of last-slots $S_k^{11}$ is assigned to each demand $k \in K$ along each edge $e \in E_k^{11}$ with $|S_k^{11}| \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} \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^{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_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. We then obtain that

$$ \mu x^{S^{\text{9}}} + \sigma z^{S^{\text{9}}} = \mu x^{S^{11}} + \sigma z^{S^{11}} = \mu x^{S^{\text{9}}} + \sigma z^{S^{\text{9}}} + \sigma_{s'}^k. $$

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

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

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

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

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

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

The corresponding incidence vector $(x^{S^{\text{9}}}, z^{S^{\text{9}}})$ is belong to $F$ and then to $F_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. We have so

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

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in H$ 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$ with $s' \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in H$ s.t. we find

$$ \sigma_{s'}^k = 0, \text{ for demand } k \text{ and all slots } s' \in \{w_k, ..., \bar{s}\} \text{ with } s' \notin \{s_i + w_k - 1, ..., s_j\} \text{ if } v_k \in H. $$
Given that the demand *k* is chosen arbitrarily. We iterate the same thing for all the demands *k'* in *K* \ {k} such that

$\sigma_s^{k'} = 0$, for all $k' \in K \setminus \{k\}$ and all slots $s \in \{w_{k'}, ..., \bar{s}\}$ with $s \notin \{s_i + w_{k'} - 1, ..., s_j\}$ if $v_{k'} \in H$.

Consequently, we conclude that

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

Let prove that $\sigma_{s'}^{k'}$ for all $v_{k'} \in H$ and all $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$ are equivalents. Consider a demand $k'$ with $v_{k'} \in H$ and a slot $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$. 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, ..., 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 S$ we have $\sum_{k \in K, e \in E_k^{12}} |\{s' \in S_k^{12}, 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^{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 there is $\frac{|\tilde{H}|-1}{2}$ demands $\tilde{H}$ from the odd-hole $H$ (i.e., $v_k \in \tilde{H} \subset H$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{12}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{12}$ for each node $v_k \in \tilde{H}$, and for each $s' \in S_{k'}^{12}$ for all $v_{k'} \in H \setminus \tilde{H}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$).

$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_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. Based on this, we distinguish two cases:

- without changing the paths established in $S^{12}$: we derive a solution $S^{13}$ from the solution $S^{12}$ as belows

* without changing the established paths for the demands $K$ in the solution $S^{12}$, i.e., $E_k^{13} = E_k^{12}$ for each demand $k \in K$,

* remove the last-slot $\tilde{s}$ totally covered by the interval $I$ and which has been selected by a demand $k_i \in \{v_{k_1}, ..., v_{k_r}\}$ in the solution $S^{12}$ (i.e., $\tilde{s} \in S_{k_i}^{12}$ and $\tilde{s}' \in \{s_i + w_{k_i} + 1, ..., s_j\}$) s.t. each pair of nodes $(v_{k'}, v_{k_j})$ are not linked in the odd-hole $H$ with $j \neq i$,

* and select a new last-slot $\tilde{s}' \notin \{s_i + w_{k_i} + 1, ..., s_j\}$ for the demand $k_i$ i.e., $S_{k_i}^{13} = (S_{k_i}^{12} \setminus \{\tilde{s}\}) \cup \{\tilde{s}'\}$ s.t. $\{\tilde{s}' - w_{k_i} - 1, ..., \tilde{s}'\} \cap \{s - w_k + 1, ..., s\} = \emptyset$ for each $k \in K$ and $s \in S_k^{12}$ with $E_k^{13} \cap E_{k_j}^{13} \neq \emptyset$,

* and add the slot $s'$ to the set of last-slots $S_{k'}^{12}$ assigned to the demand $k'$ in the solution $S^{12}$, i.e., $S_{k'}^{13} = S_{k'}^{12} \cup \{s'\}$,

* without changing the set of last-slots assigned to the demands $K \setminus \{k', k_i\}$, i.e., $S_k^{13} = S_k^{12}$ for each demand $K \setminus \{k', k_i\}$.

The solution $S^{13}$ is clearly 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}| \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^{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 S$ we have $\sum_{k \in K, e \in E_k^{13}} |\{s' \in S_k^{13}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{13}}, z^{S^{13}})$ is belong to $F$ and then to $F_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. We have so

$$ \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'} + \sigma_{\tilde{s}'}^{k_i} - \sigma_{\tilde{s}}^{k_i}. $$

This implies that $\sigma_{\tilde{s}}^{k_i} = \sigma_{s'}^{k'}$ for $v_{k_i}, v_{k'} \in H$ given that $\sigma_s^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, ..., \bar{s}\}$ with $s \notin \{s_i + w_k + 1, ..., s_j\}$ if $v_k \in H$.
- with changing the paths established in $S^{12}$: we construct a feasible solution $S'^{13}$ derived from the solution $S^{12}$ as belows

* without changing the established paths for the demands $K \setminus \tilde{K}$ in the solution $S^{12}$, i.e., $E_k'^{13} = E_k^{12}$ for each demand $k \in K \setminus \tilde{K}$,

* and with changing the established paths for the demands $\tilde{K}$ in the solution $S^{12}$ to a new paths $E_k'^{13}$ for each $k \in \tilde{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^{12}$ and $s \in S_k^{12}$ with $E_k'^{13} \cap E_{k_i}'^{13} \neq \emptyset$,

* remove the last-slot $\tilde{s}$ totally covered by the interval $I$ and which has been selected by a demand $k_i \in \{v_{k_1}, ..., v_{k_r}\}$ in the solution $S^{12}$ (i.e., $\tilde{s} \in S_{k_i}^{12}$ and $\tilde{s}' \in \{s_i + w_{k_i} + 1, ..., s_j\}$) s.t. each pair of nodes $(v_{k'}, v_{k_j})$ are not linked in the odd-hole $H$ with $j \neq i$,

* and select a new last-slot $\tilde{s}' \notin \{s_i + w_{k_i} + 1, ..., s_j\}$ for the demand $k_i$ i.e., $S_{k_i}'^{13} = (S_{k_i}^{12} \setminus \{\tilde{s}\}) \cup \{\tilde{s}'\}$ s.t. $\{\tilde{s}' - w_{k_i} - 1, ..., \tilde{s}'\} \cap \{s - w_k + 1, ..., s\} = \emptyset$ for each $k \in K$ and $s \in S_k^{12}$ with $E_k'^{13} \cap E_{k_i}'^{13} \neq \emptyset$,

* and add the slot $s'$ to the set of last-slots $S_{k'}^{12}$ assigned to the demand $k'$ in the solution $S^{12}$, i.e., $S_{k'}'^{13} = S_{k'}^{12} \cup \{s'\}$,

* and without changing the set of last-slots assigned to the demands $K \setminus \{k', k_i\}$, i.e., $S_k'^{13} = S_k^{12}$ for each demand $K \setminus \{k', k_i\}$.

The solution $S'^{13}$ is clearly 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 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_H^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k = \frac{|H|-1}{2}$. It follows 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'} + \sigma_{\tilde{s}'}^{k_i} - \sigma_{\tilde{s}}^{k_i} \\ - \sum_{\tilde{k} \in \tilde{K}} \sum_{e \in E(p_{\tilde{k}})} \mu_e^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E(p_{\tilde{k}})} \mu_{e'}^{\tilde{k}}. $$

This implies that $\sigma_{\tilde{s}}^{k_i} = \sigma_{s'}^{k'}$ for $v_{k_i}, v_{k'} \in H$ given that $\sigma_s^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, ..., \bar{s}\}$ with $s \notin \{s_i + w_k + 1, ..., s_j\}$ if $v_k \in H$, and $\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)$.

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

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all pairs } (v_k, v_{k'}) \in H. $$

Consequently, we obtain that $\sigma_s^k = \rho$ for all $v_k \in H$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$.

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

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

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

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

- $|H| \ge 5$,

- and $|C| \ge 3$,

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

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

Then, the inequality (27) is facet defining for $P(G, K, \mathbb{S})$ if and only if

- for each node $v_{k''}$ in $\tilde{G}_I^E$ with $v_{k''} \notin H \cup C$ and $C \cup \{v_{k''}\}$ is a clique in $\tilde{G}_I^E$, there exists a subset of nodes $\tilde{H} \subseteq H$ of size $\frac{|H|-1}{2}$ s.t. $\tilde{H} \cup \{v_{k''}\}$ is stable in $\tilde{G}_I^E$,

- and there does not exist an interval $I'$ of contiguous slots with $I \subset I'$ s.t. $H$ and $C$ define also an odd-hole and its connected clique in the associated conflict graph $\tilde{G}_I^E$.

**Proof. Necessity.**

- Note that if there exists a node $v_{k''}$ in $\tilde{G}_I^E$ s.t. $v_{k''}$ is linked with all nodes $v_k \in H$ and all nodes $v_{k'} \in C$. This implies that the inequality (27) is dominated by the following inequality

$$\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \frac{|H|-1}{2} \sum_{v_{k'} \in C} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} + \frac{|H|-1}{2} \sum_{s'=s_i+w_{k''}-1}^{s_j} z_{s''}^{k''} \le \frac{|H|-1}{2}.$$

- if there exists an interval $I'$ of contiguous slots with $I \subset I'$ s.t. $H$ and $C$ define also an odd-hole and its connected clique in the associated conflict graph $\tilde{G}_I^E$. This implies that the inequality (27) induced by the odd-hole $H$ and clique $C$ for the interval $I$ is dominated by the inequality (27) induced by the same odd-hole $H$ and clique $C$ for the interval $I'$ given that $\{s_i + w_k - 1, ..., s_j\} \subset I'$ for each $k \in H$.
If these cases are not verified, we ensure that the inequality (27) can never be dominated by another inequality without modifying its right hand side. Otherwise, the inequality (27) is not a facet defining for $P(G, K, \mathbb{S})$.

**Sufficiency.**

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

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

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

- 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}| \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^{13}$ and $s' \in S_{k'}^{13}$ with $E_k^{13} \cap E_{k'}^{13} \ne \emptyset$ (non-overlapping constraint),

- and there is $\frac{|H|-1}{2}$ demands $\tilde{H}$ from the odd-hole $H$ (i.e., $v_k \in \tilde{H} \subset H$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{13}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{13}$ for each node $v_k \in \tilde{H}$, and for each $s' \in S_{k'}^{13}$ for all $v_{k'} \in H \setminus \tilde{H}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$,

- and no demand from the clique $C$ selects a last-slot $s$ in the interval $I$ in the solution $S^{13}$, i.e., for each $k \in C$ and each $s \in S_k^{13}$ we have $s \notin \{s_i + w_k + 1, ..., s_j\}$.

Obviously, $S^{13}$ 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^{13}}, z^{S^{13}})$ is be-
long to $P(G, K, \mathbb{S})$ and then to $F_{H,C}^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \frac{|H|-1}{2} \sum_{v_{k'} \in C} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} = \frac{|H|-1}{2}$. As a result, $F_{H,C}^{\tilde{G}_I^E}$ is not empty (i.e., $F_{H,C}^{\tilde{G}_I^E} \ne \emptyset$). Fur-
thermore, given that $s \in \{s_i + w_k - 1, ..., s_j\}$ for each $v_k \in H$, this means that there exists at least
one feasible slot assignment $S_k$ for the demands $k$ in $H$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ for each $s \in S_k$
and each $v_k \in H$. This means that $F_{H,C}^{\tilde{G}_I^E} \ne P(G, K, \mathbb{S})$.

We denote the inequality $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k \le \frac{|H|-1}{2}$ by $\alpha x + \beta z \le \lambda$. Let $\mu x + \sigma z \le \tau$ be a valid inequality that is facet defining $F$ of $P(G, K, \mathbb{S})$. Suppose that $F_{H,C}^{\tilde{G}_I^E} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \mu x + \sigma z = \tau\}$. We show that there exist $\rho \in \mathbb{R}$ and $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (s.t. $\gamma_1 \in \mathbb{R} \sum_{k \in K} |E_0^k|, \gamma_2 \in \mathbb{R} \sum_{k \in K} |E_1^k|, \gamma_3 \in \mathbb{R} \sum_{k \in K} (w_k - 1)$) s.t. $(\mu, \sigma) = \rho(\alpha, \beta) + \gamma Q$, and that

- $\sigma_s^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, ..., \bar{s}\}$ with $s \notin \{s_i + w_k - 1, ..., s_j\}$ if $v_k \in H \cup C$ as we did in the proof of theorem 3,

- and $\mu_e^k = 0$ for all demands $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$ as we did in the proof of theorem 3,

- and $\sigma_s^k$ are equivalents for all $v_k \in H$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$ as we did in the proof of theorem 3,

s.t. the solutions $S^{49}-S^{14}$ still feasible for $F_{H,C}^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_k-1}^{s_j} z_s^k + \frac{|H|-1}{2} \sum_{v_{k'} \in C} \sum_{s'=s_i+w_{k'}-1}^{s_j} z_{s'}^{k'} = \frac{|H|-1}{2}$. We should prove now that $\sigma_s^k$ are equivalents for all $v_k \in C$ and all $s \in \{s_i + w_k - 1, ..., s_j\}$. For that, we consider a node $v_k \in C$ and a slot $s \in \{s_i + w_k - 1, ..., s_j\}$. For that, we consider a solution $S^{15} = (E^{15}, S^{15})$ in which

- 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} \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^{15}} |\{s' \in S_k^{15}, 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^{15}$ with $E_k^{15} \cap E_{k'}^{15} \neq \emptyset$,

- and there is $\frac{|H|-1}{2}$ demands $\tilde{H}$ from the odd-hole $H$ (i.e., $v_k \in \tilde{H} \subset H$ s.t. the demand $k$ selects a slot $s$ as last-slot in the solution $S^{15}$ with $s \in \{s_i + w_k - 1, ..., s_j\}$, i.e., $s \in S_k^{15}$ for each node $v_k \in \tilde{H}$, and for each $s' \in S_{k'}^{15}$ for all $v_{k'} \in H \setminus \tilde{H}$ we have $s' \notin \{s_i + w_{k'} - 1, ..., s_j\}$.

$S^{15}$ 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^{15}}, z^{S^{15}})$ is belong to $F$ and then to $F_{H,C}^{\tilde{G}_I^E}$ given that it is composed by $\sum_{v_k \in H} \sum_{s=s_i+w_{k-1}}^{s_j} z_s^k + \frac{|H|-1}{2} \sum_{v_{k'} \in C} \sum_{s'=s_i+w_{k'-1}}^{s_j} z_{s'}^{k'} = \frac{|H|-1}{2}$. Based on this, we construct a solution $S^{16}$ derived from the solution $S^{15}$ as belows

- without changing the established paths for the demands $K$ in the solution $S^{15}$, i.e., $E_k^{16} = E_k^{15}$ for each demand $k \in K$,

- remove all the last-slots $\tilde{s}_i$ totally covered by the interval $I$ and which has been selected by each demand $k_i \in \{v_{k_1}, ..., v_{k_r}\}$ in the solution $S^{15}$ (i.e., $\tilde{s} \in S_{k_i}^{15}$ and $\tilde{s} \in \{s_i + w_{k_i} + 1, ..., s_j\}$) for each $k_i \in \{v_{k_1}, ..., v_{k_r}\}$,

- and select a new last-slot $\tilde{s}'_i \notin \{s_i + w_{k_i} + 1, ..., s_j\}$ for each $k_i \in \{v_{k_1}, ..., v_{k_r}\}$ i.e., $S_{k_i}^{16} = (S_{k_i}^{15} \setminus \{\tilde{s}_i\}) \cup \{\tilde{s}'_i\}$ s.t. $\{\tilde{s}'_i - w_{k_i} - 1, ..., \tilde{s}'_i\} \cap \{s - w_k + 1, ..., s\} = \emptyset$ for each $k \in K$ and $s \in S_k^{15}$ with $E_k^{16} \cap E_{k'}^{16} \neq \emptyset$ for each $k_i \in \{v_{k_1}, ..., v_{k_r}\}$,

- and add the slot $s'$ to the set of last-slots $S_{k'}^{15}$ assigned to the demand $k'$ in the solution $S^{15}$, i.e., $S_{k'}^{16} = S_{k'}^{15} \cup \{s'\}$,

- without changing the set of last-slots assigned to the demands $K \setminus \{k', k_i\}$, i.e., $S_k^{16} = S_k^{15}$ for each demand $K \setminus \{k', k_i\}$.

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

- 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} \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^{16}} |\{s' \in S_k^{16}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{S^{15}} + \sigma z^{S^{15}} = \mu x^{S^{16}} + \sigma z^{S^{16}} = \mu x^{S^{15}} + \sigma z^{S^{15}} + \sigma_{s'}^{k'} + \sum_{i=1}^{r} \sigma_{\tilde{s}_i}^{k_i} - \sum_{i=1}^{r} \sigma_{\tilde{s}_i}^{k_i}. $$

This implies that $\sum_{i=1}^r \sigma_{\tilde{s}_i}^{k_i} = \sigma_{s'}^{k'}$ for $v_{k'} \in H$ given that $\sigma_s^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, ..., \tilde{s}\}$ with $s \notin \{s_i + w_k + 1, ..., s_j\}$ if $v_k \in H \cup C$.

Given that the $v_{k'}$ and $s' \in \{s_i + w_{k'} + 1, ..., s_j\}$ are chosen arbitrary in the clique $C$, we iterate the same procedure for all pairs $v_{k'} \in C$ and all $s' \in \{s_i + w_{k'} + 1, ..., s_j\}$ s.t. we find

$$ \sigma_{s'}^{k'} = \rho \frac{|H|-1}{2}, \text{ for all } v_{k'} \in C \text{ and } s' \in \{s_i + w_{k'} + 1, ..., s_j\}. $$

As a result,

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all } (v_k, v_{k'}) \in C \text{ and } s \in \{s_i + w_k + 1, ..., s_j\} \text{ and } s' \in \{s_i + w_{k'} + 1, ..., s_j\}. $$

Consequently, we obtain that $\sigma_{s'}^{k'} = \rho \frac{|H|-1}{2}$ for all $v_{k'} \in C$ and all $s' \in \{s_i + w_{k'} - 1, ..., s_j\}$.

Furthermore, we ensure that all the edges $e \in E_0^k$ for each demand $k$ are independants s.t. for each demand $k \in K$ we have

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

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

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

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

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

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

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

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

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

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

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

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

## 5.4 Slot-Assignment-Odd-Hole Inequalities

**Theorem 5.** Let $H$ be an odd-hole in the conflict graph $\tilde{G}_S^E$ with $|H| \ge 5$. Then, the inequality (31) is facet defining for $P(G, K, \mathbb{S})$ iff

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

- and there does not exist a node $v_{k',s'} \notin H$ in $\tilde{G}_S^E$ s.t. $v_{k',s'}$ is linked with all nodes $v_{k,s} \in H$,

- and there does not exist an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

• $[\min_{v_{k,s} \in H} (s - w_k + 1), \max_{v_{k,s} \in H} ] \subset I$,

• and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'})$ linked in $H$,

• and $2w_k \ge |I| + 1$ and $w_k \le |I|$ for each $v_k \in H$.
### Proof. Necessity.

We distinguish the following cases:

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

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

$$ \sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} z_{s'}^{k'} \le \frac{|H|-1}{2}. $$

- if there exists an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

• $[\min_{v_{k,s} \in H}(s - w_k + 1), \max_{v_{k,s} \in H}] \subset I$,

• and $w_k + w_{k'} \ge |I| + 1$ for each $(v_k, v_{k'})$ linked in $H$,

• and $2w_k \ge |I| + 1$ and $w_k \le |I|$ for each $v_k \in H$.

This implies that the inequality (31) is dominated by the inequality (26).

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

### Sufficiency.

Let $F_H^{\tilde{G}_S^E}$ denote the face induced by the inequality (31), which is given by

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

In order to prove that inequality $\sum_{v_{k,s} \in H} z_s^k \le \frac{|H|-1}{2}$ is facet defining for $P(G, K, \mathbb{S})$, we start checking that $F_H^{\tilde{G}_S^E}$ is a proper face, and $F_H^{\tilde{G}_S^E} \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 there is $\frac{|H|-1}{2}$ pairs of demand $k$ and slot $s$ from the odd-hole $H$ (i.e., $v_{k,s} \in H$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S^{16}$ denoted by $\tilde{H}_{16}$, i.e., $s \in S_k^{16}$ for each $v_{k,s} \in \tilde{H}_{16}$, and $s' \notin S_{k'}^{16}$ for all $v_{k',s'} \in H \setminus \tilde{H}_{16}$.

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

Let denote the inequality $\sum_{v_{k,s} \in H} z_s^k \le \frac{|H|-1}{2}$ by $\alpha x + \beta z \le \lambda$. Let $\mu x + \sigma z \le \tau$ be a valid inequality that is facet defining $F$ of $P(G, K, \mathbb{S})$. Suppose that $F_H^{\tilde{G}_S^E} \subset F = \{(x, z) \in P(G, K, \mathbb{S}) : \mu x + \sigma z = \tau\}$. We show that there exist $\rho \in \mathbb{R}$ and $\gamma = (\gamma_1, \gamma_2, \gamma_3)$ (s.t. $\gamma_1 \in \mathbb{R} \sum_{k \in K} |E_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_k^k = 0$ for all demands $k \in K$ and all slots $s \in \{w_k, ..., \bar{s}\}$ with $v_{k,s} \notin H$,

- 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 $\sigma_s^k$ are equivalents for all $v_{k,s} \in H$.

We first show that $\mu_e^k = 0$ for each edge $e \in E \setminus (E_0^k \cup E_1^k)$ for each demand $k \in K$. 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, ..., 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$, 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, ..., 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 there is $\frac{|H|-1}{2}$ pairs of demand $k$ and slot $s$ from the odd-hole $H$ (i.e., $v_{k,s} \in H$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S'^{16}$ denoted by $\tilde{H}_{16}$, i.e., $s \in S_k'^{16}$ for each $v_{k,s} \in \tilde{H}_{16}$, and $s' \notin S_{k'}'^{16}$ for all $v_{k',s'} \in H \setminus \tilde{H}_{16}$.

$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_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. 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'\} \cap \{s'' - w_{k'} + 1, ..., s''\} = \emptyset$ for each $k, k' \in K$ and each $s' \in S_k'^{17}$ and $s'' \in S_{k'}'^{17}$ with $E_k'^{17} \cap E_{k'}'^{17} \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'^{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_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. 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). $$

Let's show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$ with $v_{k,s} \notin H$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$ with $v_{k,s'} \notin H$. 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'\} \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} \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''^{16}} |\{s' \in 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 S_{k'}''^{16}$ with $E_k''^{16} \cap E_{k'}''^{16} \neq \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 there is one pair of demand $k$ and slot $s$ from the odd-hole $H$ (i.e., $v_{k,s} \in H$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S''^{16}$, i.e., $s \in S_k''^{16}$ for a node $v_{k,s} \in H$, and $s' \notin S_{k'}''^{16}$ for all $v_{k',s'} \in H \setminus \{v_{k,s}\}$.

$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_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. 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''^{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'\} \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).

The corresponding incidence vector $(x^{S''^{18}}, z^{S''^{18}})$ is belong to $F$ and then to $F_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. We then 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 $v_{k,s'} \notin H$.

- 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 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'^{18}} |\{s' \in 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 \tilde{K}$ and $s'' \in S_{k'}''^{16}$ (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}$).

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).
The corresponding incidence vector $(x^{S'18}, z^{S'18})$ is belong to $F$ and then to $F_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. 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_{s'}^k - \sum_{\tilde{k} \in \tilde{K}} \sum_{e \in E_k''^{16}} \mu_e^{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_k''^{18}} \mu_{e'}^{\tilde{k}} $$

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

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

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

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

Consequently, we conclude that

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

Let's prove that $\sigma_s^k$ for all $v_{k,s} \in H$ are equivalents. Consider a node $v_{k',s'}$ in $H$. 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{E}_k^{16}$),

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

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

- 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

• without modifying the paths assigned to the demands $K$ in $\tilde{S}^{16}$ (i.e., $E_k^{19} = \tilde{E}_k^{16}$ for each $k \in K$),

• and the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{16}$ remain the same in $S^{19}$, i.e., $\tilde{S}_{k''}^{16} = S_{k''}^{19}$ for each demand $k'' \in K \setminus \{k, k'\}$, where $k$ is a demand with $v_{k,s} \in \tilde{H}_{16}'$ and $s \in \tilde{S}_k^{16}$ s.t. $v_{k',s'}$ is not linked with any node $v_{k''}, s'' \in \tilde{H}_{16}' \setminus \{v_{k,s}\}$,

• and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $S_{k'}^{19} = \tilde{S}_{k'}^{16} \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 S_k^{16}$ with $v_{k,s} \in H$ and $v_{k,\tilde{s}} \notin H$ s.t. $S_k^{19} = (\tilde{S}_k^{16} \setminus \{s\}) \cup \{\tilde{s}\}$ for the demand $k$ 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'}^{19}$ with $E_k^{19} \cap E_{k'}^{19} \neq \emptyset$.
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).

The corresponding incidence vector $(x^{S^{19}}, z^{S^{19}})$ is belong to $F$ and then to $F_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. 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 + \sigma_{\tilde{s}}^k. $$

It follows that $\sigma_{s'}^{k'} = \sigma_s^k$ for demand $k'$ and a slot $s' \in \{w_{k'}, ..., \tilde{s}\}$ with $v_{k',s'} \in H$ given that $\sigma_{\tilde{s}}^k = 0$ for $v_{k,\tilde{s}} \notin H$.

* with changing the paths established in $\tilde{S}^{16}$: we construct a solution $S'^{19}$ derived from the solution $\tilde{S}^{16}$ by

* 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 the last-slots assigned to the demands $K \setminus \{k, k'\}$ in $\tilde{S}^{16}$ remain the same in $S'^{19}$, i.e., $\tilde{S}_{k'}^{16} = S_{k'}^{19}$ for each demand $k'' \in K \setminus \{k, k'\}$, where $k$ is a demand with $v_{k,s} \in \tilde{H}_{16}$ and $s \in \tilde{S}_k^{16}$ s.t. $v_{k',s'}$ is not linked with any node $v_{k'',s''} \in \tilde{H}_{16} \setminus \{v_{k,s}\}$,

* and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $S_{k'}'^{19} = \tilde{S}_{k'}^{16} \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^{16}$ with $v_{k,s} \in H$ and $v_{k,\tilde{s}} \notin H$ s.t. $S_k'^{19} = (\tilde{S}_k^{16} \setminus \{s\}) \cup \{\tilde{s}\}$ for the demand $k$ 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'^{19}$ with $E_k'^{19} \cap E_{k'}'^{19} \neq \emptyset$.

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

The corresponding incidence vector $(x^{S'^{19}}, z^{S'^{19}})$ is belong to $F$ and then to $F_H^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k = \frac{|H|-1}{2}$. 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_{\tilde{s}}^k \\ - \sum_{k \in \tilde{K}} \sum_{e \in \tilde{E}_k^{16}} \mu x^{\tilde{S}^{16}} + \sum_{k \in \tilde{K}} \sum_{e \in \tilde{E}_k^{19}} \mu x^{S^{19}}. $$

It follows that $\sigma_{s'}^{k'} = \sigma_s^k$ for demand $k'$ and a slot $s' \in \{w_{k'}, ..., \tilde{s}\}$ with $v_{k',s'} \in H$ given that $\sigma_{\tilde{s}}^k = 0$ for $v_{k,\tilde{s}} \notin H$, and $\mu_k^k = 0$ for all $k \in K$ and all $e \in E \setminus (E_0^k \cup E_1^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 \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),

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

$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_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. 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),

• 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),

• $\{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_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. 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$.

Let's us show that $\sigma_s^k = 0$ for all $k \in K$ and all $s \in \{w_k, ..., \bar{s}\}$ with $v_{k,s} \notin H \cup C$. Consider the demand $k$ and a slot $s'$ in $\{w_k, ..., \bar{s}\}$ with $v_{k,s'} \notin H \cup C$. 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 \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 $\{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 pair of demand $k$ and slot $s$ from the odd-hole $H$ (i.e., $v_{k,s} \in H$ s.t. the demand $k$ selects the slot $s$ as last-slot in the solution $S^{20}$, i.e., $s \in S_k^{20}$ for a node $v_{k,s} \in H$, and $s' \notin S_k^{20}$ for all $v_{k',s'} \in H \setminus \{v_{k,s}\}$.

$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_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. 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'}^{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 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'$} ∩ {$s'' - w_k' + 1, ..., s''$} = ∅ for each $k, k' ∈ K$ and each $s' ∈ S_k^{22}$ and $s'' ∈ S_{k'}^{22}$ with $E_k^{22} ∩ E_{k'}^{22} ≠ ∅$, i.e., for each edge $e ∈ E$ and each slot $s'' ∈ S$ we have $\sum_{k ∈ K, e ∈ E_k^{22}} |\{s' ∈ S_k^{22}, s'' ∈ \{s' - w_k + 1, ..., s'\}| ≤ 1$ (non-overlapping constraint).

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

- 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'$} ∩ {$s'' - w_k' + 1, ..., s''$} = ∅ 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} ∩ E_{k'}^{20} ≠ ∅$, 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'^{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'$} ∩ {$s'' - w_k' + 1, ..., s''$} = ∅ 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'$} ∩ {$s'' - w_k' + 1, ..., s''$} = ∅ for each $k, k' \in K$ and each $s' \in S_k'^{22}$ and $s'' \in S_{k'}'^{22}$ with $E_k'^{22} ∩ E_{k'}'^{22} ≠ ∅$, 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_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. We have so

$$\mu x^{S^{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_{\tilde{k}}^{20}} \mu_{\tilde{k}} + \sum_{\tilde{k} \in \tilde{K}} \sum_{e' \in E_{\tilde{k}}'^{22}} \mu_{e'}.$$

It follows that $\sigma_{s'}^k = 0$ for demand $k$ and a slot $s' \in \{w_k, ..., \bar{s}\}$ with $v_{k,s'} \notin H \cup C$ given that $\mu_e^k = 0$ for all the demand $k \in K$ and all edges $e \in E \setminus (E_0^k \cup E_1^k)$.

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

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

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

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

Consequently, we conclude that

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

Let's prove that $\sigma_s^k$ for all $v_{k,s} \in H$ are equivalents. Consider a node $v_{k',s'}$ in $H$. 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} \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^{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 \tilde{S}_k^{20}$ with $\tilde{E}_k^{20} \cap \tilde{E}_{k'}^{20} \neq \emptyset$ (non-overlapping constraint taking into account the possibility of adding the slot $s'$ in the set of last-slots $\tilde{S}_{k'}^{20}$ assigned to the demand $k'$ in the solution $\tilde{S}^{20}$),

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

$\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_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. 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

• 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 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'\}$, where $k$ is a demand with $v_{k,s} \in \tilde{H}_{20}'$ and $s \in \tilde{S}_k^{20}$ s.t. $v_{k',s'}$ is not linked with any node $v_{k'',s''} \in \tilde{H}_{20}' \setminus \{v_{k,s}\}$,

• and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $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 S_k^{20}$ with $v_{k,s} \in H$ and $v_{k,\tilde{s}} \notin H \cup C$ s.t. $S_k^{23} = (\tilde{S}_k^{20} \setminus \{s\}) \cup \{\tilde{s}\}$ for the demand $k$ 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}| \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^{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'\}| \le 1$ (non-overlapping constraint).

The corresponding incidence vector $(x^{S^{23}}, z^{S^{23}})$ is belong to $F$ and then to $F_{H,C}^{\tilde{G}_S^E}$ given that it is composed by $\sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} = \frac{|H|-1}{2}$. We 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'}, ..., \tilde{s}\}$ with $v_{k',s'} \in H$ given that $\sigma_{\tilde{s}}^k = 0$ for $v_{k,\tilde{s}} \notin H \cup C$.

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

$$ \sigma_s^k = \sigma_{s'}^{k'}, \text{ for all pairs } (v_{k,s}, v_{k',s'}) \in H. $$

Consequently, we obtain that $\sigma_s^k = \rho$ for all pairs $v_{k,s} \in H$.

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

• 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 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'\}$, where $k$ is a demand with $v_{k,s} \in \tilde{H}_{20}$ and $s \in \tilde{S}_{k}^{20}$ s.t. $v_{k',s'}$ is not linked with any node $v_{k'',s''} \in \tilde{H}_{20} \setminus \{v_{k,s}\}$,

* and adding the slot $s'$ as last-slot to the demand $k'$, i.e., $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 $v_{k,s} \in H$ and $v_{k,\tilde{s}} \notin H \cup C$ s.t. $S_{k}^{23} = (\tilde{S}_{k}^{20} \setminus \{s\}) \cup \{\tilde{s}\}$ for the demand $k$ 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}| \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}^{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 S$ we have $\sum_{k \in K, e \in E_{k}^{23}} |\{s' \in S_{k}^{23}, s'' \in \{s' - w_k + 1, ..., s'\}| \le 1$ (non-overlapping constraint).

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

$$ \mu x^{\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_s^k \\ - \sum_{k \in \tilde{K}} \sum_{e \in \tilde{E}_k^{20}} \mu x^{\tilde{S}^{20}} + \sum_{k \in \tilde{K}} \sum_{e \in \tilde{E}_k^{23}} \mu x^{S'^{23}}. $$

It follows that $\sigma_{s'}^{k'} = \sigma_s^k$ for demand $k'$ and a slot $s' \in \{w_{k'}, ..., \bar{s}\}$ with $v_{k',s'} \in H$ given that $\sigma_{\bar{s}}^k = 0$ for $v_{k,\bar{s}} \notin H \cup C$, and $\mu_e^k = 0$ for all $k \in K$ and all $e \in E \setminus (E_0^k \cup E_1^k)$.

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 (45) $$
We conclude that for each $k \in K$ and $e \in E$

$$ \mu_e^k = \begin{cases} \gamma_1^{k,e}, & \text{if } e \in E_0^k \\ \gamma_2^{k,e}, & \text{if } e \in E_1^k \\ 0, & \text{otherwise} \end{cases} $$

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

$$ \sigma_s^k = \begin{cases} \gamma_3^{k,s}, & \text{if } s \in \{1, \dots, w_k - 1\} \\ \rho, & \text{if } v_{k,s} \in H, \\ 0, & \text{if } v_{k,s} \notin H. \end{cases} $$

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

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

- $|H| \ge 5$,

- and $|C| \ge 3$,

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

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

Then, the inequality (32) is facet defining for $P(G, K, \mathbb{S})$ iff

- for each node $v_{k''},s''$ in $\tilde{G}_S^E$ with $v_{k''},s'' \notin H \cup C$ and $C \cup \{v_{k''},s''\}$ is a clique in $\tilde{G}_S^E$, there exists a subset of nodes $\tilde{H} \subseteq H$ of size $\frac{|H|-1}{2}$ s.t. $\tilde{H} \cup \{v_{k''},s''\}$ is stable in $\tilde{G}_S^E$,

- and there does not exist an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

$$ \bullet \left[ \min_{v_{k,s} \in H \cup C} (s - w_k + 1), \max_{v_{k,s} \in H \cup C} \right] \subset I, $$

$$ \bullet \text{ and } w_k + w_{k'} \ge |I| + 1 \text{ for each } (v_k, v_{k'}) \text{ linked in } H, $$

$$ \bullet \text{ and } w_k + w_{k'} \ge |I| + 1 \text{ for each } (v_k, v_{k'}) \text{ linked in } C, $$

$$ \bullet \text{ and } w_k + w_{k'} \ge |I| + 1 \text{ for each } v_k \in H \text{ and } v_{k'} \in C, $$

$$ \bullet \text{ and } 2w_k \ge |I| + 1 \text{ and } w_k \le |I| \text{ for each } v_k \in H, $$

$$ \bullet \text{ and } 2w_{k'} \ge |I| + 1 \text{ and } w_{k'} \le |I| \text{ for each } v_{k'} \in C. $$

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

We distinguish the following cases:

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

$$ \sum_{v_{k,s} \in H} z_s^k + \frac{|H|-1}{2} \sum_{v_{k',s'} \in C} z_{s'}^{k'} + \frac{|H|-1}{2} z_{s''}^{k''} \le \frac{|H|-1}{2}. $$

- if there exists an interval of contiguous slots $I = [s_i, s_j] \subset [1, \bar{s}]$ with

$$ \bullet \left[ \min_{v_{k,s} \in H \cup C} (s - w_k + 1), \max_{v_{k,s} \in H \cup C} \right] \subset I, $$

$$ \bullet \text{ and } w_k + w_{k'} \ge |I| + 1 \text{ for each } (v_k, v_{k'}) \text{ linked in } H, $$

$$ \bullet \text{ and } w_k + w_{k'} \ge |I| + 1 \text{ for each } (v_k, v_{k'}) \text{ linked in } C, $$

$$ \bullet \text{ and } w_k + w_{k'} \ge |I| + 1 \text{ for each } v_k \in H \text{ and } v_{k'} \in C, $$

$$ \bullet \text{ and } 2w_k \ge |I| + 1 \text{ and } w_k \le |I| \text{ for each } v_k \in H, $$

$$ \bullet \text{ and } 2w_{k'} \ge |I| + 1 \text{ and } w_{k'} \le |I| \text{ for each } v_{k'} \in C. $$

This implies that the inequality (32) is dominated by the inequality (27).

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