# The multiple steiner TSP with cyclic order on terminals: valid inequalities and polyhedra

A. Ridha Mahjoub<sup>1,2</sup> · Raouia Taktak<sup>3,4</sup> · Eduardo Uchoa<sup>5</sup>

Accepted: 19 March 2025 / Published online: 2 June 2025
© The Author(s) 2025

## Abstract

This paper deals with a variant of the Traveling Salesman Problem (TSP), called the Multiple Steiner TSP with Order Constraints (MSTSPOC). Consider an undirected graph with nonnegative weights on the edges, and a set of salesmen such that with each salesman is associated a set of ordered terminals. The MSTSPOC consists in finding a minimum-weight subgraph containing for each salesman a tour going in order through its terminals. We study the polytope associated with the Integer Linear Programming (ILP) formulation proposed in Borne et al. (2013). We characterize when the basic inequalities define facets. We also describe new valid inequalities along with necessary conditions and sufficient conditions for these inequalities to be facet-defining. Further families of valid inequalities, coming from closely related problems, are also discussed. The theoretical results presented in this paper are computationally tested in a companion paper (Taktak 2024).

**Keywords** Multiple Steiner TSP · Order constraints · Polytope · Facet · Valid inequality

**Mathematics Subject Classification** 90C10 · 52B05

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

<footnote>A. Ridha Mahjoub
ridha.mahjoub@ku.edu.kw; ridha.mahjoub@lamsade.dauphine.fr</footnote>

<footnote>Raouia Taktak
raouia.taktak@isims.usf.tn</footnote>

<footnote>Eduardo Uchoa
eduardouchoa@gmail.com</footnote>

<footnote n="1">¹ Department of Statistics and Operations Research, College of Science, Kuwait University, Kuwait City, Kuwait</footnote>

<footnote n="2">² LAMSADE, UMR CNRS 7243, Université Paris-Dauphine PSL, Paris, France</footnote>

<footnote n="3">³ ISIMS, Université de Sfax, Sfax, Tunisia</footnote>

<footnote n="4">⁴ Sm@rts, Centre de Recherche en Numérique de Sfax, Sfax, Tunisia</footnote>

<footnote n="5">⁵ Departamento de Engenharia de Produção, Universidade Federal Fluminense, Rio de Janeiro, RJ, Brasil</footnote>
<figure><img src="image_2.png" /><figcaption>Fig. 1 Illustrative example</figcaption></figure>

# 1 Introduction and related works

We consider a variant of the Traveling Salesman Problem (TSP), called the Multiple Steiner Traveling Salesman Problem with Order Constraints (MSTSPOC). Let $G = (V, E)$ be an undirected graph with nonnegative weights on the edges and $K$ a set of salesmen. For each salesman $k \in K$, there is a set $T_k \subseteq V$ of terminals. The MSTSPOC consists in finding a set of edges $F \subseteq E$, with minimum total weight, such that for each salesman $k \in K$ there is a *Steiner tour* that visits all terminals in $T_k$ in a predefined cyclic order. Steiner nodes not belonging to $T_k$ are optional and are denoted by $S_k$. These nodes may be traversed between visits to terminals. A *Steiner tour* is a cycle going once through each of its terminals. In the sequel, we may simply say tour to refer to a Steiner tour. Moreover, due to some survivability restrictions, tours must be *elementary*, that is nodes and edges are not allowed to be visited more than once (see Borne et al. 2011, 2013).

In Fig. 1, we give an example in order to illustrate the MSTSPOC. Consider the graph in Fig. 1(a). The graph is composed of 8 nodes numbered from 1 to 8. Some of these nodes are connected by edges as shown in the figure. Assume that $|K| = 2$, and that $T_1 = \{1, 3, 5, 4\}$ and $T_2 = \{1, 2, 6, 5\}$ both must be visited in the given order, and both come back to node 1. Note here that, according to the notations above mentioned, Steiner nodes for both salesmen are $S_1 = \{2, 6, 7, 8\}$ and $S_2 = \{3, 4, 7, 8\}$, respectively. A feasible solution for the MSTSPOC is illustrated in Fig. 1(b). The tours of both salesmen are illustrated in Fig. 1(c) and Fig. 1(d), respectively. The first salesman will have the following tour (1, 2, 3, 8, 5, 4, 7, 1), and the second one, (1, 2, 7, 6, 5, 4, 8, 1).

<figure><img src="image_3.png" /></figure>
## 1.1 Previous works and our contributions

The MSTSPOC was first introduced in Borne et al. (2011) motivated by reliability issues in multilayer telecommunication networks. Several ILP formulations have been then proposed for the MSTSPOC, and a variety of algorithms has also been devised to solve the problem. In Borne et al. (2011), the authors prove that the problem is NP-hard even for a single salesman. The problem is reduced to the *k*-Vertex Disjoint Paths Problem, known to be NP-hard. In Borne et al. (2011), the authors give a path-based formulation for the MSTSPOC, and present preliminary experimental results. In a further work (Gabrel et al. 2020), the authors investigate more the path-based formulation. The pricing problem is discussed, specific branching strategies are described, and a Branch-and-Price algorithm is devised. A substantial experimental study is also presented. In Mahjoub et al. (2019), the authors propose a compact ILP formulation for the MSTSPOC. In this formulation, the tour of each salesman is viewed as a union of layers, each characterized by two terminals. The authors present experimental results that show the efficiency of the corresponding model. A third ILP formulation, called cut-formulation, is also proposed for the MSTSPOC. It is first introduced in Borne et al. (2013), where the authors present some preliminary results of a Branch-and-Cut algorithm. The cut formulation is then strengthened using several families of valid inequalities in Taktak and Uchoa (2020), where the authors present briefly some theoretical results related to the polytope associated with this formulation. In Taktak (2024), the author devise a Branch-and-Cut algorithm for the cut formulation to solve the MSTSPOC. In particular, separation routines are proposed for the different classes of valid inequalities used in the algorithm. Moreover, experimental results are presented, and they show the efficiency of the valid inequalities in solving random and realistic instances. Note that the work in Taktak (2024) is complementary to the current work since both concern the cut formulation. In fact, paper (Taktak 2024) is experimental and aims at giving the experimental proofs of the efficiency of the valid inequalities whose facial aspect is studied in the current paper.

In this paper, we study the polytope of the cut formulation, that is the convex hull of the solutions of the cut formulation. We first recall the cut formulation introduced in Borne et al. (2013). Then we characterize the dimension of the polytope and investigate the facial structure of the basic inequalities. We also describe new classes of valid inequalities and give necessary conditions and sufficient conditions for these inequalities to be facet-defining. The efficiency of these valid inequalities in solving the MSTSPOC is shown in Taktak (2024). Finally, we describe further classes of valid inequalities that extend valid inequalities coming from relaxed problems like the *k*-Node Connected Subgraph Problem, the *k*-Edge Connected Subgraph Problem, and the TSP.

## 1.2 Other related works

Several variants of the TSP are closely related to the MSTSPOC. In what follows, we review some of them.
The *Steiner Traveling Salesman Problem (STSP)* is a variant of the TSP in which only a given subset of nodes, called terminals, must be visited in a minimum-weight cycle. The cycle may contain non terminal nodes, called *Steiner* nodes. Letchford et al. (2013) propose several compact formulations for the STSP obtained from ones known for the TSP. The authors compare these formulations both theoretically and computationally. In Interian and Ribeiro (2017), Interian and Ribeiro adapt some classical constructive heuristics as well as neighborhood structures used for the TSP to solve the STSP. In particular, they devise a GRASP heuristic-based algorithm that proved to be efficient for solving large-sized instances. In Rodríguez-Pereira et al. (2019), Rodríguez-Pereira et al. consider the STSP as well as some extensions with depots. They propose compact ILP formulations for the studied variants of the STSP, and devise Branch-and-Cut algorithms. Álvarez-Miranda and Sinnl (2019) propose a transformation of the STSP to the classical TSP. In consequence, they use a state-of-the-art TSP-solver to solve a benchmark of instances. Compared to the approaches developed in Letchford et al. (2013) and Interian and Ribeiro (2017), the authors were able to solve all instances from the literature to optimality within 20 seconds. In particular, they provide optimal solutions for 14 instances not yet solved.

A further interesting variant is the so-called *multiple TSP* (mTSP) which consists in finding a set of tours for a predefined number of salesmen, each starting from and coming back to a depot node while visiting exactly once the other intermediate nodes. The mTSP has been widely studied in the literature. In Cheikhrouhou and Khoufi (2021), Cheikhrouhou and Khoufi present a survey of the problem. They discuss the different variants and approaches as well as the various applications introduced in the literature for the problem. Bektas (2006) presents a survey of the variant where all salesmen are supposed to start from the same depot. In Benavent and Martínez (2013), Benavent and Martínez study the problem where the salesmen are assumed to start from different depots. They give an ILP formulation for the problem and describe several families of valid inequalities along with a substantial polyhedral study. Using this, they devise an efficient Branch-and-Cut algorithm for the problem. Sundar and Rathinam (2016) consider the Generalized multi-depot TSP, a variant that has several applications in ring networks, flexible manufacturing, and scheduling. The authors propose an integer programming formulation for the problem. They also study the associated polytope and derive facet-defining inequalities. These results are used to devise an efficient Branch-and-Cut algorithm. Bernardino et al. (2022) study three variants of the mTSP, the multi-depot family TSP and its two clustered variants. They present several mixed integer linear programming formulations and develop appropriate Branch-and-Cut based algorithms. Cornejo-Acosta et al. (2023) consider the so-called depot-free mTSP where the depots are unknown or unnecessary. New compact integer programming formulations are proposed along with a substantial experimental study. In Duchenne et al. (2007, 2012), Duchenne et al. study the undirected m-Capacitated Peripatetic Salesman Problem. The aim is to determine *m* Hamiltonian cycles of minimal total cost on a graph, such that all the edges are traversed less than the value of their capacity. In Duchenne et al. (2007), the authors study the polyhedral aspect of the problem, and devise a 2-index Branch-and-Cut algorithm. In Duchenne et al. (2012), they introduce three formulations for the problem, and develop Branch-and-Cut and Branchd-and-Price algorithms.

<figure><img src="image_4.png" /></figure>
Another variant, the *Steiner multiple TSP*, closely related to the problem studied in this paper, has been addressed in several works. D'Angelo (2018) considers the Steiner Multi Cycle Problem. Heuristic-based algorithms are described. In Lintzmayer et al. (2020), Lintzmayer et al. study a randomized approximation scheme for the Euclidean Steiner Multi Cycle problem which runs in quasilinear time. Liu et al. (2021) discuss the online Multiple Steiner TSP (mSTSP) with edge blockages. They study the problem with *minsum* and *minmax* objectives. Lower bounds and efficient online algorithms are proposed for both variants.

A further close variant is the *TSP with Precedence Constraints* that consists in finding a minimum-weight tour respecting precedence constraints between some pairs of nodes. This variant has also been widely studied in the literature. In Balas et al. (1995), Balas et al. examine the polytope of the Asymmetric TSP with Precedence Constraints (ATSP-PC). They characterize the dimension of the polytope and derive several families of valid inequalities. They also discuss conditions for these inequalities to be facet-defining and devise separation routines. In Ascheuer et al. (2000), Ascheuer et al. propose a Branch-and-Cut algorithm to solve the ATSP-PC. Gouveia and Pesneau (2006) give extended formulations for the ATSP-PC. Moreover, they describe classes of valid inequalities, and discuss polynomial time separation algorithms. Using this, they devise a cutting plane approach to the problem. The computational results show the efficiency of their approach for reducing the LP gap. In Gouveia et al. (2018), Gouveia et al. propose network-flow-based formulations for the ATSP-PC. Sarin et al. (2014) study variants of the multiple asymmetric TSP with and without precedence constraints and investigate the performances of 32 MILP formulations modeling these variants. Some of these formulations are based on a transformation of the Multiple Asymmetric TSP (mATSP) to Asymmetric TSP (ATSP) (Sarin et al. 2005). In a recent work, Khachai et al. (2023) address the Generalized ATSP-PC. The authors study the associated polytope, identify several families of valid inequalities, and discuss facet-defining conditions. The authors also propose MILP formulations and devise Branch-and-Cut algorithms for the problem.

In what follows, we give notations and definitions that will be used.

## 1.3 Notations

Let $G = (V, E)$ be a simple edge-weighted undirected graph, such that with each edge $e \in E$ is associated a nonnegative weight $w_e$. We denote $n = |V|$ and $m = |E|$. An edge $e$ between two nodes $u$ and $v$ in $V$ will be denoted by $e = uv$. We suppose given a set $K$ of salesmen, each having to visit a set of terminals $T_k = \{w_1^k, w_2^k, \dots, w_{|T_k|}^k\}, k \in K$. The order of terminals' visitation for each tour (salesman) is assumed to follow the cyclic order of the indices $j$ in $w_j^k$. Consider a terminal $w_j^k \in T_k$, the terminals in $T_k \setminus \{w_{j-1}^k, w_{j+1}^k\}$ are said to be *non-consecutive*, for $w_j^k, j = 1, 2, \dots, |T_k|$, where $w_{|T_k|+1}^k$ refers to $w_1^k$. The nodes of $V$ that are not terminals for $k \in K$ are called *Steiner nodes*, and denoted by $S_k$. If $k \in K$, a pair $q_j^k = (w_j^k, w_{j+1}^k)$ of consecutive terminals $w_j^k$ and $w_{j+1}^k$ is called a *section* for $j \in \{1, 2, \dots, |T_k|\}$. Each tour, for a salesman $k \in K$, can be seen as the union of node-disjoint sections. We denote by $\mathcal{T}_k$
the set of these sections for $k \in K$. With each section $q_j^k = (w_j^k, w_{j+1}^k) \in \mathcal{T}_k, k \in K$ and $j \in \{1, 2, \dots, |T_k|\}$, we associate a reduced graph, denoted by $G_j^k = (V_j^k, E_j^k)$, obtained from the original graph $G$ by deleting all the terminals of $T_k$, except $w_j^k$ and $w_{j+1}^k$, as well as their incident edges. The graph $G_j^k$ will be used to compute a path between $w_j^k$ and $w_{j+1}^k$ not going through any of the other terminals.

Let $V' \subset V$, we denote by $G(V') = (V', E')$ the subgraph induced by the set of vertices $V'$ and the set of edges connecting these vertices $E' = E(V')$. If $W \subset V$ is a subset of nodes of $V$, we let $\delta_G(W)$ denote the cut in $G$ induced by $W$, that is the set of edges of $G$ having one node in $W$ and the other in $\bar{W} = V \setminus W$. If $W = \{w\}$, $w \in V$, we will write $\delta_G(w)$ for $\delta_G(\{w\})$. In the sequel we simply write $\delta(W)$ and $\delta(w)$, if the context is clear.

## 1.4 Paper organization

The paper is organized as follows. In the next section, we propose an ILP formulation for the MSTSPOC, and we introduce the associated polytope. In Sect. 3, we study the facial aspect of the basic constraints. In Sect. 4, we describe some valid inequalities and give necessary conditions and sufficient conditions for these inequalities to be facet-defining. In Sect. 5, we give further families of valid inequalities coming from closely related problems. Finally, Sect. 6 is devoted to some concluding remarks. An Appendix is used to give some proofs of facets.

# 2 Integer linear programming formulation

## 2.1 ILP formulation

Consider a salesman $k \in K$ and an edge $e \in E$. We define the binary variable $x_e^k$ that is equal to 1 if the tour of salesman $k$ uses edge $e$, and 0 if not. We also define the binary variable $y_e$ for each $e \in E$, which is equal to 1 if edge $e$ is considered in the final solution, and 0 if not. The MSTSPOC is equivalent to the following ILP.

$$ \min \sum_{e \in E} w_e y_e \qquad (1) $$

$$ \sum_{e \in \delta_{G_j^k}(W)} x_e^k \geq 1 \qquad \text{for all } k \in K, j \in \{1, \dots, |T_k|\}, \qquad (2) $$

$$ W \subset V_j^k : w_j^k \in W \text{ and } w_{j+1}^k \in \bar{W}, $$

$$ \sum_{e \in \delta(w)} x_e^k \leq 2 \qquad \text{for all } w \in V, k \in K, \qquad (3) $$

$$ x_e^k \leq y_e \qquad \text{for all } e \in E, k \in K, \qquad (4) $$

$$ 0 \leq x_e^k \qquad \text{for all } e \in E, k \in K, \qquad (5) $$

$$ y_e \leq 1 \qquad \text{for all } e \in E, \qquad (6) $$
$$x_e^k \in \{0, 1\} \quad \text{for all } e \in E, k \in K, \qquad (7)$$

$$y_e \in \{0, 1\} \quad \text{for all } e \in E. \qquad (8)$$

Inequalities (2) are called *section cut inequalities*. They ensure for each section $q_j^k = (w_j^k, w_{j+1}^k)$, corresponding to a salesman $k \in K$ and $j \in \{1, \dots, |T_k|\}$, a path in the reduced graph $G_j^k$. Hence, this guarantees, for each salesman a tour going in order through its terminals. Inequalities (3) are called *disjunction inequalities*. They ensure that the different sections for a salesman, $k \in K$ are disjoint, and hence that the associated tour is elementary. Inequalities (4) are the *linking inequalities* which express the fact that if an edge $e \in E$ is not considered in the solution, that is if $y_e = 0$, then $e$ can not be used in any tour for the salesmen $K$. Finally, inequalities (5) and (6) are the *trivial inequalities*, and (7) and (8) are the *variables' integrality constraints*.

In what follows, we refer to the ILP (1)-(8) as the *cut formulation*. Note that this formulation was first introduced in Borne et al. (2013) and is experimentally studied in Taktak (2024).

## 2.2 Associated polytope

An instance of the MSTSPOC corresponds to the triplet $(G, K, T)$, where $G$ is a graph, $K$ a set of salesmen, each salesman has a set $T_k$ of terminals and $T = \bigcup_{k \in K} T_k$.

We denote by MSTSPOC$(G, K, T)$ the polytope associated with the MSTSPOC, that is the convex hull of the solutions of (2)-(8), i.e.,

$$\text{MSTSPOC}(G, K, T) = \text{conv}\{(x, y) \in \{0, 1\}^{|E|(|K|+1)} : (x, y) \text{ satisfies (2)-(6)}\}.$$

In what follows, $G$ is assumed to be complete and for each salesman $k \in K$, $T_k \neq V$. These assumptions are not restrictive. In fact, if the graph is not complete, one can consider a complete graph by associating very high costs with the non-existent edges. Moreover, if there exists a salesman $k \in K$ such that $T_k = V$, then the solution is unique for this salesman. In this case, the problem reduces to solving the MSTSPOC for the $K \setminus \{k\}$ remaining salesmen. Furthermore, for convenience, we will suppose that each salesman $k \in K$ has at least 4 Steiner nodes. This will enable us to considerably simplifying some facet proofs.

Give an instance $(G, K, T)$ of MSTSPOC, we denote by $\Omega(G, K, T)$ the set of its solutions. Each solution in $\Omega(G, K, T)$ is represented by the pair $(U, I)$ where $I \subseteq E$ is the set of *installed edges* and $U = (U_1, U_2, \dots, U_{|K|}) \subseteq E^{|K|}$ such that $U_j, j = 1, \dots, |K|$, is the set of edges used by salesman $j$. Given a solution $(U, I) \in \Omega(G, K, T)$, we define $(x^U, y^I)$ its incidence vector. Note that $x^U = (x^{U_1}, x^{U_2}, \dots, x^{U_{|K|}})$.

Now, we give a solution for the MSTSPOC that will be used throughout the paper.

**Remark 1** Let $U^0 = (U_1^0, U_2^0, \dots, U_{|K|}^0)$ be the set of edges between the consecutive terminals of all the salesmen, that is $U_j^0 = \{w_j^j w_{i+1}^j, j \in K, i = 1, \dots, |T_j|\}$. And let $I^0 = \bigcup_{j \in K} U_j^0$. Clearly, the pair $(U^0, I^0)$ is a solution of the MSTSPOC.
For sake of presentation, for each of the coming facet proofs, we will begin numbering the solutions $(U^j, I^j)$ by $j = 1$. Having the same name, these solutions may be different from one proof to another.

# 3 Dimension and facial investigation

In this section, we characterize the dimension of MSTSPOC$(G, K, T)$ and discuss necessary and sufficient conditions for inequalities (2)-(6) to be facet-defining.

## 3.1 Dimension

In this section, we characterize the dimension of the polytope MSTSPOC$(G, K, T)$. To this end, we first identify the system of its equations.

**Remark 2** Consider a salesman $k \in K$ and let $w_j^k \in T_k$ be a terminal. Then $w_j^k$ has a degree equal to 2 in any solution, that is

$$ \sum_{e \in \delta(w_j^k)} x_e^k = 2 \quad \text{for all } w_j^k \in T_k, k = 1, \dots, |K|, j \in \{1, \dots, |T_k|\}. \quad (9) $$

**Remark 3** Since equations (9) are written for each terminal $w_j^k \in T_k$, there are $|T_k|$ equations for each salesman $k \in K$.

**Remark 4** Consider a salesman $k \in K$, and $w_i^k, w_j^k \in T_k$ be two non-consecutive terminals of $k$. This yields that edge $e = w_i^k w_j^k$ does not belong to any solution of the MSTSPOC.

$$ x_e^k = 0 \quad \text{for all } e = w_i^k w_j^k, w_i^k, w_j^k \in T_k : \quad j > i, k = 1, \dots, |K|. \quad (10) $$

**Remark 5** Let $G(T_k)$ be the graph induced by the terminals $T_k$ of salesman $k$. Notice that since $G$ is complete, $G(T_k)$ is also complete and contains $\frac{|T_k|(|T_k|-1)}{2}$ edges. In this graph, there are exactly $|T_k|$ edges between the consecutive terminals. All the remaining edges are between non-consecutive terminals and, in consequence, their number is equal to $\frac{|T_k|(|T_k|-1)}{2} - |T_k| = \frac{|T_k|(|T_k|-3)}{2}$. Consequently, constraints (10) imply $\frac{|T_k|(|T_k|-3)}{2}$ equations of type (10) for salesman $k$. In the sequel, we shall denote by $p_k$ the number of edges between non-consecutive terminals for salesman $k$, that is $p_k = \frac{|T_k|(|T_k|-3)}{2}$.

**Proposition 1** Consider an equation $ax + by = \alpha$ of MSTSPOC$(G, K, T)$. Then:

1. $b = 0$,

2. $ax = \alpha$ is a linear combination of equations (9) and (10).

**Proof** We first show that $b = 0$. Consider the feasible solution $(U^0, I^0)$ given by Remark 1. Recall that $U_j^0, j = 1, \dots, |K|$ consists of the set of edges linking the consecutive terminals of $T_j$ of salesman $j \in K$ and $I^0 = \cup_{j \in K} U_j^0$.
Let $e \in E \setminus I^0$ be an arbitrary edge. The solution $(U^1, I^1)$ such that $I^1 = I^0 \cup \{e\}$ and $U^1 = U^0$ also induces a feasible solution of MSTSPOC(G, K, T). This implies that $ax^{U^0} + by^{I^0} = ax^{U^0} + by^{I^0} + b_e$, implying that $b_e = 0$. Since $e$ is arbitrarily chosen in $E \setminus I^0$, we have that

$$b_e = 0 \quad \text{for all } e \in E \setminus I^0. \qquad (11)$$

Now, let us consider the solution $(U^2, I^2)$ obtained as follows. For a salesman $k \in K$, let $e = t_i t_{i+1}$ be an edge between two consecutive terminals $t_i$ and $t_{i+1}$ of $T_k$. Let $U_k^2 = (U_k^0 \setminus \{e\}) \cup \{t_i s, s t_{i+1}\}$ where $s$ is a Steiner node of salesman $k$. In addition, let $U_j^2 = U_j^0$, $j = 1, \dots, K$, $j \neq k$, and $I^2 = \cup_{j \in K} U_j^2$. Moreover, consider the solution $(U^3, I^3)$ given by $U^3 = U^2$ and $I^3 = I^2 \cup \{e\}$. Both are feasible solutions for the MSTSPOC and hence their incidence vectors satisfy equation $ax + by = \alpha$. As a consequence, we have $ax^{U^2} + by^{I^2} = ax^{U^2} + by^{I^2} + b_e$, which implies that $b_e = 0$. As $e$ is arbitrary in $I^0$, this yields

$$b_e = 0 \quad \text{for all } e \in I^0. \qquad (12)$$

By (11) and (12) we then have

$$b_e = 0 \quad \text{for all } e \in E. \qquad (13)$$

Therefore all the equations of MSTSPOC(G, K, T) are given only in terms of variables $x$.

Let $a^k$ be the restriction of $a$ on salesman $k \in K$. Let $M^k = \begin{pmatrix} M_1^k \\ M_2^k \end{pmatrix}$ be the sub-matrix of equations (9) and (10) involving variables $x_e^k$, $e \in E$, such that $M_1^k$ is the sub-matrix corresponding to equations (9) and $M_2^k$ the one corresponding to equations (10). To prove that $ax = \alpha$ is a linear combination of equations (9) and (10), it would be sufficient to prove that for each $k \in K$, there exit $\lambda_1^k \in \mathbb{R}^{|T_k|}$ and $\lambda_2^k \in \mathbb{R}^{|P_k|$} $ such that $a^k = \lambda_1^k M_1^k + \lambda_2^k M_2^k$ (recall that $p_k$ is the number of edges between non-consecutive terminals of $T_k$).

To this end, first we show that for every edge $ss'$ between two Steiner nodes $s, s'$, $a_{ss'}^k = 0$. Consider again the solution $(U^0, I^0)$ and let $(U^4, I^4)$ be the solution given by $U_k^4 = U_k^0 \cup \{ss'\}$, $U_j^4 = U_j^0$ for all $j \in \{1, \dots, K\} \setminus k$, and $I^4 = \cup_{j \in K} U_j^4$. Obviously, $(U^4, I^4)$ is a solution of the MSTSPOC. Since solutions $(U^0, I^0)$ and $(U^4, I^4)$ are both feasible for the MSTSPOC and by (13) $b = 0$, we have that $ax^{U^0} = ax^{U^4} = ax^{U^0} + a_{ss'}^k x_{ss'}^k$. Hence $a_{ss'}^k = 0$, implying that

$$a_{ss'}^k = 0 \quad \text{for all } s, s' \in S_k, k \in K. \qquad (14)$$

Consider now an edge $f = t_i t_{i+1}$ between two consecutive terminals $t_i$ and $t_{i+1}$ of $T_k$. Let $s$ be a Steiner node of $S_k$. Consider the solution $(U^5, I^5)$ given by $U_k^5 = (U_k^0 \setminus \{f\}) \cup \{t_i s, s t_{i+1}\}$, $U_j^5 = U_j^0$, for each $j \in \{1, \dots, K\} \setminus k$, and $I^5 = \cup_{j \in K} U_j^5$.
As $(U^5, I^5)$ is feasible for the MSTSPOC, it follows that $ax^{U^0} = ax^{U^5} = ax^{U^0} - a_{ti_{i+1}}^k + a_{ti_s}^k + a_{st_{i+1}}^k$, implying that $a_{ti_{i+1}}^k = a_{ti_s}^k + a_{st_{i+1}}^k$. Therefore, as nodes $s, t_i$ and $t_{i+1}$ are all arbitrary, we have

$$a_{ti_{i+1}}^k = a_{ti_s}^k + a_{st_{i+1}}^k \quad \text{for all } t_i, t_{i+1} \in T_k, s \in S_k, k \in K. \quad (15)$$

Now, we will prove that all the edges linking a terminal to Steiner nodes of $S_k$ have the same coefficient $a_e^k$. Consider $(U^6, I^6)$ obtained from $(U^5, I^5)$ as follows: $U_k^6 = (U_k^5 \setminus \{st_i\}) \cup \{ss', s't_i\}, U_j^6 = U_j^5$ for each $j \in \{1, \dots, K\} \setminus k$ and $I^6 = \cup_{j \in K} U_j^6$, where $s$ and $s'$ are Steiner nodes of $S_k$ (Recall that we assumed that $|S_k| \ge 2$ for all $k \in K$). Since $(U^5, I^5)$ and $(U^6, I^6)$ satisfy equation $ax + by = \alpha$, this implies that $ax^{U^5} = ax^{U^6} = ax^{U^5} - a_{st_i}^k + a_{ss'}^k + a_{s't_i^k}^k$, and hence $a_{st_i}^k = a_{ss'}^k + a_{s't_i}^k$. By (14), it follows that

$$a_{st_i}^k = a_{s't_i}^k = \lambda_1^k(t_i) \quad \begin{array}{ll} \text{for all } t_i \in T_k, s, s' \in S_k, k \in K, & \\ \text{for some } \lambda_1^k(t_i) \in \mathbb{R}. & (16) \end{array}$$

Now, let $\lambda^k = (\lambda_1^k, \lambda_2^k)$, $k \in K$ such that $\lambda_1^k = (\lambda_1^k(t_i), t_i \in T_k)$ and $\lambda_2^k = (\lambda_2^k(uv), u, v \in T_k, uv \notin U_k^0)$ such that $\lambda_2^k(uv) = a_{uv}^k - \lambda_1^k(u) - \lambda_1^k(v), k \in K$. By (15), we have $a_{ti_{i+1}}^k = \lambda_1^k(t_i) + \lambda_1^k(t_{i+1})$ for each two consecutive terminals $t_i$ and $t_{i+1}$ of $T_k$.

The vectors $\lambda_1^k$ and $\lambda_2^k$ can then be given so that:

$$a_{uv}^k = \begin{cases} \lambda_1^k(u) + \lambda_1^k(v) & \text{if } uv = t_i t_{i+1}, t_i, t_{i+1} \in T_k, \\ \lambda_1^k(u) & \text{if } u \in T_k, v \in S_k, \\ \lambda_2^k(uv) + \lambda_1^k(u) + \lambda_1^k(v) & \text{if } uv = t_i t_j, t_i, t_j \in T_k, \quad j > i, \\ 0 & \text{if } u, v \in S_k, u \neq v, \end{cases}$$

yielding

$$a^k = \lambda_1^k M_1^k + \lambda_2^k M_2^k \quad \text{for all } k \in K,$$

as desired.

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

By Proposition 1, we know that the only equations of MSTSPOC($G, K, T$) are equations (9) and (10). The matrix $M$ of equations of MSTSPOC($G, K, T$) can hence be written as

$$M = \begin{pmatrix} M_1 & & & \\ & M_2 & & \\ & & \ddots & \\ & & & M_{|K|} \end{pmatrix}$$

where $M_k$ is the matrix of the equations system (9) and (10) involving variables $x_e^k$ for salesman $k \in K$. Each matrix $M_k, k = 1, \dots, |K|$, consists of two sub-matrices.
<figure><img src="image_6.png" /><figcaption>Fig. 2 Matrix of equations for salesman k</figcaption></figure>

The first one is a terminal-edge incidence matrix and the second is a restriction of the identity matrix for the edges between non-consecutive terminals. More precisely, each matrix $M_k$ can be organized as in Fig. 2. The first $m_1$ columns correspond to the edges between consecutive terminals ($m_1 = |T_k|$). The next $m_2$ columns correspond to the edges between non-consecutive terminals ($m_2 = p_k$). The last $m_3$ columns correspond to the edges between the terminals of $T_k$ and the Steiner nodes of $S_k$ for $k = 1, \dots, |K|$. Here, the first columns are related to the Steiner node $s_1$, the second to $s_2$, and so on. The first $|T_k|$ rows of $M_k$ are associated with the terminals of $T_k$, and the last ones are associated with the edges between non-consecutive terminals. Note that the first $|T_k|$ rows of $M_k$ correspond to equations (9) and the last $p_k$ ones correspond to equations (10). The sub-matrices $I_1, \dots, I_{|S_k|}$ are identity matrices and are related to the Steiner nodes $s_1, \dots, s_{|S_k|}$ of $S_k$, respectively.

Observe that $M_k$ contains two blocks consisting of two identity matrices, namely $I_1$ and $I$ (hatched matrices). Moreover, these matrices cover the rows of $M_k$. Hence $M_k$ is of full rank equal to $|T_k| + p_k = \frac{|T_k|(|T_k| - 1)}{2}$. Therefore

$$ \mathrm{rank}(M) = \sum_{k \in K} \mathrm{rank}(M_k) = \sum_{k \in K} \frac{|T_k|(|T_k| - 1)}{2}. $$

As a consequence, we have the following result.

**Theorem 1**

$$ \mathrm{dim}(\mathrm{MSTSPOC}(G, K, T)) = (|K| + 1)|E| - \sum_{k \in K} \frac{|T_k|(|T_k| - 1)}{2}. $$

**3.2 Facial investigation**

In this section, we study the facial structure of the polytope $\mathrm{MSTSPOC}(G, K, T)$. In particular, we give necessary and sufficient conditions for inequalities of the cut formulation to be facet defining.

For convenience, we will suppose that each salesman has at least 4 Steiner nodes.

**Theorem 2** Inequality $x_e^k \ge 0$ defines a facet of $\mathrm{MSTSPOC}(G, K, T)$ if and only if $e$ is not between non-consecutive terminals of $T_k$.
**Proof** Let

$$F_e^k = \{(x, y) \in \text{MSTSPOC}(G, K, T) : x_e^k = 0\}.$$

The necessity condition is a consequence of Remark 4.

In what follows, we suppose that $e$ is not an edge between non-consecutive terminals of $T^k$.

Denote inequality $x_e^k \ge 0$ by $ax+by \le \alpha$ and let $rx+qy \le \beta$ be a valid inequality defining a facet $F$ of MSTSPOC$(G, K, T)$. Assume that $F_e^k \subseteq F$. To prove that $F_e^k$ is a facet of MSTSPOC$(G, K, T)$, it suffices to show that there exist $\rho \in \mathbb{R}$ and $\lambda = (\lambda^j, j \in K)$, $\lambda^j \in \mathbb{R}^{|T_j|+p_j}$ for $j \in K$, such that $q = \rho b$ and $r = \rho a + \lambda M$ (where $r = (r^1, r^2, \dots, r^{|K|})$ with $r^j \in \mathbb{R}^m$, $j = 1, \dots, |K|$ and $M$ is the equations matrix defined above). Note here that $a = (a^1, a^2, \dots, a^{|K|})$ is such that $a^i \in \mathbb{R}^m$, $i = 1, \dots, |K|$ with $a^i = 0$ for $i \in \{1, \dots, |K|\} \setminus \{k\}$, $a_e^k = 1$ and $a_{e'}^k = 0$ for $e \ne e'$. Note also that $b = 0$.

We will consider the case $e = s_1 s_2$, where $s_1$ and $s_2$ are Steiner nodes of $S_k$, the proof for the remaining cases is along the same line.

First, we prove that $q = 0$.

Consider the solution $(U^0, I^0)$ given in Remark 1 and let $f \in E \setminus I^0$. The solution $(U^1, I^1)$ such that $I^1 = I^0 \cup \{e\}$ and $U^1 = U^0$ also induces a feasible solution of MSTSPOC$(G, K, T)$. Moreover, the incidence vectors of these solutions are in $F_e^k$ and hence in $F$. This implies that $rx^{U^0} + qy^{I^0} = rx^{U^0} + qy^{I^0} + q_e$, and hence $q_f = 0$. Since $f$ is arbitrarily chosen in $E \setminus I^0$, we obtain that

$$q_f = 0 \quad \text{for all } f \in E \setminus I^0. \qquad (17)$$

Now, consider the solution $(U^2, I^2)$ obtained as follows. Consider a salesman $l \in K$ and let $f = t_i t_{i+1}$ be an edge between two consecutive terminals $t_i$ and $t_{i+1}$ of $T_l$. Let $U_l^2 = (U_l^0 \setminus \{e\}) \cup \{t_i s, s t_{i+1}\}$ where $s \in S_l$. In addition, let $U_j^2 = U_j^0$, $j = 1, \dots, |K|$, $j \ne l$, and $I^2 = \bigcup_{j \in K} U_j^2$. And, let $(U^3, I^3)$ be the solution such that $U^3 = U^2$ and $I^3 = I^2 \cup \{e\}$. Clearly, both solutions are feasible for the MSTSPOC and are in $F_e^k$. Hence, $rx^{U^2} + qy^{I^2} = rx^{U^2} + qy^{I^2} + q_e$, which implies that $q_f = 0$. As $f$ is arbitrary in $I^0$, this yields

$$q_f = 0 \quad \text{for all } f \in I^0. \qquad (18)$$

By (17) and (18), we then have

$$q_f = 0 \quad \text{for all } f \in E. \qquad (19)$$

We now show that $r_{ss'}^j = 0$ for all $s, s' \in S_j$ such that either $j = k$ and $ss' \ne e$ or $j \in K \setminus \{k\}$.

Consider an edge $ss'$ between two Steiner nodes $s$ and $s'$ of $S_k$ different from $e$. Let $(U^4, I^4)$ be the solution defined as follows: $U_k^4 = U_k^0 \cup \{ss'\}$, $U_j^4 = U_j^0$ for all $j \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^4 = \bigcup_{j \in K} U_j^4$. As $ss' \notin U_k^0$ and $ss' \notin U_k^4$,
$(x^{U^0}, y^{I^0}), (x^{U^4}, y^{I^4}) \in F_e^k$, and consequently $(x^{U^0}, y^{I^0}), (x^{U^4}, y^{I^4}) \in F$. By (19), it follows that $rx^{U^0} = rx^{U^4}$. Therefore $rx^{U^0} = rx^{U^0} + r_{ss'}^k$, and hence $r_{ss'}^k = 0$. As $s$ and $s'$ are arbitrary in $S_k$, we then obtain that

$$r_{ss'}^k = 0 \quad \text{for all } s, s' \in S_k, ss' \neq e. \qquad (20)$$

Similarly we can show that

$$r_{ss'}^j = 0 \quad \text{for all } ss' \in S_j, l \in K \setminus \{k\}. \qquad (21)$$

Now, we will consider edges between consecutive terminals.

Consider a salesman $l \in K$ and let $t_i t_{i+1}$ be an edge between two consecutive terminals $t_i$ and $t_{i+1}$ of $T_l$. Consider a Steiner node $s$ of $S_l$ and let $(U^6, I^6)$ be the solution given by $U_l^6 = (U_l^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, s t_{i+1}\}$, $U_j^6 = U_j^0$ for each $j \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^6 = \bigcup_{j \in K} U_j^6$. As $(x^{U^6}, y^{I^6})$ is in $F_e^k$ and hence in $F$, by (19) we have $rx^{U^0} = rx^{U^0} - r_{t_i t_{i+1}}^l + r_{t_i s}^l + r_{s t_{i+1}}^l$ consequently, $r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l$. As $l, t_i, t_{i+1}$ and $s$ are arbitrarily chosen, we have

$$r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l \quad \text{for all } t_i, t_{i+1} \in T_l, s \in S_l, l \in K. \qquad (22)$$

Now, we will prove that all the edges linking a terminal to Steiner nodes have the same coefficient.

Consider a salesman $l \in K \setminus \{k\}$ and two Steiner nodes $s$ and $s'$ in $S_l$. Denote $(U^7, I^7)$ the solution given by $U_l^7 = (U_l^0 \setminus \{s t_i\}) \cup \{s s', s' t_i\}$, $U_j^7 = U_j^0$ for each $j \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^6 = \bigcup_{j \in K} U_j^6$. Clearly, $(x^{U^7}, y^{I^7})$ is in $F_e^k$ and thus in $F$. The incidence vectors of $(U^6, I^6)$ and $(U^7, I^7)$ satisfy equation $rx + qy = \beta$. As $q = 0$, this implies that $rx^{U^6} = rx^{U^7} = rx^{U^6} - r_{s t_i}^l + r_{s s'}^l + r_{s' t_i}^l$. Hence $r_{s t_i}^l = r_{s s'}^l + r_{s' t_i}^l$. By (21), we obtain that $r_{s t_{i+1}}^l = r_{s' t_{i+1}}^l$. As salesman $l$, and nodes $s, s'$ and $t_{i+1}$ are arbitrary, we then have

$$r_{s t_i}^l = r_{s' t_i}^l \quad \text{for all } t_i \in T_l, s, s' \in S_l, l \in K \setminus \{k\}.$$

In a similar way, we can show that

$$r_{s t_i}^k = r_{s' t_i}^k \quad \text{for all } t_i \in T_k, s, s' \in S_k, ss' \neq e.$$

The previous relation can be extended to $s_1, s_2$. In fact, if $\bar{s} \in S_k \setminus \{s_1, s_2\}$, by the relations above for every terminal $t_i$ of $T_k$, $r_{t_i s_1}^k = r_{t_i \bar{s}}^k$ and $r_{t_i s_2}^k = r_{t_i \bar{s}}^k$. As a consequence, we have $r_{t_i s_1}^k = r_{t_i s_2}^k$.

Overall, we obtain that

$$r_{s t_i}^l = r_{s' t_i}^l = \lambda_l^1(t_i) \quad \text{for all } t_i \in T_l, s, s' \in S_l, l \in K, \\ \text{for some } \lambda_l^1(t_i) \in \mathbb{R}. \qquad (23)$$
Now, let $\rho = r_{s_1s_2}^k$ and $\lambda^l = (\lambda_1^l, \lambda_2^l)$, $l \in K$ such that $\lambda_1^l = (\lambda_1^l(t_i), t_i \in T_k)$ where $\lambda_1^l(t_i)$ is as given by (23) and $\lambda_2^l = (\lambda_2^l(uv), u, v \in T_k, uv \notin U_l^0)$ such that $\lambda_2^l(uv) = r_{uv}^l - \lambda_1^l(u) - \lambda_1^l(v)$, $l \in K$.

Overall, we obtain that

$$r_{uv}^l = \begin{cases} \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_{i+1}, t_i, t_{i+1} \in T_l, \\ \lambda_1^l(u) & \text{if } u \in T_l, \\ \lambda_2^l(uv) + \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_j, t_i, t_j \in T_l, j > i, \\ 0 & \text{if } l \neq k \text{ and } u, v \in S_l, u \neq v, \\ 0 & \text{if } l = k \text{ and } u, v \in S_k, uv \neq s_1 s_2, \\ \rho & \text{if } l = k \text{ and } uv = s_1 s_2. \end{cases}$$

It is not hard to see that, $r^l = \rho a^l + \lambda_1^l M_1^l + \lambda_2^l M_2^l$, for all $l \in K$. Consequently, $r = \rho a + \lambda M$. □

**Theorem 3** *Inequality $y_e \le 1$ defines a facet of MSTSPOC(G, K, T).*

*Proof* See Appendix A, Sect. A.1. □

In what follows, we study the facial structure of the section cut inequalities (2). Consider a salesman $k \in K$ and a section $q_j^k = (t_j, t_{j+1}) \in T_q$. Consider W a subset of nodes of $V_j^k$ such that $t_j \in W$ and $t_{j+1} \in \bar{W}$.

**Theorem 4** *Inequality (2) defines a facet of MSTSPOC(G, K, T) if and only if $W \cap S_k \neq \emptyset \neq \bar{W} \cap S_k$.*

*Proof* See Appendix A, Sect. A.2. □

Now, we examine the facial structure of the disjunction inequalities (3).

**Theorem 5** *Consider a salesman $k \in K$, and $w \in V$. Inequality $\sum_{e \in \delta(w)} x_e^k \le 2$ defines a facet for MSTSPOC(G, K, T) if and only if w is not a terminal of $T_k$.*

*Proof* Let $F_w^k$ define the face induced by inequality $\sum_{e \in \delta(w)} x_e^k \le 2$, that is

$$F_w^k = \{(x, y) \in \text{MSTSPOC}(G, K, T) : \sum_{e \in \delta_G(w)} x_e^k = 2\}.$$

The necessity follows from Remark 2.

Suppose that $w \in S_k$, that is to say $w$ is a Steiner node of salesman $k$. Let $T_k = \{t_1, t_2, t_3, \dots, t_{|T_k|}\}$. We prove that inequalities (3) are facet defining by exhibiting $dim(\text{MSTSPOC}(G, K, T))$ points in $F_w^k$ that are affinely independent. These will be determined in two steps.
<figure><img src="image_7.png" /><figcaption>**Fig. 3** Facial aspect of disjunction inequalities: configuration</figcaption></figure>

We first exhibit $q_1 = (|K| + 1)|E| - \sum_{j \in K} \frac{|T_j|(|T_j| - 1)}{2} - |T_k| + 1$ solutions of MSTSPOC$(G, K, T)$ that are in $F_w^k$. These can be obtained as follows. Consider, without loss of generality, the first section of salesman $k$, that is $(t_1, t_2) \in T_k$ (see Fig. 3). Figure 3 shows the edges $e_1, e_2, \dots, e_{|T_k|-1}, e_{|T_k|}$. These are the edges linking the different terminals of $T_k$ to the node $w$. Now, consider all the possible solutions of MSTSPOC$(G, K, T)$ that are obtained by inserting the Steiner node $w$ between $t_1$ and $t_2$. Note that these solutions all use edges $e_1$ and $e_2$. Note also that, since $w$ always appears in these solutions, $w$ can be considered as a terminal for salesman $k$. Hence, the incidence vectors of these solutions are all in $F_w^k$ and are nothing but the possible solutions of the problem when $w$ is added as terminal of $T_k$ between $t_1$ and $t_2$. Note that all these solutions do not use any of the edges $e_3, e_4, \dots, e_{|T_k|-1}, e_{|T_k|}$. Hence, all the solutions built this way are also solutions of the polytope MSTSPOC$(G, K, T')$, where $T' = (T \setminus T_k) \cup T'_k$ with $T'_k = T_k \cup \{w\}$, is the new set of terminals of salesman $k$.

By Theorem 1, there are $dim(MSTSPOC(G, K, T')) + 1$ solutions affinely independent in MSTSPOC$(G, K, T')$. As all these solutions are in $F_w^k$ and $|T'_k| = |T_k| + 1$, we then obtain $(|K| + 1)|E| - \sum_{j \in K} \frac{|T_j|(|T_j| - 1)}{2} - |T_k| + 1$ solutions affinely independent in $F_w^k$.

Now, we will exhibit $q_2 = |T_k| - 1$ further solutions in $F_w^k$.

Consider a Steiner node $v \in S_k \setminus \{w\}$ and let $(U^j, I^j)$, $j = 2, \dots, |T_k|$, be the solution given by $U_k^j = (U_k^0 \setminus \{t_j t_{j+1}\}) \cup \{t_j w, w v, v t_{j+1}\}$, $U_p^j = U_p^0$ for each $p \in K \setminus \{k\}$, and $I^j = \cup_{p \in K} U_p^j$. Observe that solution $(U^j, I^j)$ is nothing but $(U^0, I^0)$ for which we delete edge $t_j t_{j+1}$ and insert the Steiner nodes $w$ and $v$ respectively, between $t_j$ and $t_{j+1}$. Also note that exactly two edges related to salesman $k$ are incident to $w$ in each of these solutions. Hence, the incidence vectors of these solutions all belong to $F_w^k$. Furthermore, it is clear that their incidence vectors are affinely independent.
<figure><img src="image_8.png" /><figcaption>Fig. 4 Facial aspect of disjunction inequalities: matrix</figcaption></figure>

Let $L$ be the matrix whose rows are the incidence vectors of all the solutions obtained above (see Fig. 4). Matrix $L$ is organized as follows. The first $m'_1$ columns of $L$ correspond to all the variables $y_e, e \in E$ and $x'_e, e \in E, l \in K$ except the variables $x_{e_1}^k, x_{e_2}^k, \dots, x_{e_{|T_k|}}^k$. The last $m'_2$ columns of $L$ are associated with the variables $x_{e_1}^k, x_{e_2}^k, \dots, x_{e_{|T_k|}}^k$. The first $q_1$ rows of $L$ correspond to the solutions obtained in the first step of the proof. The ones built in the second step correspond to the last $q_2$ rows of $L$.

Observe that the first $q_1$ solutions use only edges among $e_1$ and $e_2$ and do not use the $m'_2 - 2$ last edges of matrix $L$, that are edges between $w$ and terminals $t_3, \dots, t_{|T_k|}$. Moreover, these solutions do not use the edge $t_1t_2$. The other $q_2$ solutions uses each time only one of the $m'_2$ last edges that is different from $e_1$. Remark also that, in contrast with the first $q_1$ solutions, all the last $p_2$ solutions use the edge $t_1t_2$. As the first $q_1$ solutions are affinely independent, it can be easily seen that the $q_1 + q_2$ solutions are affinely independent.

Thus, we obtain

$$q_1 + q_2 = (|K| + 1)|E| - \sum_{j \in K} \frac{|T_j|(|T_j| - 1)}{2} = \dim(\text{MSTSPOC}(G, K, T)) \text{ affinely independent solutions of } F_w^k, \text{ which ends the proof.} \quad \square$$

## 4 Valid and facet-defining inequalities

In this section, we present several families of valid inequalities for the MSTSPOC. The main objective of this section is to study the facial aspects of these inequalities. In particular, we describe necessary conditions and sufficient conditions for these
inequalities to be facet-defining. For the validity of these inequalities the reader is referred to Taktak (2024).

## 4.1 Steiner cut inequalities

The first family of valid inequalities is a straight consequence related to the connectivity requirements of the problem. For a salesman $k \in K$, as the solution is a Steiner tour, every cut separating terminals of $T_k$ must contain at least 2 edges (Taktak 2024).

**Proposition 2** Consider a salesman $k \in K$ and let $W \subset V$ such that $W \cap T_k \neq \emptyset \neq \bar{W} \cap T_k$. Then

$$ \sum_{e \in \delta(W)} x_e^k \geq 2 \qquad (24) $$

is valid for MSTSPOC($G$, $K$, $T$).

Inequalities of type (24) are called Steiner cut inequalities.

**Theorem 6** Inequality (24) defines a facet of MSTSPOC($G$, $K$, $T$) if and only if the following hold.

1. W and $\bar{W}$ do not contain non-consecutive terminals of $T_k$, with at least one of them having its successor and predecessor in $\bar{W}$.

2. If $|W \cap T_k| = 2$ (resp. $|\bar{W} \cap T_k| = 2$), then $W \cap S_k \neq \emptyset$ (resp. $\bar{W} \cap S_k \neq \emptyset$),

3. If $|W \cap T_k| \geq 3$ (resp. $|\bar{W} \cap T_k| \geq 3$), then $S_k \subset W$ (resp. $S_k \subset \bar{W}$).

**Proof** Let $F_W^k$ be the face induced by inequality (24) that is

$$ F_W^k = \{(x, y) \in \text{MSTSPOC}(G, K, T) : \sum_{e \in \delta(W)} x_e^k = 2\}. $$

Necessity.

(1) Suppose that $W$ contains non-consecutive terminals $t_i$ and $t_j$ (see Fig. 5). Consider a solution $(U, I)$ of MSTSPOC. By (2), $t_i$ must be linked to $t_{i-1}$ and $t_{i+1}$ by two disjoint paths. Denote by $P_{i,1}$ and $P_{i,2}$ these paths. Also, there must exist a path $P_j$ linking $t_j$ to $\bar{W}$. As $t_i$ and $t_j$ are non-consecutive, this implies that the paths $P_{i,1}$, $P_{i,2}$, and $P_j$ all intersect cut $\delta(W)$. Thus, $x^k(\delta(W)) \geq 3$ and therefore $(x^U, y^I)$ does not belong to $F_W^k$. But this implies that $F_W^k = \emptyset$, and hence it can not define a facet.

(2) Now, suppose that condition 1) is satisfied, however condition 2) is not. Suppose for instance that $|W \cap T_k| \geq 3$ and $\bar{W} \cap S_k \neq \emptyset$. Consider, without loss of generality, the case where $|W \cap T_k| = 3$. Denote the terminals of $T_k$ in $W$ by $t_1, t_2$ and $t_3$ (see Fig. 6).

Consider a solution $(U, I)$ of MSTSPOC, with $U = (U_1, U_2, \dots, U_{|K|})$, such that $(x^U, y^I) \in F_W^k$. Let $e = t_2s$ be the edge between $t_2$ and a Steiner node $s \in \bar{W}$ (see Fig. 6). Suppose that $e \in U_k$. From constraints (2), there exist a path $P_1$ between $t_1$ and its successor in $\bar{W}$, a path $P_3$ between $t_3$ and its predecessor in $\bar{W}$ and a path $P_4$ between
<figure><img src="image_9.png" /><figcaption>**Fig. 6** Facial aspect for Steiner
Cut inequalities: condition 2</figcaption></figure>

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

$t_2$ and $t_3$. Moreover, as $e \in U_k$, by (2), it follows that $e$ must belong to the path joining $t_1$ and $t_2$. Therefore, there must exist a path between the Steiner node $s$ and the terminal $t_1$. This path is denoted $P_2$. Notice that $P_1, P_2, P_3$ and $\{e\}$ all intersect cut $\delta(W)$ (see Fig. 6). As a consequence, $x^k(\delta(W)) \ge 4$ and hence $(x^U, y^I)$ does not belong to $F_W^k$. This implies that every solution of MSTSPOC such that $(x^U, y^I) \in F_W^k$ satisfies $x_e^k = 0$. Hence $F_W^k \subset F_e^k$, where $F_e^k = \{(x, y) \in \text{MSTSPOC}(G, K, T) : x_e^k = 0\}$. Here, $e$ is not between non-consecutive terminals. By Theorem (2), it follows that $F_e^k$ define a facet of MSTSPOC$(G, K, T)$. Moreover, inequality (24) cannot be obtained as a combination of $x_e^k \ge 0$ and the equations of MSTSPOC$(G, K, T)$, i.e. 9 and 10. Consequently, $F_W^k$ cannot define a facet of MSTSPOC$(G, K, T)$.

3) Now, we will suppose that conditions 1) and 2) are satisfied. Assume however that condition 3) is not satisfied. Suppose, for example, that $|W \cap T_k| = 2$ but $W \cap S_k = \emptyset$ (see Fig. 7).

Consider a solution $(U, I)$ of MSTSPOC with $U = (U_1, U_2, \dots, U_{|K|})$ such that $t_1 t_2 \notin U_k$. As $x^k(t_1) = 2$ and $x^k(t_2) = 2$ hold, it follows that $x^k(\delta(W)) = 4$, and hence $(x^U, y^I) \notin F_W^k$. But this implies that $F_W^k$ is contained in the face induced by $x_{t_1 t_2}^k \le 1$. Hence $F_W^k$ cannot define a facet of MSTSPOC$(G, K, T).

*Sufficiency*.

See Appendix B, Sect. B.1. □
<figure><img src="image_11.png" /><figcaption>**Fig. 8** Steiner non-consecutive terminals: configuration 1</figcaption></figure>

## 4.2 Steiner non-consecutive terminals inequalities

In this section, we introduce a further family of valid inequalities for the MSTSPOC.

Consider a salesman $k \in K$ and let $w_j$ be a terminal of $T_k$. Consider a Steiner node $s$ of $S_k$ and denote $f = sw_j$. Denote the edges linking the Steiner node $s$ with the terminals of $T_k$ non-consecutive to $w_j$ by $e_1, e_2, \dots, e_p$ (see Fig. 8).

Remark that if the edge $f$ is considered in a solution $S$, it can be used to route only one among the sections $(w_{j-1}, w_j)$ and $(w_j, w_{j+1})$. Thus, (exactly) one edge of $\delta'(s) = \delta(s) \setminus \{f, e_1, e_2, \dots, e_p\}$ will be used in the solution $S$, and none of the edges $e_1, e_2, \dots, e_p$ could be considered in $S$. Therefore the inequality

$$ \sum_{e \in \delta'(s)} x_e^k \geq x_f^k, \qquad (25) $$

is valid.

In the following, we propose a generalization of inequality (25). Consider a salesman $k \in K$ such that $|T_k| \geq 4$ and let $w_j$ be a terminal of $T_k$. Consider a subset of Steiner nodes $S \subset S_k$ and let $\Pi = (V_0, V_1, \dots, V_p)$, $p \geq 4$ be a partition of $V$ (see Fig. 9) such that:

1. $V_0 = S$,

2. $V_1 \cap T_k = \{w_{j-l}, \dots, w_{j-2}, w_{j-1}\}$,
<figure><img src="image_12.png" /><figcaption>Fig. 9 Steiner non-consecutive terminals: configuration 2</figcaption></figure>

3. $V_2 = \{w_j\}$,

4. $V_3 \cap T_k = \{w_{j+1}, w_{j+2}, \dots, w_{j+l'}\}$,

5. $V_4, \dots, V_p$ are such that $V_i \cap T_k \neq \emptyset$ and $V_i \cap S_k = \emptyset$, $i = 4, \dots, p$ (see Fig. 9).

Denote by $F_{j-1}, F_j, F_{j+1}$ and $E_j$ the sets of edges of $E$ such that $F_{j-1} = [V_0, V_1]$, $F_j = [V_0, V_2]$, $F_{j+1} = [V_0, V_3]$, and $E_j = \bigcup_{i=4}^{p} ([V_0, V_i])$. With partition $\Pi$ and the sets $F_{j-1}, F_j, F_{j+1}$ and $E_j$, we associate the following inequality

$$ \sum_{e \in \delta'(S)} x_e^k \geq \sum_{e \in F_j} x_e^k, \qquad (26) $$

where $\delta'(S) = F_{j-1} \cup F_{j+1} = \delta(S) \setminus \{E_j, F_j\}$. Inequality (26) express the fact that the flow going from $w_j$ to a subset of Steiner nodes $S \subseteq S_k$ must be conserved in $S$ and only used to route sections that are adjacent to $w_j$.

**Proposition 3** *Inequality (26) is valid for MSTSPOC(G, K, T).*

*Proof* See Taktaq (2024). □

Inequalities of type (26) will be called *Steiner non-consecutive terminals inequalities*.

**Theorem 7** *Inequality (26) defines a facet of MSTSPOC(G, K, T) if and only if $V_1 \cap T_k = \{w_{j-1}\}$ and $V_3 \cap T_k = \{w_{j+1}\}$.*
<figure><img src="image_13.png" /><figcaption>**Fig. 10** Steiner F-partition configuration</figcaption></figure>

**Proof** See Appendix B, Sect. B.2. □

### 4.3 F-partition inequalities

The F-partition inequalities were first introduced by Mahjoub (1994). Further works have shown the efficiency of this class of inequalities in solving different variants of the survivable network design problem (see for instance Bendali et al. 2010; Huygens et al. 2004; Mahjoub and Pesneau 2008). In what follows, we discuss a variant of these inequalities for the MSTSPOC.

**Proposition 4** Consider a salesman $k \in K$ and let $\Pi = (V_0, \dots, V_p)$, $p \ge 2$ be a partition of V such that $|V_i \cap T_k| \ge 1$, $i = 1, \dots, p$. Let $F \subseteq \delta(V_0)$ such that $|F|$ is odd. Then

$$x^k(\delta(V_0, \dots, V_p) \setminus F) \ge p - \lfloor \frac{|F|}{2} \rfloor \quad (27)$$

is valid for MSTSPOC(G, K, T), and is called Steiner F-partition inequality.

**Proof** The following inequalities are valid for MSTSPOC(G, K, T)

$$ \begin{aligned} x^k(\delta(V_i)) &\ge 2 & \text{for all } i = 1, \dots, p, \\ -x^k(f) &\ge -1 & \text{for all } f \in F, \\ x^k(g) &\ge 0 & \text{for all } g \in \delta(V_0) \setminus F. \end{aligned} $$

By summing these inequalities, we obtain

$$2x^k(\delta(V_0, \dots, V_p) \setminus F) \ge 2p - |F|$$
By dividing by 2 and rounding up the right-hand side, we obtain

$$x^k(\delta(V_0, \dots, V_p) \setminus F) \geq p - \lfloor \frac{|F|}{2} \rfloor.$$

□

Observe that if $|F| = 2q + 1$ for some integer $q$, inequality (27) can also be written as

$$x^k(\delta(V_0, \dots, V_p) \setminus F) \geq p - q. \quad (28)$$

Now, we will study the facial aspect of these inequalities.

First, we give necessary conditions for these inequalities to be facet-defining.

**Theorem 8** *Inequality (27) defines a facet for MSTSPOC(G, K, T) only if*

1. Each $V_i$, $i \in \{1, \dots, p\}$ is such that

(i) $V_i$ does not contain non-consecutive terminals of $T_k$,

(ii) if $V_i$ contains (at least) three consecutive terminals, then $S_k \subset V_i$,

(iii) if $V_i$ contains exactly two consecutive terminals, then $V_i \cap S_k \neq \emptyset$.

2. $F$ does not contain an edge between non-consecutive terminals of $T_k$,

3. if $s$ and $s'$ are two Steiner nodes of $S_k$ such that $s \in V_i$ and $s' \in V_j$, $i, j \in \{1, \dots, p\}$ and $i \neq j$, then $V_i$ and $V_j$ contain consecutive terminals.

*Proof* Let $F_{\Pi,F}^k$ be the face induced by inequality (27), that is

$$F_{\Pi,F}^k = \{(x, y) \in \text{MSTSPOC}(G, K, T) : x^k(\delta(V_0, \dots, V_p) \setminus F) = p - \lfloor \frac{|F|}{2} \rfloor\},$$

*Necessity*

1) Suppose that condition 1) is not satisfied.

i) Suppose that $V_i$ contains non-consecutive terminals of $T_k$. Then, the following hold for any solution of MSTSPOC(G, K, T)

$$\begin{align*}
x^k(\delta(V_i)) &\geq 4 \\
x^k(\delta(V_j)) &\geq 2 \quad \text{for all } j \in \{1, \dots, p\} \setminus \{i\}, \\
-x^k(f) &\geq -1 \quad \text{for all } f \in F, \\
x^k(g) &\geq 0 \quad \text{for all } g \in \delta(W) \setminus F.
\end{align*}$$

By summing these inequalities, we obtain

$$2x^k(\delta(V_0, \dots, V_p) \setminus F) \geq 2p + 2 - |F|$$

This yields,

$$x^k(\delta(V_0, \dots, V_p) \setminus F) \geq p - \frac{|F|}{2}.$$
which means that any solution of MSTSPOC(G, K, T) does not belong to $F_{\Pi,F}^k$.
Hence, $F_{\Pi,F}^k$ cannot be facet-defining.

ii) Now, suppose that $V_i$ contains 3 consecutive terminals, say $t_1, t_2$ and $t_3$ and that $S_k \not\subseteq V_i$. Consider a Steiner node $s \in V_0$ ($s$ can also be chosen in any other $V_j, j \neq i$ such that $V_j \cap S_k \neq \emptyset$). Let $f = st_2$. Here $f$ cannot be considered in any solution of the face $F_{\Pi,F}^k$. The proof is similar to the previous case. By the use of edge $f$, we have $x^k(\delta(V_i)) \geq 4$). Consequently, every solution of MSTSPOC inducing a point in $F_{\Pi,F}^k$ satisfies $x_j^k = 0$. This implies that $F_{\Pi,F}^k$ is not facet defining for MSTSPOC(G, K, T).

iii) The proof of this case is similar to that of ii).

2) In the sequel, one can suppose that condition 1) is satisfied. Suppose that $F$ contains an edge $e = t_i w_j$ between two non-consecutive terminals $t_i$ and $w_j$. Clearly, the following inequalities are valid for MSTSPOC(G, K, T)

$$ 
\begin{array}{lll}
x^k(\delta(V_i)) & \geq 2 & \text{for all } i = 1, \dots, p, \\
-x^k(f) & \geq -1 & \text{for all } f \in F \setminus \{e\}, \\
x^k(g) & \geq 0 & \text{for all } g \in \delta(W) \setminus F, \\
-x^k(e) & = 0 &
\end{array}
$$

By summing these inequalities, we obtain

$$ 2x^k(\delta(V_0, \dots, V_p) \setminus F) \geq 2p - (|F| - 1). $$

By dividing by 2, we obtain

$$ x^k(\delta(V_0, \dots, V_p) \setminus F) \geq p - \lfloor \frac{|F|}{2} \rfloor. $$

As a consequence, $F_{\Pi,F}^k$ cannot be facet-defining.

3) Suppose there are two Steiner nodes $s$ and $s'$ of $S_k$ and two sets $V_i$ and $V_j, i \neq j$ such that $s \in V_i$ and $s' \in V_j$ and $V_i$ and $V_j$ do not contain consecutive terminals, let $f = ss'$. In what follows, we will prove that $f$ can never be considered in a solution of $F_{\Pi,F}^k$. First, we state the following claim.

**Claim** If edge $f$ is considered in some solution whose incidence vector is in $F_{\Pi,F}^k$, then $x^k(\delta(V_i)) + x^k(\delta(V_j)) \geq 6$.

**Proof of the Claim:** See Appendix B, Sect. B.3. □

Using the previous Claim and the results developed in the previous sections, the following inequalities are valid for MSTSPOC(G, K, T)

$$ 
\begin{array}{lll}
x^k(\delta(V_i)) + x^k(\delta(V_j)) & \geq 6, \\
x^k(\delta(V_i)) & \geq 2 & \text{for all } l \in \{1, \dots, p\} \setminus \{i, j\}, \\
-x^k(f) & \geq -1 & \text{for all } f \in F, \\
x^k(g) & \geq 0 & \text{for all } g \in \delta(W) \setminus F.
\end{array}
$$
The sum of these inequalities implies

$$2x^k(\delta(V_0, \dots, V_p) \setminus F) \geq 2(p-2) + 6 - |F| = 2p + 2 - |F|.$$

By dividing by 2, we obtain

$$x^k(\delta(V_0, \dots, V_p) \setminus F) \geq p + 1 - \frac{|F|}{2}.$$

This implies that

$$x^k(\delta(V_0, \dots, V_p) \setminus F) \geq p - \lfloor \frac{|F|}{2} \rfloor + \frac{1}{2},$$

and hence (27) is not satisfied with equality.

Consequently, every solution of $F_{\Pi,F}^k$ satisfies $x_f^k = 0$, yielding that $F_{\Pi,F}^k$ does not define a facet for MSTSPOC(G, K, T). □

Next, we will give sufficient conditions for inequalities (27) to be facet-defining.

**Theorem 9** *Inequality (27) defines a facet for MSTSPOC(G, K, T) if*

(a) every $V_i$, $i = 1, \dots, p$ is such that $|V_i \cap T_k| = 1$,

(b) $V_0$ is such that $V_0 \cap T_k = \emptyset$ and $|V_0 \cap S_k| \geq \lceil \frac{|F|}{2} \rceil$,

(c) $F$ is such that

(i) $|F| = p$ if $p$ is odd and $|F| = p - 1$ if $p$ is even,

(ii) $|F \cap \delta(V_i)| \leq 1$ for each $i \in \{1, \dots, p\}$,

(iii) for each $s_j \in V_0$, if $F \cap \delta(s_j) = \{s_j u, s_j v\}$, where $u \in V_i$ and $v \in V_j$, $i \neq j$, then $V_i$ and $V_j$ must contain consecutive terminals.

*Proof* See Appendix B, Sect. B.4. □

The families of valid inequalities, previously studied, as well as the theoretical results obtained in this section, have been used within a Branch-and-Cut algorithm whose results are presented in Taktak (2024). As pointed out in Taktak (2024), these inequalities have shown to be very effective in solving the problem for a variety of random and realistic instances.

# 5 Further valid inequalities

In this section, we present further families of valid inequalities. These inequalities are extensions of inequalities valid for related problems.

## 5.1 Generalized Steiner partition inequalities

The partition inequalities have got a particular interest and arise as valid inequalities for several well-known problems. Introduced by Nash-Williams for the spanning tree
problem in the beginning of the 60's Nash-Williams (1961), these inequalities have been later widely studied (Chopra 1989). In the beginning of the 90's, Grötschel and Monma use partitions for the connected subgraph polytope (Grötschel and Monma 1990). Later, Stoer (1992) introduces partition inequalities for both kECON (k-Edge Connected) and kNCON (k-Node Connected) subgraph problems. The author investigates necessary conditions and sufficient conditions for these inequalities to be facet-defining for the kECON and the kNCON polytopes. The partition inequalities have also been efficient in modeling the Steiner tree problem. In Chopra and Rao (1994a, b), Chopra and Rao introduce the *Steiner partition inequalities* and study their facial aspect for the Steiner tree polytope. In Barahona and Mahjoub (1995), Barahona and Mahjoub show that the partition inequalities, together with bound, cut and odd-wheel inequalities give a complete description of the 2NCON for Halin graphs. In further work, Baïou et al. (2000) propose a separation algorithm for these inequalities based on submodular functions. For more results related to partition inequalities, the reader is referred to Baïou et al. (2011).

Thus it seems to be interesting to look for an adaptation of partition inequalities to our problem. In what follows, we give a more general class of inequalities called *Generalized Steiner Partition Inequalities*.

**Proposition 5** Consider a salesman $k \in K$ and let $\Pi = (V_1, ..., V_p)$ be a partition of $V$ such that $|V_i \cap T_k| \ge 1, i = 1, ..., p (p \ge 2)$. Suppose that $V_1, ..., V_r, r \le p$ contain respectively $q_i \ge 2, i = 1, ..., r$ non-succcessive terminals (or sequences of terminals).

Let $S \subseteq S_k$ be a subset of Steiner nodes of salesman k. Then

$$x^k(\delta_{G \setminus S}(V_1, V_2, ..., V_p)) \ge (p + \sum_{i=1}^{r} q_i - r) - |S| \quad (29)$$

is valid for MSTSPOC($G, K, T$).

**Proof** The idea of the proof is to replace each time the subset $V_i$ of the partition $\Pi$ by $q_i$ equivalent disjoint subsets. The proof is done by induction on $r$.

First, notice that if $|S| \ge p + \sum_{i=1}^{r} q_i - r$, inequalities (29) are redundant with respect to the trivial inequalities (5).

In the sequel, we assume that $|S| < p + \sum_{i=1}^{r} q_i - r$.

If $r = 0$, this means that all the sets $V_i, i = 1, ..., p$ contain either only one terminal or a sequence of successive terminals. In this case, inequalities (29) are equivalent to the following ones

$$x^k(\delta_{G \setminus S}(V_1, V_2, ..., V_p)) \ge p - |S| \quad (30)$$

Consider a solution $(U, I)$ of the problem with $U = (U_1, ..., U_{|T_k|})$. If $U_k$ does not use any node of $S$, then $U_k$ uses at least $p$ edges from $\delta_{G \setminus S}(V_1, ..., V_p)$. As any node of $S$ can be used to route at most one section $t_i t_{i+1}$, then $U_k$ must intersect $\delta_{G \setminus S}(V_1, ..., V_p)$ in at least $p - |S|$ edges, and thus inequality (30) is satisfied.
Now, suppose that (29) is valid for $r = h > 0$ and let us prove its validity for $r = h + 1$.

We know that $r$ ($r = h+1$) subsets of the partition contain non-succcessive terminals (or sequences of terminals). Recall that these sets are the $r$ first sets of the partition $\Pi$, denoted $V_1, V_2, ..., V_r$. This means that the node sets $V_{r+1}, ...V_p$ contain only successive terminals (or sequences of successive terminals). Suppose, without loss of generality, that the terminals (or sequences of terminals) of the sets $V_{r-1}$ and $V_r$ are pairwise non-succcessive. Note that this hypothesis is not restrictive since we can always consider it by a suitable numbering of the sets $V_1, V_2, ..., V_r$.

Consequently, if we combine the sets $V_{r-1}$ and $V_r$ in one set called $W$, we get exactly $q_{r-1} + q_r$ non-succcessive terminals (or sequences of terminals) in $W$.

Now, consider the new partition $\Pi' = (V'_1, ..., V'_{p'})$ where $p' = p - 1$, obtained from $\Pi$ by combining the two node sets $V_{r-1}$ and $V_r$. That is, $\Pi'$ is defined as follows,

$$V'_{j} = \begin{cases} V_{j} & \text{if } j \in \{1, ..., r-2\}, \\ V_{r-1} \cup V_{r} & \text{if } j = r-1, \\ V_{j+1} & \text{if } j \in \{r, ..., p'\}. \end{cases}$$

Observe that by construction, partition $\Pi'$ contains exactly $r' = r - 1$ node sets $V'_1, V'_2, ..., V'_{r'}$ such that $V'_i, i = 1, ..., r'$ contains $q'_i, i = 1, ..., r'$ non-succcessive terminals (or sequences of terminals). Remark also that $q'_i = q_i$ for all $i = 1, ..., r' - 1$ and $q'_{r'} = q_{r-1} + q_r$. Since by hypothesis, (29) is assumed to be valid for the rank $h$ and $r' = r - 1 = h + 1 - 1 = h$, we can write

$$x^k(\delta_{G\setminus S}(V'_1, V'_2, ..., V'_{p'})) \geq (p' + \sum_{i=1}^{r'} q'_i - r') - |S| \quad (31)$$

Recall that by construction, the terminals of $V_{r-1}$ and $V_r$ are pairwise non-succ excessive. This means that there are no edges linking $V_{r-1}$ to $V_r$ in any solution, and hence $x^k(\delta_{G\setminus S}(V_{r-1}, V_r)) = 0$. We can deduce, in consequence, that:

$$x^k(\delta_{G\setminus S}(V'_1, V'_2, ..., V'_{p'})) = x^k(\delta_{G\setminus S}(V_1, V_2, ..., V_p)) \quad (32)$$

Moreover, we know that

$$\begin{align*} (p' + \sum_{i=1}^{r'} q'_i - r') - |S| &= (p - 1 + \sum_{i=1}^{r-2} q_i + q'_{r-1} - (r-1)) - |S| \\ &= (p - 1 + \sum_{i=1}^{r-2} q_i + (q_{r-1} + q_r) - r + 1) - |S| \\ &= (p + \sum_{i=1}^{r} q_i - r) - |S|. \end{align*}$$
Consequently,

$$ (p' + \sum_{i=1}^{r'} q'_{i} - r') - |S| = (p + \sum_{i=1}^{r} q_{i} - r) - |S|. \quad (33) $$

The result follows from (32) and (33). □

Notice that the Generalized Steiner Partition inequalities written for particular values of $p, r$, and $|S|$, coincide with some known inequalities in the literature.

- If $p = 2, r = 0$ and $|S| = 1$, denote $W = V_1$ ($\overline{W} = V_2$) and $S = \{s\}$. The Generalized Steiner Partition inequalities (29) are hence equivalent to

$$ x^k(\delta_{G\setminus s}(W)) \geq 1. \quad (34) $$

Inequalities (34) are known as the *node cut constraints* for the 2NCON problem (Stoer 1992).

- If $p > 2$ and $r = 0$, the Generalized Steiner Partition inequalities (29) are equivalent to

$$ x^k(\delta_{G\setminus S}(V_1, V_2, \dots, V_p)) \geq p - |S| \quad (35) $$

Inequalities (35) known as the *node partition constraints* for the kNCON problem (Stoer 1992).

In Appendix C, we investigate the relationship between inequalities (29) and inequalities (24), (3) and (5).

## 5.2 Generalized disjunction inequalities

In this section, we introduce further valid inequalities which, as inequalities (3) and inequalities (26), come from the disjunction constraint in the problem.

**Proposition 6** Consider a salesman $k \in K$. Let $W \subset V$ and $F \subseteq \delta(W)$ such that $|F|$ is odd. Then

$$ x^k(E(W)) + x^k(F) \leq |W| + \lfloor \frac{|F|}{2} \rfloor \quad (36) $$

is valid for MSTPOC($G, K, T$).

**Proof** We prove the validity of inequalities (36) for MSTPOC($G, K, T$) using a Chvátal-Gomory procedure.

Clearly, the following inequalities are valid for MSTPOC($G, K, T$)

$$ \begin{aligned} x^k(\delta(v_i)) &\leq 2 & \text{for all } v_i \in W, \\ x^k(f) &\leq 1 & \text{for all } f \in F, \\ -x^k(g) &\leq 0 & \text{for all } g \in \delta(W) \setminus F. \end{aligned} $$
By summing these inequalities, we obtain

$$2(x^k(E(W)) + x^k(F)) \leq 2|W| + |F|$$

Now, by dividing by 2 and rounding up the right-hand side, we obtain

$$x^k(E(W)) + x^k(F) \leq |W| + \lfloor \frac{|F|}{2} \rfloor.$$

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

Inequalities (36) will be called generalized disjunction inequalities.

Notice that these inequalities look like the *blossom inequalities* for the TSP which coincide with the 2-matching inequalities introduced by Edmonds (1965) in the context of matching problems (Edmonds 1965).

In the following section, we will get more profit from this relationship and propose to our problem an analogue of the well-known *Comb inequalities* of the TSP.

## 5.3 Steiner comb inequalities

Comb inequalities have been first discovered by Chvátal (1973) in the mid-1970s. After that, Grötschel and Padberg (1979) proposed a generalization of these inequalities.

The name "comb" comes from the form of these inequalities. Indeed, the vertices of the graph are partitioned in subsets $H$ and $T_1, ..., T_{2k+1}$, where $H$ is called the *handle* and $T_1, ..., T_{2k+1}$ are the *teeth*.

This type of inequalities have interested many researchers who show that they are a powerful source of cutting planes for some classical problems and particularly the TSP. The efficiency of the combs was first shown (Grötschel 1980) by finding the optimal tour through 120 German cities, using a very small number of inequalities. Comb inequalities have been also shown effective for survivable network design problems. In Stoer (1992), Stoer introduces several classes of comb inequalities for 2NCON, 2ECON, and the kNCON problems. A deep facial investigation of the proposed inequalities is also held by the author.

**Proposition 7** Consider a salesman $k \in K$. Consider a family of subsets of $V$, $H$ called the handle and $T_{th_1}, T_{th_2}, ..., T_{th_p}$ called the teeth such that

1. $p \geq 3$ and odd,

2. for every two disjoint teeth $T_{th_i}$ and $T_{th_j}$, $T_{th_i} \cap T_{th_j} = \emptyset$,

3. for each tooth $T_{th_j}$, $|T_{th_j} \cap T_k| \geq 2$,

4. for each tooth $T_{th_j}$, $H \cap T_{th_j} \neq \emptyset$, $T_{th_j} \setminus H \neq \emptyset$, and one of the following conditions is satisfied

a) if $(H \cap T_{th_j}) \cap T_k = \emptyset$, then $T_{th_j} \setminus H$ contains at least 2 non successive terminals (or sequences of terminals),

b) if $(T_{th_j} \setminus H) \cap T_k = \emptyset$, then $H \cap T_{th_j}$ contains at least 2 non successive terminals (or sequences of terminals),
<figure><img src="image_15.png" /><figcaption>**Fig. 11** Steiner Comb configuration</figcaption></figure>

c) $(H \cap T_{th_j}) \cap T_k \neq \emptyset$ and $(T_{th_j} \setminus H) \cap T_k \neq \emptyset$.

Then

$$x^k(\delta(H)) + \sum_{i=1}^{p} x^k(\delta(T_{th_j})) \geq 3p + 1 \quad (37)$$

is valid for MSTSPOC(G, K, T).

**Proof** The proof of the validity here is in the same spirit as the one given for the general comb inequalities for the TSP Applegate et al. (2007).

Let us define for each $i = 1, ..., p$ the parameter $c_i$ as follows:

$$c_i = \begin{cases} 1 & \text{if } x^k \text{ contains an edge between } H \cap T_{th_j} \text{ and } T_{th_j} \setminus H \\ 0 & \text{otherwise} \end{cases}$$

By condition 2) the teeth are pairwise disjoint and we have $x^k(\delta(H)) \geq \sum_{i=1}^{p} c_i$. In addition, by definition of parameter $c_i$, we have $\sum_{i=1}^{p} c_i \leq p$. Since $x^k(\delta(H))$ is even and $p$ is odd, we conclude that:

$$x^k(\delta(H)) \geq 2 \sum_{i=1}^{p} c_i - p + 1 \quad (38)$$

Moreover, by conditions 3) and 4), we can write for each tooth $T_{th_j}$

$$x^k(\delta(T_{th_j})) \geq 4 - 2ci \quad (39)$$

By (39) for all $i = 1, ..., p$ together with (38), we obtain

$$x^k(\delta(H)) + \sum_{i=1}^{p} x^k(\delta(T_{th_j})) \geq 2 \sum_{i=1}^{p} c_i - p + 1 + \sum_{i=1}^{p} (4 - 2c_i).$$
Notice that the parameter $c_i$ will disappear since quantity $2 \sum_{j=1}^{p} c_j$ will be simplified. This yields

$$x^k(\delta(H)) + \sum_{j=1}^{p} x^k(\delta(T_{th_j})) \geq -p+1 + \sum_{j=1}^{p} 4 = 3p+1.$$

□

# 6 Conclusion

In this paper, we have studied the Multiple Steiner TSP with Order Constraints (MST-SPOC). We have considered the ILP formulation proposed for the problem in Borne et al. (2013). We have investigated the associated polytope and studied the facial aspect of its basic constraints. We have also described new families of valid inequalities, and stated necessary conditions and sufficient conditions for these inequalities to be facet-defining. Further classes of valid inequalities inspired from the TSP ones have also been presented. The theoretical results presented in this paper are computationally validated in Tak Tak (2024).

Several future research lines are interesting to consider. First, we would like to investigate the facial aspect of the Generalized Disjunction Inequalities and Steiner Comb Inequalities described in the last section. It would also be interesting to study some extensions of our problem. We may think about adding hop-constraints for the section paths. That is the length of the path between two consecutive terminals of a given salesman is not allowed to exceed a threshold of hops, which may have many practical interpretations.

# A Appendix: Facial investigation

## A.1 Proof of Theorem 3

Let $F_e$ be the corresponding induced face, that is

$$F_e = \{(x, y) \in \text{MSTSPOC}(G, K, T) : y_e = 1\}.$$

Denote inequality $y_e \leq 1$ by $ax + by \leq \alpha$. Let $rx + qy \leq \beta$ be a valid inequality defining a facet $F$ of MSTSPOC$(G, K, T)$. Assume that $F_e \subseteq F$. We prove that there exist $\rho \in \mathbb{R}$ and $\lambda = (\lambda^j, j \in K)$, $\lambda^j \in \mathbb{R}^{|T_j|+p_j}$ for $j \in K$, such that $q = \rho b$ and $r = \rho a + \lambda M$ (where $r = (r^1, r^2, \dots, r^{|K|})$ with $r^i \in \mathbb{R}^m, i = 1, \dots, |K|$ and $M$ is the matrix of equations defined above). Note here that $b_{e'} = 0$ for all $e' \in E \setminus \{e\}$. Moreover, $a = (a^1, a^2, \dots, a^{|K|})$ is such that $a^i \in \mathbb{R}^m$ with $a^i = 0, i = 1, \dots, |K|$.

In the sequel, we will distinguish two cases.

**Case 1.** $e \in I^0$.

Suppose $e = t_1t_2$ is an edge between two consecutive terminals $t_1$ and $t_2$ of a salesman $k \in K$. We first show that every edge $f$ in $E \setminus I^0$ has a coefficient $q_f$
equal to 0. Consider the solution $(U^0, I^0)$ and let $(U^1, I^1)$ be the solution defined by $U^1 = U^0$ and $I^1 = I^0 \cup \{f\}$. It is clear that $(x^{U^0}, y^{I^0})$ and $(x^{U^1}, y^{I^1})$ are in $F_e$ and hence in $F$. Therefore, $rx^{U^0} + qy^{U^0} = rx^{U^0} + qy^{U^0} + q_f$ and thus $q_f = 0$. As $f$ is arbitrary in $E \setminus I^0$, this implies that

$$q_f = 0 \quad \text{for all } f \in E \setminus I^0. \qquad (40)$$

Now, consider a salesman $l \in K$, and let $t_i t_{i+1} \in I^0 \setminus \{e\}$. Consider a Steiner node $s$ of $S_l$ and let $(U^2, I^2)$ be the solution given by $U_l^2 = (U_l^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, s t_{i+1}\}$, $U_j^2 = U_j^0$, $j \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^2 = \bigcup_{j \in K} U_j^2$. And let $(U^3, I^3)$ be the solution defined by $U^3 = U^2$ and $I^3 = I^2 \cup \{t_i t_{i+1}\}$. As $(x^{U^2}, y^{I^2})$ and $(x^{U^3}, y^{I^3})$ are in $F_e$ and thus in $F$, we have $rx^{U^2} + qy^{I^2} = rx^{U^2} + qy^{I^2} + q_{t_i t_{i+1}}$, which implies that $q_{t_i t_{i+1}} = 0$. As $t_i$ and $t_{i+1}$ are arbitrary in $T_l$, and $l$ is arbitrary in $K$, we obtain that

$$q_f = 0 \quad \text{for all } f \in I^0 \setminus \{e\}. \qquad (41)$$

Next, we will establish some relations between the components of vector $r$.

Consider a salesman $l \in K$ and let $s$ and $s'$ be two Steiner nodes of $S_l$. Consider again the solution $(U^0, I^0)$ and let $(U^4, I^4)$ be the solution such that $U_l^4 = U_l^0 \cup \{ss'\}$, $U_j^4 = U_j^0$ for $j \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^4 = \bigcup_{j \in K} U_j^4$. Clearly $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ are both in $F_e$ and hence in $F$. Consequently, $rx^{U^0} + qy^{I^0} = rx^{U^0} + qy^{I^0} + r_{ss'}^l + q_{ss'}$. By (40), it follows that $r_{ss'}^l = 0$. And therefore,

$$r_{ss'}^l = 0 \quad \text{for all } s, s' \in S_l. \qquad (42)$$

Now, consider $l \in K$, $l \neq k$ and let $t_i$ and $t_{i+1}$ be two consecutive terminals of $T_l$ and $s$ a Steiner node of $S_l$. Let $(U^5, I^5)$ be given as follows $U_l^5 = (U_l^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, s t_{i+1}\}$, $U_j^5 = U_j^0$ for $j \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^5 = \bigcup_{j \in K} U_j^5$. Obviously $(x^{U^0}, y^{I^0})$ and $(x^{U^5}, y^{I^5})$ are in $F_e$ and then in $F$. This means that $rx^{U^0} + qy^{I^0} = rx^{U^0} + qy^{I^0} - r_{t_i t_{i+1}}^l + r_{t_i s}^l + r_{s t_{i+1}}^l - q_{t_i t_{i+1}} + q_{t_i s} + q_{s t_{i+1}}$. By (40), $q_{t_i s} = q_{s t_{i+1}} = 0$. Moreover, as $l \neq k$, by (41), $q_{t_i t_{i+1}} = 0$. This yields $r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l$. As salesman $l$ and nodes $s, t_i, t_{i+1}$ are arbitrary, we obtain that

$$r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l \quad \text{for all } t_i, t_{i+1} \in T_l, s \in S_l, l \in K \setminus \{k\}. \qquad (43)$$

Similarly, we also obtain that

$$r_{t_i t_{i+1}}^k = r_{t_i s}^k + r_{s t_{i+1}}^k \quad \text{for all } t_i, t_{i+1} \in T_k, s \in S_k, t_i t_{i+1} \neq e. \qquad (44)$$

Now, we will prove that the previous relation remains valid even when $t_i t_{i+1} = e$. Consider a Steiner node $s$ of $S_k$ and let $(U^6, I^6)$ be the solution defined by $U_k^6 = (U_k^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, s t_{i+1}\}$, $U_j^6 = U_j^0$ for $j \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^6 = (\bigcup_{j \in K} U_j^6) \cup \{e\}$. We have that $(x^{U^0}, y^{I^0})$ and $(x^{U^6}, y^{I^6})$ are in $F_e$ and thus in
F. This implies that $rx^{U^0} + qy^{I^0} = rx^{U^0} + qy^{I^0} - r_{ti_{t_i+1}}^k + r_{ti_s}^k + r_{st_{t_i+1}}^k - q_{ti_{t_i+1}} + q_{ti_s} + q_{st_{t_i+1}} + q_{ti_{t_i+1}}$ (recall that $e = t_i t_{i+1}$). By (40) it follows that $q_{ti_s} = q_{st_{t_i+1}} = 0$, implying that $r_{ti_{t_i+1}}^k = r_{ti_s}^k + r_{st_{t_i+1}}^k$. Hence,

$$r_{ti_{t_i+1}}^k = r_{ti_s}^k + r_{st_{t_i+1}}^k \quad \text{for all } s \in S_k, t_i t_{i+1} = e. \quad (45)$$

From (44) and (45), we get

$$r_{ti_{t_i+1}}^k = r_{ti_s}^k + r_{st_{t_i+1}}^k \quad \text{for all } t_i, t_{i+1} \in T_k, s \in S_k. \quad (46)$$

In what follows, we will prove that all the edges linking a terminal to Steiner nodes of a salesman $l$ have the same coefficient in $r^l$.

First, suppose that $l \neq k$ and consider two Steiner nodes $s$ and $s'$ in $S_l$. consider again the solution $(U^5, I^5)$ given previously and denote by $(U^7, I^7)$ the solution given as follows $U_l^7 = (U_l^5 \setminus \{st_i\}) \cup \{ss', s't_i\}$, $U_j^7 = U_j^5$ for each $j \in \{1, \dots, |K|\} \setminus l$ and $I^7 = \cup_{j \in K} U_j^7$. It is clear that $(x^{U^7}, y^{I^7})$ is in $F_e$ and thus in $F$. The incidence vectors of $(U^5, I^5)$ and $(U^7, I^7)$ satisfy that equation $rx + qy = \beta$. This, together with equations (40), allow to write $rx^{U^5} = rx^{U^7} = rx^{U^5} - r_{st_i}^l + r_{ss'}^l + r_{s't_i}^l$. Hence, $r_{st_i}^l = r_{ss'}^l + r_{s't_i}^l$. By (42), we obtain that $r_{st_{i+1}}^l = r_{s't_i}^l$.

Similarly, we can show that, if $l = k$, $r_{st_i}^k = r_{s't_i}^k$.

Thus, we get

$$\begin{align}
r_{st_i}^l &= r_{s't_i}^l = \lambda_1^l(t_i) \quad &\text{for all } t_i \in T_l, s, s' \in S_l, l \in K, \nonumber \\
& &\text{for some } \lambda_1^l(t_i) \in \mathbb{R}. \tag{47}
\end{align}$$

Now, let $\rho = q_e$ and $\lambda^l = (\lambda_1^l, \lambda_2^l)$, $l \in K$ such that $\lambda_1^l = (\lambda_1^l(t_i), t_i \in T_k)$ where $\lambda_1^l(t_i)$ is as given by (47) and $\lambda_2^l = (\lambda_2^l(uv), u, v \in T_k, uv \notin U_l^0)$ such that $\lambda_2^l(uv) = r_{uv}^l - \lambda_1^l(u) - \lambda_1^l(v)$, $l \in K$.

The coefficients $r_{uv}^l$ for all $uv \in E$ and $l \in K$ can then be expressed in terms of $\lambda_1^l$ and $\lambda_2^l$ as follows

$$r_{uv}^l = \begin{cases}
\lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_{i+1}, t_i, t_{i+1} \in T_l, \\
\lambda_1^l(u) & \text{if } u \in T_l, v \in S_l, \\
\lambda_2^l(uv) + \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_j, t_i, t_j \in T_l : j > i, \\
0 & \text{if } uv = s_i s_j, s_i, s_j \in S_l : j \neq i,
\end{cases}$$

yielding $r^l = \lambda_1^l M_1^l + \lambda_2^l M_2^l$ for all $l \in K$ as desired. Consequently, we have $q = \rho b$ and $r = \rho a + \lambda M$.

**Case 2.** The remaining case (i.e., $e \in E \setminus I^0$) is similarly proved.
## A.2 Proof of Theorem 4

Let $F_W^{k,j}$ be the face induced by the section cut inequalities (2) corresponding to $k, j$ and $W$, that is

$$F_W^{k,j} = \{(x, y) \in \text{MSTSPOC}(G, K, T) : \sum_{e \in \delta_{G_k,j}(W)} x_e^k = 1\}.$$

### Necessity.

Assume for instance that $W \cap S_k = \emptyset$. Thus, $W$ is reduced to a single node, namely terminal $t_j$. Consider a solution $(U, I)$ of MSTSPOC with $U = (U_1, U_2, \dots, U_{|K|})$ the edge sets corresponding to the salesmen $1, \dots, |K|$. Let $U_{k,j}$ be the restriction of $U_k$ on $G_j^k$. By constraints (2), $U_k$ must have two edges incident to $t_j$. Hence, $U_{k,j}$ must have exactly one edge incident to $t_j$. As $W \cap S_k = \emptyset$, the cut $\delta_{G_j^k}(W)$ is reduced to that edge. And therefore, the incidence vector of $(U, I)$, $(x^U, y^I)$ belong to $F_W^{k,j}$. But, this implies that $F_W^{k,j} \in \text{MSTSPOC}(G, K, T)$, and hence it cannot be facet defining.

The case where $\overline{W} \cap S_k = \emptyset$ is similar.

### Sufficiency.

Throughout the proof, we will suppose that $W$ and $\overline{W}$ contain each at least one Steiner node of $S_k$.

Denote inequality (2) corresponding to $k, j$ and $W$ by $ax+by \le \alpha$ and let $F_W^{k,j} = \{(x, y) \in \text{MSTSPOC}(G, K, T) : ax+by = \alpha\}$. Let $rx+qy \le \beta$ be a valid inequality defining a facet $F$ of MSTSPOC$(G, K, T)$ such that $F_W^{k,j} \subseteq F$. In the following, we prove that there exist $\rho \in \mathbb{R}$ and $\lambda = (\lambda^1, l \in K)$, $\lambda^l \in \mathbb{R}^{|T|+p_l}$ for $l \in K$, such that $q = \rho b$ and $r = \rho a + \lambda M$ (where $r = (r^1, r^2, \dots, r^{|K|})$ with $r^i \in \mathbb{R}^m, i = 1, \dots, |K|$ and $M$ is the matrix of equations defined above). Note here that $a = (a^1, a^2, \dots, a^{|K|})$ is such that $a^l \in \mathbb{R}^m, i = 1, \dots, |K|$ with $a^i = 0$ for $i \in \{1, \dots, |K|\} \setminus \{k\}, a_e^k \neq 0$ for every $e \in \delta_{G_j^k}(W)$ and $a_e^k = 0$ for every $e' \in E \setminus \delta_{G_j^k}(W)$. Also, note that $b = 0$.

First, we prove that $q = 0$.

Consider the solution $(U^0, I^0)$ and let $e \in E \setminus I^0$ be an arbitrary edge. Let $(U^1, I^1)$ be the solution given by $I^1 = I^0 \cup \{e\}$ and $U^1 = U^0$. Both $(U^0, I^0)$ and $(U^1, I^1)$ induce solutions in $F_W^{k,j}$. This implies that their incidence vectors satisfy equation $rx+qy = \beta$. Consequently, $rx^{U^0}+qy^{I^0} = qx^{U^0}+qy^{I^0}+q_e$, implying that $q_e = 0$. Since $e$ is arbitrarily chosen in $E \setminus I^0$, we have

$$q_e = 0 \quad \text{for all } e \in E \setminus I^0. \qquad (48)$$

Similarly, we can show that

$$q_e = 0 \quad \text{for all } e \in I^0. \qquad (49)$$

By (48) and (49) we then have

$$q_e = 0 \quad \text{for all } e \in E. \qquad (50)$$
Next, we will establish some relations between the components of vector $r$.

First, we consider the edges between Steiner nodes.

Let $l \in K \setminus \{k\}$ and $s$ and $s'$ be two Steiner nodes of $S_l$. Consider the solution $(U^0, I^0)$ and let $(U^4, I^4)$ be the solution defined by $U_l^4 = U_l^0 \cup \{ss'\}$, $U_p^4 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus l$ and $I^4 = \bigcup_{p \in K} U_p^4$. Clearly, $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ are both in $F_W^{k,j}$ and thus in $F$. This implies that $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ satisfy $rx+qy = \beta$. Since $q=0$, we have $r^k x^{U^0} = r^k x^{U^0} + r_{ss'}^l$, which yields $r_{ss'}^l = 0$. As salesman $l$ and nodes $s$ and $s'$ are all arbitrary, we have

$$r_{ss'}^l = 0 \quad \text{for all } s, s' \in S_l, l \in K \setminus \{k\}. \qquad (51)$$

Similarly, we obtain that

$$r_{ss'}^k = 0 \quad \text{for all } s, s' \in S_k, ss' \notin \delta_{G_j^k}(W). \qquad (52)$$

Now, we will consider the edges between terminals.

Consider a salesman $l \in K \setminus \{k\}$ and let $t_i$ and $t_{i+1}$ be two terminals of $T_l$. Let $s$ be a Steiner node of $S_l$. Consider the solution $(U^6, I^6)$ given by $U_l^6 = (U_l^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, s t_{i+1}\}$, $U_p^6 = U_p^0$, for each $p \in \{1, \dots, |K|\} \setminus l$ and $I^6 = \bigcup_{p \in K} U_p^6$. As $(x^{U^6}, y^{I^6})$ is in $F_W^{k,j}$ and hence in $F$, it follows that $rx^{U^0} = rx^{U^0} - r_{t_i t_{i+1}}^l + r_{t_i s}^l + r_{s t_{i+1}}^l$, implying that $r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l$. Salesman $l$ as well as nodes $s, t_i$ and $t_{i+1}$ are all arbitrary, therefore,

$$r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l \quad \text{for all } t_i, t_{i+1} \in T_l, s \in S_l, l \in K \setminus \{k\}. \qquad (53)$$

If $t_i$ and $t_{i+1}$ are terminals of $T_k$ such that $t_i t_{i+1} \neq t_j t_{j+1}$, we can also prove along the same line that

$$r_{t_i t_{i+1}}^k = r_{t_i s}^k + r_{s t_{i+1}}^k \quad \text{for all } t_i, t_{i+1} \in T_k, s \in S_k, t_i t_{i+1} \neq t_j t_{j+1}. \qquad (54)$$

Consider now two Steiner nodes $s$ and $s'$ of $S_k$ such that $s \in W$ and $s' \in \bar{W}$ (recall that $W \cap S_k \neq \emptyset$ and $\bar{W} \cap S_k \neq \emptyset$). Let $(U^7, I^7)$ be the solution defined as follows: $U_k^7 = (U_k^0 \setminus \{t_j t_{j+1}\}) \cup \{t_j s, ss', s' t_{j+1}\}$, $U_p^7 = U_p^0$, for each $p \in \{1, \dots, |K|\} \setminus k$ and $I^7 = \bigcup_{p \in K} U_p^7$. As $(x^{U^7}, y^{I^7})$ and $(x^{U^4}, y^{I^4})$ are both in $F_W^{k,j}$ and thus in $F$, we have $rx^{U^0} = rx^{U^7} = rx^{U^0} - r_{t_j t_{j+1}}^k + r_{t_j s}^k + r_{ss'}^k + r_{s' t_{j+1}}^k$, yielding $r_{t_j t_{j+1}}^k = r_{t_j s}^k + r_{ss'}^k + r_{s' t_{j+1}}^k$. Hence, we have

$$r_{t_j t_{j+1}}^k = r_{t_j s}^k + r_{ss'}^k + r_{s' t_{j+1}}^k \quad \text{for all } s, s' \in S_k, s \in W \text{ and } s' \in \bar{W}. \qquad (55)$$

In what follows, we will look at the coefficients of edges between terminals and Steiner nodes.

To this end, consider first a salesman $l \in K \setminus \{k\}$ and let $(U^8, I^8)$ be the solution obtained from $(U^6, I^6)$ as follows, $U_l^8 = (U_l^0 \setminus \{s t_{i+1}\}) \cup \{ss', s' t_{i+1}\}$, $U_p^8 = U_p^0$ for
each $p \in \{1, \dots, |K|\} \setminus I$ and $I^8 = \bigcup_{j \in K} U_j^8$, where $s$ and $s'$ are Steiner nodes of $S_l$. Since $(x^{U^6}, y^{I^6})$ and $(x^{U^8}, y^{I^8})$ are both in $F_W^{k,j}$ and thus in $F$, this implies that $rx^{U^6} = rx^{U^6} - r_{st_{i+1}}^l + r_{ss'}^l + r_{s't_{i+1}}^{l'}$. By (51) it follows that $r_{st_{i+1}}^l = r_{s't_{i+1}}^{l'}$. As salesman $l$ and nodes $s, s'$ and $t_i$ are all arbitrary, we have

$$r_{st_i}^l = r_{s't_i}^l = \lambda_1^l(t_i) \quad \begin{array}{l} \text{for all } t_i \in T_l, s, s' \in S_l, l \in K \setminus \{k\}, \\ \text{for some } \lambda_1^l(t_i) \in \mathbb{R}. \end{array} \qquad (56)$$

If $l=k$, along the same way we obtain that

$$\begin{array}{ll} r_{st_i}^k = r_{s't_i}^k = \lambda_1^k(t_i) & \text{for all } t_i \in T_k, s, s' \in S_k, ss' \notin \delta_{G_j^k}(W) \\ & \text{for some } \lambda_1^k(t_i) \in \mathbb{R}. \end{array} \qquad (57)$$

Suppose now that $s$ and $s'$ are Steiner nodes of $S_k$ such that $ss' \notin \delta_{G_j^k}(W)$. Consider the solution $(U^9, I^9)$ defined as follows, $U_k^9 = (U_k^0 \setminus \{t_j t_{j+1}\}) \cup \{t_j s, st_{j+1}\}$, $U_p^9 = U_p^0$, for each $p \in \{1, \dots, K\} \setminus k$ and $I^9 = \bigcup_{p \in K} U_p^9$. We also define $(U^{10}, I^{10})$ by: $U_k^{10} = (U_k^9 \setminus \{t_j s\}) \cup \{t_j s', ss'\}$, $U_p^{10} = U_p^9$, for each $p \in \{1, \dots, K\} \setminus k$ and $I^{10} = \bigcup_{p \in K} U_p^{10}$. Solutions $(x^{U^9}, y^{I^9})$ and $(x^{U^{10}}, y^{I^{10}})$ are both in $F_W^{k,j}$ and thus in $F$. As a consequence, we have $rx^{U^9} = rx^{U^{10}} = rx^{U^{10}} - r_{t_j s}^k + r_{t_j s'}^k + r_{ss'}^k$, yielding $r_{t_j s}^k = r_{t_j s'}^k + r_{ss'}^k$. By (52), it follows that $r_{t_j s}^k = r_{t_j s'}^k$. Similarly, we can show that $r_{t_{j+1}s}^k = r_{t_{j+1}s'}^k$. And since $s$ and $s'$ are arbitrary in $S_k$, we have

$$\begin{array}{ll} r_{t_i s}^k = r_{t_i s'}^k = \lambda_1^k(t_i) & \text{for all } s, s' \in S_k, ss' \notin \delta_{G_j^k}(W), t_i \in \{t_j, t_{j+1}\}, \\ & \text{for some } \lambda_1^k(t_i) \in \mathbb{R}. \end{array} \qquad (58)$$

Now, suppose that $ss' \in \delta_{G_j^k}(W)$ with $s' \in W$ and $s \in \bar{W}$. Along the same line, we can prove that $r_{t_j s}^k = r_{t_j s'}^k + r_{ss'}^k$ and $r_{t_{j+1}s}^k = r_{t_{j+1}s'}^k + r_{ss'}^k$. As $s$ and $s'$ are arbitrary, we have the following

$$r_{t_i s}^k = r_{t_i s'}^k + r_{ss'}^k \quad \begin{array}{l} \text{for all } s, s' \in S_k, s' \in W, s \in \bar{W}, \\ t_i \in \{t_j, t_{j+1}\}. \end{array} \qquad (59)$$

Now, we will go back to the case that we left in the beginning of the proof, concerning edges between Steiner nodes of $S_k$ that belong to $\delta_{G_j^k}(W)$.

Consider salesman $k$ and let $s_1, s_2, s_3$ and $s_4$ be Steiner nodes of $S_k$ such that, $s_1$ and $s_3$ are in $W$, and $s_2$ and $s_4$ are in $\bar{W}$ ($s_1$ and $s_3$, $s_2$ and $s_4$ may be the same). By (59) and as $s_1 s_2, s_3 s_4 \in \delta_{G_j^k}(W)$, we have that, $r_{t_{j+1}s_1}^k = r_{t_{j+1}s_2}^k + r_{s_1 s_2}^k$ and $r_{t_{j+1}s_3}^k = r_{t_{j+1}s_4}^k + r_{s_3 s_4}^k$. Moreover, by (58) and since $s_1 s_3, s_2 s_4 \notin \delta_{G_j^k}(W)$, it follows that $r_{t_{j+1}s_1}^k = r_{t_{j+1}s_3}^k$ and $r_{t_{j+1}s_2}^k = r_{t_{j+1}s_4}^k$, yielding $r_{s_1 s_2}^k = r_{s_3 s_4}^k$. As $s_1, s_2, s_3$ and $s_4$ are all arbitrary in $S_k$, we then have
$$ 
\begin{array}{l}
r_{s_1 s_2}^k = r_{s_3 s_4}^k = \rho \qquad \text{for all } s_1, s_2, s_3, s_4 \in S_k, \\
\qquad s_1 s_2, s_3 s_4 \in \delta_{G_j}^k(W) \qquad (60) \\
\text{for some } \rho \in \mathbb{R}.
\end{array}
$$

Now, let $\rho \in \mathbb{R}$ be as given by (60) and $\lambda^l = (\lambda_1^l, \lambda_2^l)$, $l \in K$ such that $\lambda_1^l = (\lambda_1^l(t_i), t_i \in T_k)$ where $\lambda_1^l(t_i)$ is as given by (56), (57), (58) and (59). $\lambda_2^l = (\lambda_2^l(uv), u, v \in T_k, uv \notin U_l^0)$ such that $\lambda_2^l(uv) = r_{uv}^l - \lambda_1^l(u) - \lambda_1^l(v)$, $l \in K$.

Overall, the coefficients $r_{uv}^l$ for all $uv \in E$ and $l \in K$ can then be expressed in terms of $\rho$, $\lambda_1^l$ and $\lambda_2^l$ as follows

$$ 
\begin{array}{l}
r_{uv}^l = \left\{
\begin{array}{ll}
\lambda_1^l(u) + \lambda_1^l(v) & \text{if } l \neq k, uv = t_i t_{i+1}, t_i, t_{i+1} \in T_l, \\
\lambda_1^k(u) + \lambda_1^k(v) & \text{if } l = k, uv = t_i t_{i+1}, t_i, t_{i+1} \in T_k, uv \neq t_j t_{j+1}, \\
\rho + \lambda_1^k(u) + \lambda_1^k(v) & \text{if } l = k, uv = t_j t_{j+1}, \\
\lambda_1^l(u) & \text{if } l \neq k, u \in T_l, v \in S_l, \\
\lambda_1^k(u) & \text{if } l = k, u \in T_k \setminus \{t_j, t_{j+1}\}, v \in S_k, \\
\rho + \lambda_1^k(u) & \text{if } l = k, u \in T_k \setminus \{t_j, t_{j+1}\}, v \in S_k, uv \in \delta_{G_j}^k(W), \\
\lambda_2^l(uv) + \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_{i'}, t_i, t_{i'} \in T_l, i' > i, \\
0 & \text{if } l \neq k \text{ and } uv = s_i s_{i'}, s_i, s_{i'} \in S_l, i' \neq i, \\
0 & \text{if } l = k \text{ and } uv = s_i s_{i'}, s_i, s_{i'} \in S_k, s_i s_{i'} \notin \delta_{G_j}^k(W), \\
\rho & \text{if } l = k \text{ and } uv = s_i s_{i'}, s_i, s_{i'} \in S_k, s_i s_{i'} \in \delta_{G_j}^k(W).
\end{array}
\right.
\end{array}
$$

Clearly, $r^l = \rho a^l + \lambda_1^l M_1^l + \lambda_2^l M_2^l$, for all $l \in K$. As a consequence, $r = \rho a + \lambda M$, and the proof is complete.

# B Appendix: Valid Inequalities

## B.1 Proof of Theorem 6 (Sufficiency)

In the sequel, we suppose that conditions 1), 2) and 3) are satisfied.

Denote inequality (24) corresponding to $k$ and $W$ by $ax+by \le \alpha$. Let $rx+qy \le \beta$ be a valid inequality defining a facet $F$ of MSTSPOC($G$, $K$, $T$). In the following, we prove that there exist $\rho \in \mathbb{R}$ and $\lambda = (\lambda^l, l \in K)$, $\lambda^l \in \mathbb{R}^{|T_l|+|P_l|}$ for $l \in K$, such that $q = \rho b$ and $r = \rho a + \lambda M$.

First, we prove that $q = 0$.

Consider the solution $(U^0, I^0)$ and let $e \in E \setminus I^0$ be an arbitrary edge. Consider also the solution $(U^1, I^1)$ such that $I^1 = I^0 \cup \{e\}$ and $U^1 = U^0$. Both induce vectors that are in $F_W^k$ and thus in $F$. This implies that $q_e = 0$. Since $e$ is arbitrarily chosen in $E \setminus I^0$, we then have

$$ q_e = 0 \quad \text{for all } e \in E \setminus I^0. \qquad (61) $$

Now, consider the solution $(U^2, I^2)$ obtained as follows. Consider a salesman $l \in K$ and let $e = t_i t_{i+1}$ be an edge between two consecutive terminals $t_i$ and $t_{i+1}$ of $T_l$.
Let $U_l^2 = (U_l^0 \setminus \{e\}) \cup \{t_i s, st_{i+1}\}$ where $s \in S_l$ is a Steiner node of salesman $l$. In addition, let $U_j^2 = U_j^0, j = 1, \dots, K, j \neq l$, and $I^2 = \cup_{j \in K} U_j^2$. Now, let us define the solution $(U^3, I^3)$ given by $U^3 = U^2$ and $I^3 = I^2 \cup \{e\}$. Both are feasible solutions of MSTSPOC inducing vectors that are in $F_W^k$ and hence satisfying equation $rx + qy = \beta$. As a consequence, we obtain that $q_e = 0$. As $e$ is arbitrary in $I^0$, this yields

$$q_e = 0 \quad \text{for all } e \in I^0. \qquad (62)$$

By (61) and (62) we then have

$$q_e = 0 \quad \text{for all } e \in E. \qquad (63)$$

Next, we will examine vector $r$.

Consider a salesman $l \in K \setminus \{k\}$ and let $s$ and $s'$ be two Steiner nodes of $S_l$. Consider the solution $(U^0, I^0)$ defined above and let $(U^4, I^4)$ be the pair defined by $U_l^4 = U_l^0 \cup \{ss'\}$, $U_p^4 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^4 = \cup_{p \in K} U_p^4$. It is clear that $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ are both in $F_W^k$ and thus in $F$. This implies that $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ satisfy $rx + qy = \beta$. Since $q = 0$, we have $rx^{U^0} = rx^{U^4} = r^k x^{U^0} + r_{ss'}^l$, which implies $r_{ss'}^l = 0$. As salesman $l$ and Steiner nodes $s$ and $s'$ are arbitrary, we have

$$r_{ss'}^l = 0 \quad \text{for all } s, s' \in S_l, l \in K \setminus \{k\}. \qquad (64)$$

Similarly, we can show that,

$$r_{ss'}^k = 0 \quad \text{for all } s, s' \in S_k, ss' \notin \delta(W). \qquad (65)$$

The case where $ss' \in \delta(W)$ for $s, s' \in S_k$ will be treated at the end of the proof.

Consider a salesman $l \in K \setminus \{k\}$ and let $t_i$ and $t_{i+1}$ be two terminals of $T_l$. Let $s$ be a Steiner node of $S_l$. Consider the solution $(U^6, I^6)$ given by $U_l^6 = (U_l^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, st_{i+1}\}$, $U_p^6 = U_p^0$, for each $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^6 = \cup_{p \in K} U_p^6$. As $(x^{U^6}, y^{I^6})$ is in $F_W^k$ and hence in $F$, it follows that $rx^{U^0} = rx^{U^0} - r_{t_i t_{i+1}}^l + r_{t_i s}^l + r_{s t_{i+1}}^l$, implying that $r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l$. Therefore

$$r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l \quad \text{for all } t_i, t_{i+1} \in T_l, s \in S_l, l \in K \setminus \{k\}. \qquad (66)$$

Now, suppose that $t_i$ and $t_{i+1}$ are terminals of $T_k$ such that $t_i t_{i+1} \notin \delta(W)$. Suppose, without loss of generality, that $t_i$ and $t_{i+1}$ are in $W$. Consider a Steiner node $s \in S_k \cap W$. Along the same line, we can prove that $r_{t_i t_{i+1}}^k = r_{t_i s}^k + r_{s t_{i+1}}^k$. Hence,

$$r_{t_i t_{i+1}}^k = r_{t_i s}^k + r_{s t_{i+1}}^k \quad \text{for all } t_i, t_{i+1} \in T_k \cap W \text{ (resp. } T_k \cap \bar{W}\text{)}, \\ s \in S_k \cap W \text{ (resp. } S_k \cap \bar{W}\text{)}. \qquad (67)$$
Suppose now that $t_i t_{i+1} \in \delta(W)$ such that $t_i \in W$ and $t_{i+1} \in \overline{W}$. Consider two Steiner nodes $s$ and $s'$ of $S_k$ such that $s \in W$ and $s' \in \overline{W}$. Let $(U^7, I^7)$ be the solution given by $U_k^7 = (U_k^0 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, ss', s't_{i+1}\}$, $U_p^7 = U_p^0$, for each $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^7 = \cup_{p \in K} U_p^7$. As $(x^{U^0}, y^{I^0})$ and $(x^{U^7}, y^{I^7})$ are both in $F_W^k$ and thus in $F$, we have $rx^{U^0} = rx^{U^7} = rx^{U^0} - r_{t_i t_{i+1}}^k + r_{t_i s}^k + r_{ss'}^k + r_{s't_{i+1}}^k$, yielding $r_{t_i t_{i+1}}^k = r_{t_i s}^k + r_{ss'}^k + r_{s't_{i+1}}^k$. As nodes $t_i, t_{i+1}, s$ and $s'$ are all arbitrary, we then have

$$r_{t_i t_{i+1}}^k = r_{t_i s}^k + r_{ss'}^k + r_{st_{i+1}}^k \quad \begin{array}{l} \text{for all } t_i, t_{i+1} \in T_k, t_i \in W, t_{i+1} \in \overline{W}, \\ \text{for all } s, s' \in S_k, s \in W, s' \in \overline{W}. \end{array} \qquad (68)$$

In the following, we will look at the coefficients of edges between a terminal and Steiner nodes.

To this end, consider a salesman $l \in K \setminus \{k\}$ and let $(U^8, I^8)$ be the pair obtained from $(U^7, I^7)$ as follows: $U_l^8 = (U_l^7 \setminus \{st_{i+1}\}) \cup \{ss', s't_{i+1}\}$, $U_p^8 = U_p^7$ for each $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^8 = \cup_{j \in K} U_j^8$, where $s$ and $s'$ are Steiner nodes of $S_l$. Since $(x^{U^7}, y^{I^7})$ and $(x^{U^8}, y^{I^8})$ are both in $F_W^{k,j}$ and thus in $F$, this implies $rx^{U^7} = rx^{U^8} = rx^{U^7} - r_{st_{i+1}}^l + r_{ss'}^l + r_{s't_{i+1}}^l$. By (64), it follows that $r_{st_{i+1}}^l = r_{s't_{i+1}}^l$. As salesman $l$, and nodes $t_i, s$ and $s'$ are arbitrary, we have

$$r_{st_i}^l = r_{s't_i}^l = \lambda_1^l(t_i) \quad \begin{array}{l} \text{for all } t_i \in T_l, s, s' \in S_l, l \in K \setminus \{k\}, \\ \text{for some } \lambda_1^l(t_i) \in \mathbb{R}. \end{array} \qquad (69)$$

Similarly, we can show that

$$r_{t_i s}^k = r_{t_i s'}^k = \lambda_1^l(t_i) \quad \begin{array}{l} \text{for all } t_i, t_{i+1} \in T_k \cap W \text{ (resp. } T_k \cap \overline{W}\text{),} \\ \text{for all } s, s' \in S_k \cap W \text{ (resp. } S_k \cap \overline{W}\text{),} \\ \text{for some } \lambda_1^l(t_i) \in \mathbb{R}. \end{array} \qquad (70)$$

Now, consider again the terminal $t_i$ and suppose now that $\{t_{i-1}t_i, t_i t_{i+1}\} \not\subseteq \delta(W)$. Consider the two Steiner nodes $s$ and $s'$ and suppose that $t_i$ and the set $\{s, s'\}$ are situated on different sides of the cut $\delta(W)$. That is $t_i s \in \delta(W)$ and $st_{i+1} \in \delta(W)$. The same reasoning as the previous ones enables us to write

$$r_{st_i}^k = r_{s't_i}^k = \lambda_1^k(t_i) \quad \begin{array}{l} \text{for all } t_i \in T_k, s, s' \in S_k, st_i \in \delta(W) \text{ and } s't_i \in \delta(W), \\ \text{for some } \lambda_1^l(t_i) \in \mathbb{R}. \end{array} \qquad (71)$$

Now, we will consider the case where $t_i$ and $s'$ are in $W$ and $s \in \overline{W}$. Similarly, we can have the following relation $r_{t_i s}^k = r_{t_i s'}^k + r_{ss'}^k$. And since $t_i, s$ and $s'$ are arbitrary, we have

$$r_{st_i}^k = r_{s't_i}^k + r_{ss'}^k \quad \begin{array}{l} \text{for all } t_i \in T_k, s, s' \in S_k, \\ st_i \in \delta(W) \text{ and } s't_i \notin \delta(W). \end{array} \qquad (72)$$
Now, we will go back to the case that we left in the beginning of the proof, concerning edges between Steiner nodes of $S_k$ that belong to $\delta(W)$.

Consider salesman $k$, a terminal $t_1$ of $T_k$ and let $s_1, s_2, s_3$ and $s_4$ be Steiner nodes of $S_k$ such that, $s_1$ and $s_3$ are in $W$, and $t_1, s_2$ and $s_4$ are in $\overline{W}$ ($s_1$ and $s_3$, resp. $s_2$ and $s_4$, may be the same). By (72) and as $s_1s_2 \in \delta(W)$ and $s_3s_4 \in \delta(W)$, we have the following, $r_{t_1s_1}^k = r_{t_1s_2}^k + r_{s_1s_2}^k$ and $r_{t_1s_3}^k = r_{t_1s_4}^k + r_{s_3s_4}^k$. Moreover, by (71) and since $s_1s_3 \notin \delta(W)$ and $s_2s_4 \notin \delta(W)$, it follows that $r_{t_1s_1}^k = r_{t_1s_3}^k$ and $r_{t_1s_2}^k = r_{t_1s_4}^k$, yielding $r_{s_1s_2}^k = r_{s_3s_4}^k$. As $s_1, s_2, s_3$ and $s_4$ are all arbitrary in $S_k$, we then have

$$ r_{s_1s_2}^k = r_{s_3s_4}^k = \rho \quad \begin{array}{l} \text{for all } s_1, s_2, s_3, s_4 \in S_k, \\ \text{for some } \rho \in \mathbb{R}. \end{array} \qquad (73) $$

Now, let $\rho \in \mathbb{R}$ be as given by (73) and $\lambda_1^l = (\lambda_1^l, \lambda_2^l)$, $l \in K$ such that $\lambda_1^l = (\lambda_1^l(t_i), t_i \in T_k)$ where $\lambda_1^l(t_i)$ is as given by (69), (70) and (71). $\lambda_2^l = (\lambda_2^l(uv), u, v \in T_k, uv \notin U_l^0)$ such that $\lambda_2^l(uv) = r_{uv}^l - \lambda_1^l(u) - \lambda_1^l(v), l \in K$.

Overall, the coefficients $r_{uv}^l$ for all $uv \in E$ and $l \in K$ can then be expressed in terms of $\rho, \lambda_1^l$ and $\lambda_2^l$ as follows

$$ r_{uv}^l = \begin{cases} \lambda_1^l(u) + \lambda_1^l(v) & \text{if } l \neq k, uv = t_i t_{i+1}, t_i, t_{i+1} \in T_l, \\ \lambda_1^k(u) + \lambda_1^k(v) & \text{if } l = k, uv = t_i t_{i+1}, t_i, t_{i+1} \in T_k, uv \notin \delta(W), \\ \rho + \lambda_1^k(u) + \lambda_1^k(v) & \text{if } l = k, uv \in \delta(W), \\ \lambda_1^l(u) & \text{if } l \neq k, u \in T_l, v \in S_l, \\ \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \notin \delta(W) \\ \rho + \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \in \delta(W) \\ \lambda_2^l(uv) + \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_j, t_i, t_j \in T_l, j > i, \\ 0 & \text{if } l \neq k \text{ and } uv = s_i s_j, s_i, s_j \in S_l, j \neq i, \\ 0 & \text{if } l = k \text{ and } uv = s_i s_j, s_i, s_j \in S_k, uv \notin \delta(W), \\ \rho & \text{if } l = k \text{ and } uv = s_i s_j, s_i, s_j \in S_k, uv \in \delta(W). \end{cases} $$

Clearly, $r^l = \rho a^l + \lambda_1^l M_1^l + \lambda_2^l M_2^l$, for all $l \in K$. As a consequence, $r = \rho a + \lambda M$ and the result follows.

## B.2 Proof of Theorem 7

### Necessity

Assume for instance that $V_1$ contains terminals predecessor to $w_{j-1}$ (the case when $V_3$ contains terminals successor to $w_{j+1}$ can be treated in a similar way). Consider the partition $\Pi' = (V'_0, V'_1, \dots, V'_p)$, where

$$ V'_1 = V_1 \setminus \{w_{j-l}, \dots, w_{j-2}\}, $$

$$ V'_4 = V_4 \cup \{w_{j-l}, \dots, w_{j-2}\}, $$

$$ V'_i = V_i, \text{ otherwise.} $$
It is clear that the left-hand side of inequality (26) with respect to partition $\Pi'$ is less or equal than that of partition $\Pi$. Moreover, the right-hand side of inequality (26) is the same for both partitions $\Pi$ and $\Pi'$. This implies that inequality (26) induced by partition $\Pi'$ dominates the one induced by partition $\Pi$. As a consequence, (26) cannot be facet defining for MSTSPOC($G$, $K$, $T$).

### Sufficiency

In what follows, we will assume that $V_1 \cap T_k = \{w_{j-1}\}$ and $V_3 \cap T_k = \{w_{j+1}\}$. Note here that $V_1$ and $V_3$ may contain Steiner nodes of $S_k$.

Denote inequality (26) by $ax + by \le \alpha$ and let

$$F_{j,S}^k = \{(x, y) \in \text{MSTSPOC}(G, K, T) : \sum_{e \in F_{j-1} \cup F_{j+1}} x_e^k = \sum_{e \in F_j} x_e^k\}.$$

Let $rx + qy \le \beta$ be a valid inequality defining a facet $F$ of MSTSPOC($G$, $K$, $T$) such that $F_{j,S}^k \subseteq F$. In the following, we will prove that there exist $\rho \in \mathbb{R}$ and $\lambda = (\lambda^l, l \in K)$, $\lambda^l \in \mathbb{R}^{|T|+p_l}$ for $l \in K$, such that $q = \rho b$ and $r = \rho a + \lambda M$. Notice here that $a = (a^1, a^2, \dots, a^{|K|})$ such that $a^i \in \mathbb{R}^m$, $i = 1, \dots, |K|$ with $a^i = 0$ for $i \in \{1, \dots, |K|\} \setminus \{k\}$, $a_e^k \ne 0$ for every $e \in F_{j-1} \cup F_j \cup F_{j+1}$ and $a_{e'}^k = 0$ for every $e' \in E \setminus (F_{j-1} \cup F_j \cup F_{j+1})$. Remark also that $b = 0$.

First, we prove that $q = 0$.

Consider the solution $(U^0, I^0)$ and let $e \in E \setminus I^0$ be an arbitrary edge. Consider the solution $(U^1, I^1)$ given by $U^1 = U^0$ and $I^1 = I^0 \cup \{e\}$. Note that the incidence vectors of solutions $(U^0, I^0)$ and $(U^1, I^1)$ are in $F_{j,S}^k$. This means that $(x^{U^0}, y^{I^0})$ and $(x^{U^1}, y^{I^1})$ satisfy equation $rx+qy = \beta$. Consequently, $rx^{U^0}+qy^{I^0} = rx^{U^1}+qy^{I^1} = qx^{U^0}+qy^{I^0} + q_e$, implying that $q_e = 0$. Since $e$ is arbitrarily chosen in $E \setminus I^0$, we have

$$q_e = 0 \quad \text{for all } e \in E \setminus I^0. \qquad (74)$$

Now, consider the solution $(U^2, I^2)$ obtained as follows. Consider a salesman $l \in K$ and let $e = w_i w_{i+1}$ be an edge between two consecutive terminals $w_i$ and $w_{i+1}$ of $T_l$. Let $U_l^2 = (U_l^0 \setminus \{e\}) \cup \{w_i s, w_{i+1} s\}$ where $s \in S_l$ is a Steiner node of salesman $l$ (if $l = k$ $s$ could be either in $S$ or in $S_k \setminus S$). In addition, let $U_j^2 = U_j^0$, $j = 1, \dots, |K|$, $j \ne l$, and $I^2 = \cup_{j \in K} U_j^2$. Now, let us define the solution $(U^3, I^3)$ given by $U^3 = U^2$ and $I^3 = I^2 \cup \{e\}$. The incidence vectors of both solutions $(U^2, I^2)$ and $(U^3, I^3)$ are in $F_{j,S}^k$, and hence they satisfy equation $rx+qy = \beta$. As a consequence, we have $rx^{U^2}+qy^{I^2} = rx^{U^3}+qy^{I^3} = rx^{U^2}+qy^{I^2}+q_e$, which implies that $q_e = 0$. Recall that $I^0$ is the set of edges between the consecutive terminals of all the salesmen. As $e$ is arbitrary in $I^0$, this yields

$$q_e = 0 \quad \text{for all } e \in I^0. \qquad (75)$$
By (74) and (75) we then have

$$q_e = 0 \quad \text{for all } e \in E. \tag{76}$$

Now, we will examine the coefficients between Steiner nodes.

Consider a salesman $l \in K \setminus \{k\}$ and let $s$ and $s'$ be two Steiner nodes of $S_l$. Consider the solution $(U^0, I^0)$ defined above and let $(U^4, I^4)$ be the pair defined by $U_l^4 = U_l^0 \cup \{ss'\}$, $U_p^4 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^4 = \bigcup_{p \in K} U_p^4$. Clearly $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ are both in $F_{j,S}^k$ and thus in $F$. This implies that $(x^{U^0}, y^{I^0})$ and $(x^{U^4}, y^{I^4})$ satisfy equation $rx + qy = \beta$. Since $q = 0$, we have $rx^{U^0} = r^k x^{U^0} + r_{ss'}^l$, which yields $r_{ss'}^l = 0$. As salesman $l$ and Steiner nodes $s$ and $s'$ are arbitrary, we have

$$r_{ss'}^l = 0 \quad \text{for all } s, s' \in S_l, l \in K \setminus \{k\}. \tag{77}$$

Now, consider salesman $k$ and suppose that $s$ and $s'$ are Steiner nodes of $S_k$ such that $ss' \notin \delta(S)$. That is, $ss'$ is an edge between two Steiner nodes which are both either in $S$ or in $S_k \setminus S$. Let $(U^5, I^5)$ be the solution defined as follows $U_k^5 = U_k^0 \cup \{ss'\}$, $U_p^5 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^5 = \bigcup_{p \in K} U_p^5$. Obviously, $(x^{U^5}, y^{I^5})$ is in $F_{j,S}^k$ and hence in $F$. As a consequence, the incidence vectors of $(U^0, I^0)$ and $(U^5, I^5)$ satisfy equation $rx + qy = \beta$. Since $q = 0$, it follows that $r_{ss'}^k = 0$. As $s$ and $s'$ are arbitrary in $S_k$, we have that

$$r_{ss'}^k = 0 \quad \text{for all } s, s' \in S_k, ss' \notin \delta(S). \tag{78}$$

Now, consider four Steiner nodes of salesman $k$ denoted $s_1, s_2, s_3$ and $s_4$ such that $s_1, s_3 \in V_0$ and $s_2, s_4 \in V_1$ (resp. $s_2, s_4 \in V_3$). Note that $s_1$ may coincide with $s_3$, and similarly $s_2$ may coincide with $s_4$. Let $(U^6, I^6)$ be the solution defined as follows $U_k^6 = U_k^0 \setminus w_j w_{j+1} \cup \{w_j s_1, s_1 s_2, s_2 w_{j+1}\}$, $U_p^6 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^6 = \bigcup_{p \in K} U_p^6$. Consider also the solution $(U^7, I^7)$ given by $U_k^7 = U_k^0 \setminus w_j w_{j+1} \cup \{w_j s_3, s_3 s_4, s_4 w_{j+1}\}$, $U_p^7 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^7 = \bigcup_{p \in K} U_p^7$. It is clear that $(x^{U^6}, y^{I^6})$ and $(x^{U^7}, y^{I^7})$ are in $F_{j,S}^k$ and hence in $F$. Since $q = 0$, this implies that $rx^{U^6} = rx^{U^6} - r_{s_1 s_2}^k + r_{s_1 s_3}^k + r_{s_3 s_4}^k + r_{s_4 s_2}^k$. As $s_1 s_3 \notin \delta(S)$ and $s_4 s_2 \notin \delta(S)$, by (78) we obtain that $r_{s_1 s_2}^k = r_{s_3 s_4}^k$. As Steiner nodes $s_1, s_2, s_3$ and $s_4$ are arbitrarily chosen in $S_k$, we have

$$\begin{align}
r_{s_1 s_2}^k &= r_{s_3 s_4}^k = \rho && \text{for all } s_1, s_2, s_3, s_4 \in S_k, \nonumber \\
& && s_1 s_2 \in \delta(S) \text{ and } s_3 s_4 \in \delta(S) \tag{79} \\
& && \text{for some } \rho \in \mathbb{R}. \nonumber
\end{align}$$

Next, we will establish the coefficients between terminals.

Consider a salesman $l \in K$ and let $w_i$ and $w_{i+1}$ be two terminals of $T_l$. Let $s$ be a Steiner node of $S_l$ and consider the solution $(U^8, I^8)$ given by $U_l^8 = (U_l^0 \setminus \{w_i w_{i+1}\}) \cup$
$\{w_i s, sw_{i+1}\}, U_p^8 = U_p^0$, for each $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^8 = \bigcup_{p \in K} U_p^8$. It is clear that when $l \neq k$, the incidence vector of solution $(U^8, I^8)$ is in $F_{j,S}^k$. Note here that when $l = k$, one can also easily check that $(x^{U^8}, y^{I^8})$ is in $F_{j,S}^k$ for all choice of the Steiner node $s$ (either $s \in S$ or $s \in S_k \setminus S$) and for every choice of terminals $w_i$ and $w_{i+1}$ (in particular $w_i w_{i+1}$ can be equal to $w_j w_{j+1}$ or $w_{j-1} w_j$). As $(x^{U^8}, y^{I^8})$ is in $F_{j,S}^k$ and hence in $F$, it follows that $rx^{U^0} = rx^{U^8} = rx^{U^0} - r_{w_i w_{i+1}}^l + r_{w_i s}^l + r_{sw_{i+1}}^l$, implying that $r_{w_j w_{i+1}}^l = r_{w_i s}^l + r_{sw_{i+1}}^l$. Salesman $l$ and nodes $s, w_i$ and $w_{i+1}$ are all arbitrary. Therefore

$$r_{w_i w_{i+1}}^l = r_{w_i s}^l + r_{sw_{i+1}}^l \quad \text{for all } w_i, w_{i+1} \in T_l, s \in S_l, l \in K. \quad (80)$$

In what follows, we will look at the coefficients of edges between terminals and Steiner nodes.

Consider a salesman $l \in K \setminus \{k\}$ and let $(U^9, I^9)$ be the pair obtained from $(U^8, I^8)$ as follows, $U_l^9 = (U_l^8 \setminus \{sw_{i+1}\}) \cup \{ss', s'w_{i+1}\}, U_p^9 = U_p^8$ for all $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^9 = \bigcup_{j \in K} U_j^9$, where $s$ and $s'$ are Steiner nodes of $S_l$. Since $(x^{U^8}, y^{I^8})$ and $(x^{U^9}, y^{I^9})$ are both in $F_{j,S}^k$ and thus in $F$, this implies that $rx^{U^8} = rx^{U^9} = rx^{U^8} - r_{sw_{i+1}}^l + r_{ss'}^l + r_{s'w_{i+1}}^l$. By (77), it follows that $r_{sw_{i+1}}^l = r_{s'w_{i+1}}^l$. As salesman $l$, and nodes $w_i$, $s$ and $s'$ are arbitrary, we have

$$r_{sw_i}^l = r_{s'w_i}^l = \lambda_1^l(w_i) \quad \begin{array}{l} \text{for all } w_i \in T_l, s, s' \in S_l, l \in K \setminus \{k\}, \\ \text{for some } \lambda_1^l(w_i) \in \mathbb{R}. \end{array} \quad (81)$$

Consider two Steiner nodes $s$ and $s'$ of $S_k$ such that $ss' \notin \delta(S)$. Let $(U^{10}, I^{10})$ be the solution such that $U_k^{10} = (U_k^0 \setminus \{w_i w_{i+1}\}) \cup \{w_i s, sw_{i+1}\}, U_p^{10} = U_p^0$, for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^{10} = \bigcup_{p \in K} U_p^9$. We also define $(U^{11}, I^{11})$ by $U_k^{11} = (U_k^{10} \setminus \{w_i s\}) \cup \{w_i s', ss'\}, U_p^{11} = U_p^0$, for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^{11} = \bigcup_{p \in K} U_p^{11}$. Note that $(x^{U^{10}}, y^{I^{10}})$ and $(x^{U^{11}}, y^{I^{11}})$ are both in $F_{j,S}^k$ and thus in $F$. As a consequence, we have $rx^{U^{10}} = rx^{U^{10}} - r_{w_i s}^k + r_{w_i s'}^k + r_{ss'}^k$. As by (78), $r_{ss'}^k = 0$, we have $r_{w_i s}^k = r_{w_i s'}^k$. And since $w_i$, $s$ and $s'$ are arbitrary, we can write

$$r_{w_i s}^k = r_{w_i s'}^k = \lambda_1^k(w_i) \quad \begin{array}{l} \text{for all } w_i \in T_k, s, s' \in S_k, ss' \notin \delta(S), \\ \text{for some } \lambda_1^k(w_i) \in \mathbb{R}. \end{array} \quad (82)$$

If $ss' \in \delta(S)$, we can similarly show that $r_{w_i s}^k = r_{w_i s'}^k + r_{ss'}^k$. Since $w_i$, $s$ and $s'$ are arbitrary, we have

$$r_{sf_i}^k = r_{s'f_i}^k + r_{ss'}^k = \lambda_1^l(w_i) + \rho \quad \begin{array}{l} \text{for all } w_i \in T_k, s, s' \in S_k, ss' \notin \delta(S), \\ \text{for some } \lambda_1^l(w_i) \in \mathbb{R}, \rho \in \mathbb{R}. \end{array} \quad (83)$$
Now, let $\rho \in \mathbb{R}$ be as given by (79) and $\lambda^l = (\lambda_1^l, \lambda_2^l)$, $l \in K$ such that
$\lambda_1^l = (\lambda_1^l(w_i), w_i \in T_k)$ where $\lambda_1^l(w_i)$ is as given by (81), (82) and (83). $\lambda_2^l = (\lambda_2^l(uv), u, v \in T_k, uv \notin U_l^0)$ such that $\lambda_2^l(uv) = r_{uv}^l - \lambda_1^l(u) - \lambda_1^l(v)$, $l \in K$.

Overall, the coefficients $r_{uv}^l$ for all $uv \in E$ and $l \in K$ can then be expressed in terms of $\rho$, $\lambda_1^l$ and $\lambda_2^l$ as follows

$$r_{uv}^l = \begin{cases} \lambda_1^l(u) + \lambda_1^l(v) & \text{if } l \neq k, uv = w_i w_{i+1}, w_i, w_{i+1} \in T_l, \\ \lambda_1^l(u) & \text{if } l \neq k, u \in T_l, v \in S_l, \\ \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \notin \delta(S) \\ \rho + \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \in \delta(S) \\ \lambda_2^l(uv) + \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = w_i w_j, w_i, w_j \in T_l, j > i, \\ 0 & \text{if } l \neq k \text{ and } uv = s_i s_j, s_i, s_j \in T_l, j \neq i, \\ 0 & \text{if } l = k \text{ and } uv = s_i s_j, s_i, s_j \in S_k, uv \notin \delta(S), \\ \rho & \text{if } l = k \text{ and } uv = s_i s_j, s_i, s_j \in S_k, uv \in \delta(S). \end{cases}$$

It is clear that $r^l = \rho a^l + \lambda_1^l M_1^l + \lambda_2^l M_2^l$, for all $l \in K$. We then deduce that $r = \rho a + \lambda M$ and the result follows.

### B.3 Proof of Claim 4.3

If edge $f$ is considered in some solution, there are two possible configurations.

- The first corresponds to the case where $f$ is not used to route some section of salesman $k$. Consider solution $(U^1, I^1)$ defined as follows: $U_k^1 = U^0 \cap f$ and $U_j^1 = U_j^0, j = 1, \dots, |K|, j \neq k$, and $I^1 = \cup_{j \in K} U_j^1$. In this case, it is not hard to see that $x^{U^1,k}(\delta(V_i)) \ge 3$ and $x^{U^1,k}(\delta(V_j)) \ge 3$ and hence $x^{U^1,k}(\delta(V_i)) + x^{U^1,k}(\delta(V_j)) \ge 6$.

- The second configuration is when edge $f$ is used to route some section of salesman $k$. Suppose, without loss of generality, that this section is $(t_i, t_{i+1})$, where $t_i \in V_i$ and $t_{i+1} \notin (V_i \cap V_j)$. Consider solution $(U^2, I^2)$ defined as follows: $U_k^2 = U^0 \setminus t_i t_i + 1 \cap \{t_i s, ss', s't_{i+1}\}$ and $U_j^2 = U_j^0, j = 1, \dots, K, j \neq k$, and $I^2 = \cup_{j \in K} U_j^1$. Clearly, the following hold for solution $(U^2, I^2)$: $x^{U^2,k}(\delta(V_i)) \ge 2$ and $x^{U^2,k}(\delta(V_j)) \ge 4$. And this implies that $x^{U^2,k}(\delta(V_i)) + x^{U^1,k}(\delta(V_j)) \ge 6$.

### B.4 Proof of Theorem 9

Denote inequality (27) by $ax + by \le \alpha$. Let $rx + qy \le \beta$ be a valid inequality defining a facet $F$ of MSTSPOC$(G, K, T)$ such that $F_{\Pi,F}^k \subseteq F$, where $F_{\Pi,F}^k$ is the face induced by inequality (27). In what follows, we prove that there exist $\rho \in \mathbb{R}$ and $\lambda = (\lambda^l, l \in K)$, $\lambda^l \in \mathbb{R}^{|T_l|+|P_l|}$ for $l \in K$, such that $q = \rho b$ and $r = \rho a + \lambda M$. Notice here that $a = (a^1, a^2, \dots, a^{|K|})$ such that $a^i \in \mathbb{R}^m, i = 1, \dots, |K|$ with $a^i = 0$ for $i \in \{1, \dots, |K|\} \setminus \{k\}, a_e^k \neq 0$ for every $e \in \delta(\Pi) \setminus F$ and $a_{e'}^k = 0$ for every $e' \in E \setminus \delta(\Pi) \setminus F$. Note also that $b = 0$.
<figure><img src="image_16.png" /><figcaption>**Fig. 12** An odd wheel configuration</figcaption></figure>

Throughout the proof, we will suppose for convenience that the edges of $F$ are linking Steiner nodes of $V_0$ to terminals of $V_i$, $i = 1, \dots, p$. Moreover, we will restrict ourselves to the case where $p$ is odd, the case where $p$ is even can be done along the same line. Remark that, under this hypothesis, we have an odd-wheel configuration as shown in Fig. 12.

In the sequel, we will suppose that the terminals of $V_1, V_2, \dots, V_p$ are consecutive. We will refer to the terminals of these sets by $t_1, t_2, \dots, t_p$. In addition, we will denote the edges of $F$ by $f_1, f_2, \dots, f_p$, where $f_i = t_i s_i$, $i = 1, \dots, p$.

First, we prove that $q = 0$.

Consider the solution $(U^0, I^0)$ and let $e_1, e_2, \dots, e_p$ be the edges between consecutive terminals ($e_i = t_i t_{i+1}$, with $t_{p+1} = t_1$). Note that $U^0 = \{e_1, \dots, e_p\}$.

Let $(U^1, I^1)$ be the solution given by

$U_k^1 = \{e_1, e_2, f_3, s_3 s_4, f_4, e_4, f_5, \dots, e_{p-1}, f_p, s_{p-1} s_p, f_1\}$ and $U_j^1 = U_j^0$, $j = 1, \dots, K$, $j \neq k$, and $I^1 = \cup_{j \in K} U_j^1$ (note here that one can have $s_3 = s_4$ and/or $s_{p-1} = s_p$). Consider an edge $g \in E \setminus I^1$ and let $(U^2, I^2)$ be the solution given by $U^2 = U^1$ and $I^2 = I^1 \cup \{g\}$. It is not hard to see that the incidence vectors of solutions $(U^1, I^1)$ and $(U^2, I^2)$ are in $F_{\Pi,F}^k$. This means that $(x^{U^1}, y^{I^1})$ and $(x^{U^2}, y^{I^2})$ satisfy equation $rx+qy = \beta$. Consequently, $rx^{U^1}+qy^{I^1} = rx^{U^2}+qy^{I^2} = qx^{U^1}+qy^{I^1}+q_e$, implying that $q_e = 0$. Since $e$ is arbitrarily chosen in $E \setminus I^1$, we then have that

$$q_e = 0 \quad \text{for all } e \in E \setminus I^1. \qquad (84)$$

Now consider an edge $g_1$ of $I^1$ and a salesman $l \in K$.

Here we distinguish two cases.

First, suppose that $l \neq k$. Hence $g_1 \in U_l^0$. Let $g_1 = t_i t_{i+1}$ and $(U^3, I^3)$ the solution given by $U_j^3 = (U_l^1 \setminus \{g_1\}) \cup \{t_i s, s t_{i+1}\}$, where $s \in S_l$ is a Steiner node of salesman $l$. In addition, let $U_j^3 = U_j^1$, $j = 1, \dots, K$, $j \neq l$, and $I^3 = \cup_{j \in K} U_j^3$. Let $(U^4, I^4)$ given by $U^4 = U^3$ and $I^4 = I^3 \cup \{g_1\}$. The incidence vectors of both solutions

<figure><img src="image_17.png" /></figure>
$(U^3, I^3)$ and $(U^4, I^4)$ are in $F_{\Pi,F}^k$, and hence $rx + qy = \beta$. As a consequence, we have $rx^{U^3} + qy^{I^3} = rx^{U^4} + qy^{I^4} = rx^{U^3} + qy^{I^3} + q_{g_1}$, which implies that $q_{g_1} = 0$.

Suppose now that $l = k$. Here also, we distinguish two cases. The first one is when $g_1 \in I^1 \cap I^0$. This is similar to the previous one. The second one is when $g_1 \in I^1 \setminus I^0$, that $g_1 \in I^1 \cap F$. Suppose, without loss of generality, that $g_1 = f_1$. Let $(U^5, I^5)$ be the solution such that $U_l^5 = (U_l^1 \setminus \{f_1, e_2\}) \cup \{s_p t_1, f_2, s_1 s_2\}$. Also, let $U_j^5 = U_j^1$, $j = 1, \dots, K$, $j \neq l$, and $I^5 = \cup_{j \in K} U_j^5$. Let $(U^6, I^6)$ given by $U^6 = U^5$ and $I^6 = I^5 \cup \{f_1\}$. It is clear that $(x^{U^5}, y^{I^5})$ and $(x^{U^6}, y^{I^6})$ are in $F_{\Pi,F}^k$ and hence in $F$. Thus, we have $rx^{U^5} + qy^{I^5} = rx^{U^6} + qy^{I^6} = rx^{U^5} + qy^{I^5} + q_{f_1}$, which implies that $q_{f_1} = 0$.

As $g_1$ is arbitrary in $I^1$, this implies that

$$q_e = 0 \quad \text{for all } e \in I^1. \qquad (85)$$

By (84) and (85) we then have

$$q_e = 0 \quad \text{for all } e \in E. \qquad (86)$$

In what follows, we will examine components of vector $r$.

First, we will establish the coefficients of edges between Steiner nodes.

Consider a salesman $l \in K \setminus \{k\}$ and let $s$ and $s'$ be two Steiner nodes of $S_l$. Consider the solution $(U^1, I^1)$ defined above and let $(U^7, I^7)$ be the solution defined by $U_l^7 = U_l^1 \cup \{ss'\}$, $U_p^7 = U_p^1$ for all $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^7 = \cup_{p \in K} U_p^7$. Clearly $(x^{U^1}, y^{I^1})$ and $(x^{U^7}, y^{I^7})$ are both in $F_{\Pi,F}^k$ and thus in $F$. This implies that $(x^{U^1}, y^{I^1})$ and $(x^{U^7}, y^{I^7})$ satisfy equation $rx + qy = \beta$. Since $q = 0$, we have $rx^{U^1} = rx^{U^7} = rx^{U^1} + r_{ss'}^l$, which implies $r_{ss'}^l = 0$. As salesman $l$ and Steiner nodes $s$ and $s'$ are arbitrary, we have

$$r_{ss'}^l = 0 \quad \text{for all } s, s' \in S_l, l \in K \setminus \{k\}. \qquad (87)$$

Now consider salesman $k$ and suppose that $s$ and $s'$ are Steiner nodes of $S_k$. Here, we shall distinguish different cases. First, suppose that $ss' \in V_j$ for a given $j \in \{1, \dots, p\}$. Along the same line, we can prove that $r_{ss'}^k = 0$.

Similarly, we can also prove that $r_{ss'}^k = 0$ for every $s$ and $s'$ of $S_k \cap V_0$ such that $|\delta(s) \cap F| + |\delta(s') \cap F| \le 1$.

Now suppose that $s$ and $s'$ are in $S_k \cap V_0$ but $\delta(s) \cap F \neq \emptyset$ and $\delta(s') \cap F \neq \emptyset$. Suppose, without loss of generality, that $s = s_p$ and $s' = s_1$. Consider again solution $(U^1, I^1)$ and define solution $(U^8, I^8)$ as follows, $U_k^8 = U_k^1 \cup \{s_p s_1, s_p s_2, s_2 s_1\}$, $U_p^8 = U_p^1$ for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^8 = \cup_{p \in K} U_p^8$. It is clear that $(x^{U^1}, y^{I^1})$ and $(x^{U^8}, y^{I^8})$ are both in $F_{\Pi,F}^k$ and thus in $F$. This implies that $rx^{U^1} = rx^{U^8} = rx^{U^1} - r_{s_p s_1}^k + r_{s_p s_2}^k + r_{s_2 s_1}^k$, and hence $r_{s_p s_1}^k = r_{s_p s_2}^k + r_{s_2 s_1}^k$. By symmetry, we have
$$
\begin{align*}
r_{s_1 s_2}^k &= r_{s_2 s_3}^k + r_{s_3 s_1}^k, \\
r_{s_2 s_3}^k &= r_{s_3 s_4}^k + r_{s_4 s_2}^k, \\
&\vdots \\
r_{s_p s_1}^k &= r_{s_p s_2}^k + r_{s_2 s_1}^k,
\end{align*}
$$

yielding to $r_{ss'}^k = 0$ for all Steiner nodes $s$ and $s'$ in $S_k \cap V_0$ whose incident edges intersect $F$.

Overall, we have

$$
r_{ss'}^k = 0 \quad \text{for all } s, s' \in S_k, ss' \notin \delta(\Pi). \tag{88}
$$

Now, suppose that $s$ and $s'$ are two Steiner nodes such that $s \in V_j$ and $s' \in V_{j+1}$ for some $j \in \{1, \dots, p\}$. Suppose also that there is a Steiner node $s'' \in V_{j+1}$. Notice that $ss'$ and $ss''$ are both in $\delta(\Pi) \setminus F$.

Suppose, without loss of generality, that $j=1$ (the result can be found by symmetry for all the sets $V_i$). Consider solution $(U^1, I^1)$ given above and define solution $(U^9, I^9)$ as follows, $U_k^9 = U_k^1 \setminus \{e_1\} \cup \{t_1s, ss', s't_2\}$, $U_p^9 = U_p^0$ for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^9 = \cup_{p \in K} U_p^9$. Let $(U^{10}, I^{10})$ be the solution defined by $U_k^{10} = U_k^9 \setminus \{ss'\} \cup \{ss'', s's'\}$, $U_p^{10} = U_p^9$ for all $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^{10} = \cup_{p \in K} U_p^{10}$. Clearly, $(x^U, y^I)$ and $(x^{U^{10}}, y^{I^{10}})$ are both in $F_{\Pi,F}^k$ and then satisfy equation $rx + qy = \beta$. Since $q=0$, we have $rx^U = rx^{U^{10}} = r^k x^9 - r_{ss'}^k + r_{ss''}^k + r_{s's'}^k$. By (88), we have $r_{s''s'}^k = 0$, which implies that $r_{ss'}^k = r_{ss''}^k$. As Steiner nodes $s, s'$ and $s''$ are arbitrary of $S_k$, we have

$$
\begin{equation}
\begin{aligned}
r_{ss'}^k = r_{ss''}^k = \rho & \quad \text{for all } s, s', s'' \in S_k, ss', ss'' \in \delta(\Pi) \setminus F, \\
& \quad \text{for some } \rho \in \mathbb{R}.
\end{aligned}
\tag{89}
\end{equation}
$$

Now, we will determine the coefficients of edges between terminals.

Consider a salesman $l \in K \setminus \{k\}$ and let $t_i$ and $t_{i+1}$ be two terminals of $T_l$. Let $s$ be a Steiner node of $S_l$ and consider the solution $(U^{11}, I^{11})$ given by $U_l^{11} = (U_l^1 \setminus \{t_i t_{i+1}\}) \cup \{t_i s, s t_{i+1}\}$, $U_p^{11} = U_p^1$, for each $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^{11} = \cup_{p \in K} U_p^{11}$. Clearly, the incidence vector of solution $(U^{11}, I^{11})$ is in $F_{\Pi,F}^k$ and hence in $F$. It follows that $rx^{U^1} = rx^{U^{11}} = rx^1 - r_{t_i t_{i+1}}^l + r_{t_i s}^l + r_{s t_{i+1}}^l$, implying that $r_{t_i t_{i+1}}^l = r_{t_i s}^l + r_{s t_{i+1}}^l$. salesman $l$ and nodes $s, t_i$ and $t_{i+1}$ are all arbitrary. Therefore

$$
r_{t_i t_{i+1}}^{l} = r_{t_i s}^{l} + r_{s t_{i+1}}^{l} \quad \text{for all } t_i, t_{i+1} \in T_l, s \in S_l, l \in K \setminus \{k\}. \quad (90)
$$

Now consider salesman $k$ and suppose that $t_i$ and $t_{i+1}$ are terminals of $T_k$, such that $t_i$ and $t_{i+1}$ are in $V_i$ and $V_{i+1}$, respectively. Suppose, without loss of generality, that $t_i = t_1$ and $t_{i+1} = t_2$. Consider solution $(U^1, I^1)$ and let $(U^{12}, I^{12})$ be the solution defined as follows, $U_k^{12} = (U_k^1 \setminus \{t_1 t_2\}) \cup \{t_1 s_2, s_2 t_2\}$, $U_p^{12} = U_p^1$, for each $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^{12} = \cup_{p \in K} U_p^{12}$. $(x^U, y^I)$ and $(x^{U^{12}}, y^{I^{12}})$ are both in $F_{\Pi,F}^k$ and hence in $F$. Therefore, they satisfy equation $rx + qy = \beta$. This implies that
$rx^{U1} = rx^{U12} = rx^{U1} - r_{ti_{t_i+1}}^k + r_{ti_{s2}}^k + r_{s2_{t_i+1}}^k$. Hence $r_{ti_{t_i+1}}^k = +r_{ti_{s2}}^k + r_{s2_{t_i+1}}^k$. As a consequence, we have

$$r_{ti_{t_i+1}}^k = r_{ti_s}^k + r_{st_{t_i+1}}^k \quad \begin{array}{l} \text{for all } t_i, t_{i+1} \in T_k, s \in S_k, \\ t_i, t_{i+1}, t_i s \in \delta(\Pi), \text{ and } st_{i+1} \in F. \end{array} \qquad (91)$$

In what follows, we will examine at the coefficients of edges between terminals and Steiner nodes.

Consider a salesman $l \in K \setminus \{k\}$ and two Steiner nodes $s$ and $s'$ of $S_l$. Let $(U^{13}, I^{13})$ be the solution obtained from $(U^7, I^7)$ as follows, $U_l^{13} = (U_l^7 \setminus \{st_{i+1}\}) \cup \{ss', s't_{i+1}\}$, $U_p^{13} = U_p^7$ for each $p \in \{1, \dots, |K|\} \setminus \{l\}$ and $I^{13} = \cup_{j \in K} U_j^{13}$. Since $(x^{U^7}, y^{I^7})$ and $(x^{U^{13}}, y^{I^{13}})$ are both in $F_{\Pi,F}^k$ and thus in $F$, this implies $rx^{U^7} = rx^{U^{13}} = rx^{U^7} - r_{st_{i+1}}^l + r_{ss'}^l + r_{s't_{i+1}}^l$. By (87), it follows that $r_{st_{i+1}}^l = r_{s't_{i+1}}^l$. As salesman $l$, and nodes $t_i$, $s$ and $s'$ are arbitrary, we have

$$r_{st_i}^l = r_{s't_i}^l = \lambda_1^l(t_i) \quad \begin{array}{l} \text{for all } t_i \in T_l, s, s' \in S_l, l \in K \setminus \{k\}, \\ \text{for some } \lambda_1^l(t_i) \in \mathbb{R}. \end{array} \qquad (92)$$

Now, consider salesman $k$. Consider a terminal $t_i$ of $T_k$ and Steiner nodes $s$ and $s'$ of $S_k$ such that $t_i$, $s$ and $s'$ belong to the same set, say $V_i$.

Along the same line, we can prove that

$$r_{st_i}^k = r_{s't_i}^k = \lambda_1^k(t_i) \quad \begin{array}{l} \text{for all } t_i \in T_k, s, s' \in S_k, \\ \text{$st_i, s't_i \notin \delta(\Pi)$,} \\ \text{for some } \lambda_1^k(t_i) \in \mathbb{R}. \end{array} \qquad (93)$$

Now, suppose that $t_i$, $s$ and $s'$ are such that $t_i s \notin \delta(\Pi)$ and $t_i s' \in \delta(\Pi) \setminus F$. Without loss of generality, we will suppose that $t_i = t_1$ and $s' = s_2$. Consider solution $(U^{14}, I^{14})$ defined as follows. $U_k^{14} = (U_k^1 \setminus \{t_1 t_2\}) \cup \{t_1 s_2, s_2 t_2\}$, $U_p^{14} = U_p^1$, for each $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^{14} = \cup_{p \in K} U_p^{14}$. Define also solution $(U^{15}, I^{15})$ given by $U_k^{15} = (U_k^{14} \setminus \{t_1 s_2\}) \cup \{t_1 s, ss_2\}$, $U_p^{15} = U_p^{14}$, for each $p \in \{1, \dots, |K|\} \setminus \{k\}$ and $I^{15} = \cup_{p \in K} U_p^{15}$. Since $(x^{U^{14}}, y^{I^{14}})$ and $(x^{U^{15}}, y^{I^{15}})$ are both in $F_{\Pi,F}^k$ and thus in $F$, this implies $rx^{U^{14}} = rx^{U^{15}} = rx^{U^{14}} - r_{t_1 s_2}^k + r_{t_1 s}^k + r_{ss_2}^k$. As $t_i$, $s$ and $s'$ are all arbitrary, we have

$$r_{st_i}^k = r_{s't_i}^k + r_{ss'}^k = \lambda_1^k(t_i) + \rho \quad \begin{array}{l} \text{for all } t_i \in T_k, s, s' \in S_k, \\ \text{$t_i s' \notin \delta(\Pi)$, and $t_i s, ss' \in \delta(\Pi) \setminus F$,} \\ \text{for some } \lambda_1^k(t_i) \in \mathbb{R}, \rho \in \mathbb{R}. \end{array} \qquad (94)$$

Now, let $\rho \in \mathbb{R}$ be as given by (89) and $\lambda^l = (\lambda_1^l, \lambda_2^l)$, $l \in K$ such that $\lambda_1^l = (\lambda_1^l(t_i), t_i \in T_k)$ where $\lambda_1^l(t_i)$ is as given by (92), (93) and (94). $\lambda_2^l = (\lambda_2^l(uv), u, v \in T_k, uv \notin U_l^0)$ such that $\lambda_2^l(uv) = r_{uv}^l - \lambda_1^l(u) - \lambda_1^l(v)$, $l \in K$.
Overall, the coefficients $r_{uv}^l$ for all $uv \in E$ and $l \in K$ can then be expressed in terms of $\rho$, $\lambda_1^l$ and $\lambda_2^l$ as follows

$$r_{uv}^l = \begin{cases} \lambda_1^l(u) + \lambda_1^l(v) & \text{if } l \in K, uv = t_i t_{i+1}, t_i, t_{i+1} \in T_i, \\ \lambda_1^l(u) & \text{if } l \neq k, u \in T_i, v \in S_i, \\ \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \notin \delta(\Pi), \\ \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \in F, \\ \rho + \lambda_1^k(u) & \text{if } l = k, u \in T_k, v \in S_k, uv \in \delta(\Pi) \setminus F, \\ \lambda_2^l(uv) + \lambda_1^l(u) + \lambda_1^l(v) & \text{if } uv = t_i t_j, t_i, t_j \in T_i, j > i, \\ 0 & \text{if } l \neq k \text{ and } uv = s_i s_j, s_i, s_j \in T_i, j \neq i, \\ 0 & \text{if } l = k \text{ and } uv = s_i s_j, s_i, s_j \in S_k, uv \notin \delta(\Pi), \\ \rho & \text{if } l = k \text{ and } uv = s_i s_j, s_i, s_j \in S_k, uv \in \delta(\Pi) \setminus F. \end{cases}$$

It is clear that $r^l = \rho a^l + \lambda_1^l M_1^l + \lambda_2^l M_2^l$, for all $l \in K$. We then have that $r = \rho a + \lambda M$ and the result follows.

## C Appendix: Further valid Inequalities

**Proposition 8** Consider a salesman $k \in K$ and let $\Pi = (V_1, ..., V_p)$ be a partition of $V$ such that $|V_i \cap T_k| \ge 1, i = 1, ..., p$ ($p \ge 2$). Suppose that $V_1, ..., V_r, r \le p$ contain respectively $q_i \ge 2, i = 1, ..., r$ non-succcessive terminals (or sequences of terminals). Let $S \subseteq S_k$ be a subset of Steiner nodes of salesman $k$. Inequalities (29) are redundant with respect to inequalities (24), (3) and (5).

*Proof* Denote by $V_{i,j}, i = 1, ..., p$ and $j = 1, ..., q_i$, the $j^{th}$ component of the set $V_i$ consisting of only one terminal or a sequence of successive terminals. Clearly, the following inequalities are valid for MSTSPOC($G$, $K$, $T$)

$$\begin{align*} x^k(\delta(V_{i,j})) &\ge 2 & \text{for all } i=1, ..., p, j=1, ..., q_i \\ -x^k(\delta(s)) &\ge -2 & \text{for all } s \in S, \\ x^k(e) &\ge 0 & \text{for all } e \in E(S_k) \setminus E(S). \end{align*}$$

Remark that there are exactly $p + \sum_{i=1}^r q_i - r$ Steiner cut inequalities and $|S|$ dis-junction inequalities.

By summing these inequalities, together with (10), we obtain

$$2x^k(\delta_{G \setminus S}(V_1, V_2, ..., V_p)) \ge 2((p + \sum_{i=1}^r q_i - r) - |S|),$$

and by dividing by 2, we obtain

$$x^k(\delta_{G \setminus S}(V_1, V_2, ..., V_p)) \ge (p + \sum_{i=1}^r q_i - r) - |S|,$$

which ends the proof.

<figure><img src="image_18.png" /></figure>
**Acknowledgements** The authors would like to thank the anonymous reviewers for their valuable comments.

**Funding** Open access funding provided by Université Paris Dauphine-PSL. This research received no specific grant from any funding agency in the public, commercial, or not-for-profit sectors.

**Data Availability** Not applicable.

## Declarations

**Conflict of interest** The authors declare that they have no Conflict of interest.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## References

Álvarez-Miranda E, Sinnl M (2019) A note on computational aspects of the Steiner travelling salesman problem. Int Trans Oper Res 26(4):1396-1401

Applegate DL, Bixby RE, Chvatal V, Cook WJ (2007) The Traveling Salesman Problem: a computational study. Princeton University Press

Ascheuer N, Jünger M, Reinelt G (2000) A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints. Comput Optim Appl 17:61-84

Baïou M, Barahona F, Mahjoub AR (2000) Separation of partition inequalities. Math Oper Res 25(2):243-254

Baïou M, Barahona F, Mahjoub AR (2011) Partition inequalities: Separation, extensions and network design. In Progress Combinatorial Optimization (Ed.) Wiley-ISTE pp. 1-39

Balas E, Fischetti M, Pulleyblank WR (1995) The precedence-constrained asymmetric traveling salesman polytope. Math Program 68:241-265

Barahona F, Mahjoub AR (1995) On two-connected subgraph polytopes. Discret Math 147(1-3):19-34

Bektas T (2006) The multiple traveling salesman problem: an overview of formulations and solution procedures. Omega 34(3):209-219

Benavent E, Martínez A (2013) Multi-depot multiple TSP: a polyhedral study and computational results. Ann Oper Res 207(1):7-25

Bendali F, Diarrassouba I, Mahjoub AR, Didi Biha M, Mailfert J (2010) A branch-and-cut algorithm for the k-edge connected subgraph problem. Networks 55(1):13-32

Bernardino R, Gouveia L, Paias A, Santos D (2022) The multi-depot family traveling salesman problem and clustered variants: Mathematical formulations and branch-&-cut based methods. Networks 80(4):502-571

Borne S, Gabrel V, Mahjoub AR, Taktak R (2011) Multilayer survivable optical network design. In: International Network Optimization Conference (INOC), pp. 170-175. Springer

Borne S, Mahjoub AR, Taktak R (2013) A branch-and-cut algorithm for the multiple Steiner TSP with order constraints. Electron Notes Discr Math 41:487-494

Cheikhrouhou O, Khoufi I (2021) A comprehensive survey on the multiple traveling salesman problem: Applications, approaches and taxonomy. Comput Sci Rev 40:100369

Chopra S (1989) On the spanning tree polyhedron. Oper Res Lett 8(1):25-29

Chopra S, Rao MR (1994) The Steiner tree problem I: Formulations, compositions and extension of facets. Math Program 64(1-3):209-229

Chopra S, Rao MR (1994) The Steiner tree problem II: properties and classes of facet. Math Program 64(1-3):231-246
Chvátal V (1973) Edmonds polytopes and a hierarchy of combinatorial problems. Discret Math 4(4):305-337

Cornejo-Acosta JA, García-Díaz J, Pérez-Sansalvador JC, Segura C (2023) Compact integer programs for depot-free multiple traveling salesperson problems. Mathematics 11(13):3014

D'Angelo G (2018) The Steiner multi cycle problem with applications to a collaborative truckload problem. In: 17th International Symposium on Experimental Algorithms (SEA 2018), 103:26

Duchenne E, Laporte G, Semet F (2007) The undirected m-peripatetic salesman problem: polyhedral results and new algorithms. Oper Res 55(5):949-965

Duchenne E, Laporte G, Semet F (2012) The undirected m-capacitated peripatetic salesman problem. Eur J Oper Res 223(3):637-643

Edmonds J (1965) Maximum matching and a polyhedron with 0,1-vertices. J Res Nat Bur Std (B) 69:125-130

Gabrel V, Mahjoub AR, Taktak R, Uchoa E (2020) The multiple Steiner TSP with order constraints: complexity and optimization algorithms. Soft Comput 24(23):17957-17968

Gouveia L, Pesneau P (2006) On extended formulations for the precedence constrained asymmetric traveling salesman problem. Networks 48(2):77-89

Gouveia L, Pesneau P, Ruthmair M, Santos D (2018) Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem. Networks 71(4):451-465

Grötschel M (1980) On the symmetric travelling salesman problem: solution of a 120-city problem. Math Program Study 12:61-77

Grötschel M, Monma CL (1990) Integer polyhedra arising from certain network design problems with connectivity constraints. SIAM J Discret Math 3(4):502-523

Grötschel M, Padberg MW (1979) On the symmetric travelling salesman problem I: inequalities. Math Program 16(1):265-280

Huygens D, Mahjoub AR, Pesneau P (2004) Two edge-disjoint hop-constrained paths and polyhedra. SIAM J Discret Math 18(2):287-312

Interian R, Ribeiro CC (2017) A grasp heuristic using path-relinking and restarts for the Steiner traveling salesman problem. Int Trans Oper Res 24(6):1307-1323

Khachai D, Sadykov R, Battaia O, Khachay M (2023) Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm. Eur J Oper Res 309(2):488-505

Letchford AN, Nasiri SD, Theis DO (2013) Compact formulations of the Steiner traveling salesman problem and related problems. Eur J Oper Res 228(1):83-92

Lintzmayer CN, Miyazawa FK, Moura PF, Xavier EC (2020) Randomized approximation scheme for Steiner multi cycle in the Euclidean plane. Theoret Comput Sci 835:134-155

Liu H, Zhang H, Xu Y (2021) The m-Steiner traveling salesman problem with online edge blockages. J Comb Optim 41:844-860

Mahjoub AR (1994) Two edge connected spanning subgraphs and polyhedra. Math Program 64(1-3):199-208

Mahjoub AR, Pesneau P (2008) On the Steiner 2-edge connected subgraph polytope. RAIRO - Oper Res 42(3):259-283

Mahjoub AR, Taktak R, Uchoa E (2019) A layered compact formulation for the multiple Steiner TSP with order constraints. In: 6th International Conference on Control, Decision and Information Technologies (CoDIT), pp. 1462-1467. IEEE

Nash-Williams CSJA (1961) Edge-disjoint spanning trees of finite graphs. J Lond Math Soc s1-36(1):445-450

Rodríguez-Pereira J, Fernández E, Laporte G, Benavent E, Martínez-Sykora A (2019) The Steiner travelling salesman problem and its extensions. Eur J Oper Res 278(2):615-628

Sarin SC, Sherali HD, Bhootra A (2005) New tighter polynomial length formulations for the asymmetric traveling salesman problem with and without precedence constraints. Oper Res Lett 33(1):62-70

Sarin SC, Sherali HD, Judd JD, Tsai PFJ (2014) Multiple asymmetric traveling salesmen problem with and without precedence constraints: Performance comparison of alternative formulations. Comput Oper Res 51:64-89

Stoer M (1992) Design of survivable networks. Lectures Notes in Mathematics 1531. Springer-Verlag

Sundar K, Rathinam S (2016) Generalized multiple depot multiple traveling salesmen problem-polyhedral study and exact algorithm. Comput Oper Res 70:39-55
Taktak R (2024) A branch-and-cut algorithm for the multiple Steiner TSP with order constraints. Ann Oper Res 41:487–494

Taktak R, Uchoa E (2020) On the multiple Steiner traveling salesman problem with order constraints. In: Lecture Notes in Computer Science 12176, M. Baïou, B. Gendron, O. Günlük, A.R. Mahjoub (Eds), International Symposium on Combinatorial Optimization (ISCO), pp. 66–77. Springer

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.