Daniil Khachai
email: daniil.khachai@kedgebs.com

Olga Battaia
email: olga.battaia@kedgebs.com

Michael Khachay
email: mkhachay@imm.uran.ru

Ruslan Sadykov
email: ruslan.sadykov@inria.fr

An Exact Approach for the Precedence Constrained Generalized Traveling Salesman Problem

The Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) is an extension of two well-known combinatorial optimization problems -the Generalized Traveling Salesman Problem (GTSP) and the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP), whose path version is known as the Sequential Ordering Problem (SOP). Similarly to the classic GTSP, the goal of the PCGTSP, for a given input digraph and partition of its node set into clusters, is to find a minimum cost cyclic route (tour) visiting each cluster in a single node. In addition, as in the PCATSP, feasible tours are restricted to visit the clusters with respect to the given partial order. Unlike the GTSP and SOP, to the best of our knowledge, the PCGTSP still remain to be weakly studied both in terms of polyhedral theory and algorithms. In this paper, for the first time for the PCGTSP, we propose several families of valid inequalities, establish dimension of the PCGTS polytope and prove sufficient conditions ensuring that the extended Balas' π-and σ-inequalities become facet-inducing. Relying on these theoretical results and evolving the state-of-the-art algorithmic approaches for the PCATSP and SOP, we introduce a family of MILP-models (formulations) and several variants of the branch-and-cut algorithm for the PCGTSP. We prove their high performance in a competitive numerical evaluation against the public benchmark library PCGTSPLIB, a known adaptation of the classic SOPLIB to the problem in question.

Introduction

Introduced in the seminal paper by [START_REF] Srivastava | Generalized Traveling Salesman Problem through n sets of nodes[END_REF], the Generalized Traveling Salesman Problem (GTSP) is one of the most well-known generalizations of the classic Traveling Salesman Problem (TSP). It has numerous industrial applications including air time minimization in metal sheet cutting [START_REF] Dewil | A review of cutting path algorithms for laser cutters[END_REF]; [START_REF] Chentsov | Model of megalopolises in the tool path optimisation for CNC plate cutting machines[END_REF]; [START_REF] Makarovskikh | Mathematical models and routing algorithms for economical cutting tool paths[END_REF]) and coordinate measuring machinery [START_REF] Salman | An industrially validated CMM inspection process with sequence constraints[END_REF]).

An instance of the GTSP can be defined informally as follows. A salesperson travels across a given transportation network consisting of cities and roads connecting them, represented by the nodes and arcs of some directed graph, respectively. The set of cities is partitioned into subsets called clusters. By traveling on any road, the salesperson is charged with a corresponding transportation cost. The goal is to construct a closed tour that visits each cluster in one city exactly and minimizes the accumulated transportation costs.

Being an extension of the classic Traveling Salesman Problem (TSP), the GTSP is strongly NP-hard even on the Euclidean plane [START_REF] Papadimitriou | Euclidean TSP is NP-complete[END_REF]) any time when number of clusters m is a part of the input. On the other hand, an adaptation to this problem of the well-known Held and Karp dynamic programming scheme [START_REF] Held | A dynamic programming approach to sequencing problems[END_REF]) has running-time bound O(n 3 m 2 • 2 m ), i.e. the GTSP belongs to the class of Fixed-Parameter Tractable (FPT) problems, being parameterized by the number of clusters. Furthermore, it can be solved to optimality in polynomial time, provided that m = O(log n). In the case of PCGTSP, the running time is O(n 3 m 2 • |J |), where J is a set of ideals of the given partial order (see e.g. [START_REF] Khachay | Problem-specific Branch-and-Bound algorithms for the Precedence Constrained Generalized Traveling Salesman Problem[END_REF]). In particular, if the order specifying the precedence constraints is of fixed width w, then |J | = O(m w ) [START_REF] Steiner | On the complexity of dynamic programming for sequencing problems with precedence constraints[END_REF]). Thus, in this case, the PCGTSP can be solved to optimality in polynomial time.

The algorithmic design for the GTSP has been developed in the literature in several directions. The first approach is based on the reduction of the initial problem to an appropriate instance of the Asymmetric TSP (ATSP) [START_REF] Noon | An efficient transformation of the generalized traveling salesman problem[END_REF]), which at first glance gives an opportunity to employ a vast variety of known algorithms designed for the ATSP (see e.g. [START_REF] Roberti | Models and algorithms for the asymmetric traveling salesman problem: an experimental comparison[END_REF]). However, despite its mathematical elegance, this approach suffers from several technical shortcomings. First, even a close-to-optimal solutions of such auxiliary ATSP instances may correspond to infeasible solutions of the initial GTSP. Furthermore, such instances may have a quite unusual shape and thus difficult to solve for the existing TSP solvers [START_REF] Karapetyan | Efficient local search algorithms for known and new neighborhoods for the generalized traveling salesman problem[END_REF], see also [START_REF] Yuan | A branch-and-cut algorithm for the generalized traveling salesman problem with time windows[END_REF]).

Another approach provides various heuristics and meta-heuristics. Among them are the memetic algorithms [START_REF] Gutin | A memetic algorithm for the generalized traveling salesman problem[END_REF]), an extension of the Lin-Kernighan-Helsgaun heuristic solver [START_REF] Helsgaun | Solving the equality Generalized Traveling Salesman Problem using the Lin-Kernighan-Helsgaun algorithm[END_REF]), and the GLNS meta-heuristic [START_REF] Smith | GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem[END_REF]) based on the Adaptive Large Neighborhood Search (ALNS) framework, which appears to be the most efficient at the moment.

Finally, the third research direction is related to design of approximation algorithms with theoretical performance guarantees (see e.g. [START_REF] Feremans | The geometric generalized minimum spanning tree problem with grid clustering[END_REF]; [START_REF] Yu | Approximation schemes for the generalized traveling salesman problem[END_REF]) and problem-specific branch-and-bound and branch-and-cut algorithms [START_REF] Fischetti | A branch-and-cut algorithm for the symmetric Generalized Traveling Salesman Problem[END_REF]; [START_REF] Yuan | A branch-and-cut algorithm for the generalized traveling salesman problem with time windows[END_REF]).

The Sequential Ordering Problem (SOP), which is extremely close to the PCATSP, was introduced in [START_REF] Escudero | An inexact algorithm for the sequential ordering problem[END_REF]). We should mention three groups of important results obtained for the both problems on which the current research for the PCGTSP is based on.

The first of them, in the field of polyhedral study of the PCATSP, was obtained in the seminal paper [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF], where sufficient conditions for the π-and σ-inequalities to be facet-inducing were proved.

The second group comprises valid inequalities that exploit precedence constraints explicitly and approaches to their strengthening, as well as the design of MILP-models (formulations) in order to obtain better lower bounds while decreasing time complexity of the appropriate LP-relaxations. Among them are compact formulations proposed in [START_REF] Subhash | New tighter polynomial length formulations for the Asymmetric Traveling Salesman Problem with and without precedence constraints[END_REF]) as an extension of results of (Gouveia andPires (1999, 2001); [START_REF] Hanif | On tightening the relaxations of miller-tucker-zemlin formulations for asymmetric traveling salesman problems[END_REF]), and formulations whose exponential-size sets of valid inequalities are supplemented with polynomialtime separation techniques [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric traveling salesman problem[END_REF]). To the best of our knowledge, to the date, the models providing the tightest lower bounds were introduced in [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF]).

The last group of results relies on design and implementation of problem-specific branch-andcut algorithms including ones proposed in [START_REF] Ascheuer | A branch & cut algorithm for the asymmetric traveling salesman problem with precedence constraints[END_REF]), [START_REF] Cire | Multivalued decision diagrams for sequencing problems[END_REF]) and [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF]), where the last one is regarded to be state-of-the-art on the topic.

In this paper, we consider the PCGTSP, which is an extension of the GTSP, where the feasible tours are restricted to visit all the clusters with respect to the partial order. At the same time, PCGTSP extends the PCATSP as follows. Any instance of PCATSP is considered to be the instance of PCGTSP, where all clusters are singletons. Unlike both GTSP and PCATSP, the PCGTSP considered in this paper still remains weakly studied. To the best of our knowledge, all the related published results are exhausted by: (i) efficient algorithms for several specific precedence constraints including partial orders of Balas-type (see e.g. [START_REF] Balas | Linear time dynamic-programming algorithms for new classes of restricted TSPs: A computational study[END_REF]; [START_REF] Chentsov | An exact algorithm with linear complexity for a problem of visiting megalopolises[END_REF]) and the orders that lead to quasi-and pseudo-pyramidal optimal tours [START_REF] Khachay | Complexity and approximability of the Euclidean Generalized Traveling Salesman Problem in grid clusters[END_REF]);

(ii) the PCGLNS heuristic solver proposed in Khachay et al. (2020) that extends the results obtained in [START_REF] Smith | GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem[END_REF]) to the case of PCGTSP;

(iii) branch-and-bound and DP-and-bound algorithms for this problem [START_REF] Khachay | Problem-specific Branch-and-Bound algorithms for the Precedence Constrained Generalized Traveling Salesman Problem[END_REF]), based on Balas instance preprocessing [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF]), Held and Karp branching framework (see e.g. [START_REF] Morin | Branch-and-bound strategies for dynamic programming[END_REF]), and the combinatorial lower bounds from Salman et al. ( 2020), (iv) the public PCGTSPLIB benchmark library proposed in [START_REF] Salman | Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem[END_REF]) as an extension of the well-known SOPLIB library. According to the literature [START_REF] Salman | Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem[END_REF]; [START_REF] Khachay | Problem-specific Branch-and-Bound algorithms for the Precedence Constrained Generalized Traveling Salesman Problem[END_REF]), 12 out of 40 instances of this library were solved to optimality. Meanwhile, their solutions can be found within a competitive time by Gurobi solver supplied with our extension of the L1PCATSPxy compact model, previously introduced in (Sarin et al. ( 2005)) for the PCATSP, built-in cutting planes, and PCGLNS primal heuristic.

In addition, we should mention the branch-and-cut algorithm proposed recently in [START_REF] Yuan | A branch-and-cut algorithm for the generalized traveling salesman problem with time windows[END_REF] for the GTSP with time windows. This result seems to be relevant as the time windows defined on clusters induce natural precedence constraints. Unfortunately, this approach is hardly applicable to the general PCGTSP, since a partial order defined on the set of clusters not necessarily admits encoding in terms of time windows.

In this paper, we try to bridge the gap both in the context of polyhedral theory and in the field of branch-and-cut algorithms for the considered problem. Contribution of this paper is three-fold:

(i) by evolving the inductive framework developed in [START_REF] Fischetti | The symmetric generalized traveling salesman polytope[END_REF] for the symmetric GTSP, we establish dimension of the PCGTS polytope and extend the sufficient facet-inducing conditions for π-and σ-inequalites proved initially in [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF]) for the PCATSP, to the more general case of the PCGTSP;

(ii) relying on the known results on formulations for the PCATSP [START_REF] Subhash | New tighter polynomial length formulations for the Asymmetric Traveling Salesman Problem with and without precedence constraints[END_REF]; [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric traveling salesman problem[END_REF]; [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF]), we propose novel valid inequalities for the PCGTSP and a family of compact and exponential-size MILP-models for this problem aimed to increase tightness of their lower bounds and speed-up the solution procedure for the appropriate LPrelaxations;

(iii) by combining the best formulations (in terms of lower bounds and running times) and the PCGLNS primal heuristic, for the first time, we propose several variants of the branch-and-cut algorithm for the PCGTSP, and compare their performance with aforementioned best known results and our adaptation of the state-of-the-art algorithm proposed in [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF] for the SOP.

As a result, the number of PCGTSPLIB instances solved to optimality has increased almost twice, to 23 out of 40 instances. Furthermore, the carried out numerical evaluation confirm that the considered MILP-models and branch-and-cut algorithm for the PCGTSP benefit well from the incorporation of the predecessor/successor inequalities.

The rest of the paper is organized as follows. In Section 2, we give a mathematical statement of the considered problem, introduce some necessary definitions and notation, discuss the instance preprocessing, and describe the compact MILP-model used throughout the paper. In Section 3, we propose novel families of valid inequalities for the problem in question and explain the corresponding separation procedures. Section 4 deals with the polyhedral study of the PCGTSP. By extending the seminal results of [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF] and [START_REF] Fischetti | The symmetric generalized traveling salesman polytope[END_REF], we establish dimension of the PCGTS polytope and prove the conditions sufficient for π-and σ-inequalities to be facet-inducing. Further, Section 5 represents the proposed formulations for the PCGTSP, while Section 6 gives an overview of our branch-and-cut algorithm. In Section 7 we report the results of the numerical evaluation, both for the proposed formulations and suggested variants of the branch-and-cut algorithm. Finally, Section 8 concludes the paper.

Problem statement

An instance of PCGTSP is given by a triple (G, C, G), where -the complete loopless arc-weighted digraph G = (V, E, c), |V | = n, defines a groundset network supplemented with transportation costs c(u, v) for an arbitrary arc (u, v) ∈ E; -the partition C = {C 1 , . . . , C m } splits the nodeset V of the graph G into m non-empty pairwisedisjoint clusters, where the cluster C 1 is referred to as depot;

-the directed acyclic graph G = (C, A) defines a partial order (precedence constraints) on the set of clusters C. Further, without loss of generality, we assume G to be transitively closed, i.e.

(C i , C j ) ∈ A and (C j , C k ) ∈ A imply (C i , C k ) ∈ A, and that (C 1 , C p ) ∈ A for any p ∈ {2, . . . , m}.
A closed m-tour T is called a feasible solution of the PCGTSP, if -it departs from and arrives at some node v 1 ∈ C 1 ; -it visits each cluster C p ∈ C exactly once; -the tour T is consistent with the partial order G, i.e. no cluster C q can be visited by the tour T before its arbitrary predecessor in the order G.

The cost of a tour

T = (v 1 , v 2 , . . . , v m ) is the sum of costs of its arcs cost(T ) = c(v m , v 1 ) + m-1 i=1 c(v i , v i+1
). The objective of the PCGTSP is to find a feasible m-tour of the minimum cost.

Preliminaries

We start with some necessary definitions and notation. For any pair of clusters C p and C q except the depot cluster C 1 , for which (C p , C q ) ∈ A, we refer to C p as a predecessor of C q (and C q as a successor of C p ) or shortly C p ≺ C q . Further, to any non-depot cluster C, we assign subsets

π(C) = {C i ̸ = C 1 : C i ≺ C} and σ(C) = {C i ̸ = C 1 : C ≺ C i } of
its predecessors and successors, respectively. This notation can be easily extended to an arbitrary nonempty subset of clusters If, for C ̸ = C 1 , π(C) ∪ σ(C) = ∅, we call C a free cluster. In terms of polyhedral results, we restrict ourselves to the setting of PCGTSP with a singleton free cluster, which we call C Balas .

C ′ ⊂ C \ {C 1 }: π(C ′ ) = C∈C ′ π(C), σ(C ′ ) = C∈C ′ σ(C).
In the following, by C(v) we denote (the only) cluster that contains an arbitrary node v ∈ V . We call v a non-individual node, if |C(v)| > 1, otherwise v is called individual. To simplify the problem at hand, we use the instance preprocessing technique proposed in [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF]. We exclude any arc (i, j) ∈ E, for which at least one of the following options holds:

(i ∈ C 1 ) & (j ∈ C -) (1)
(i ∈ C + ) & (j ∈ C 1 ) (2) C(j) ≺ C(i) (3) ∃ C ∈ C : (C(i) ≺ C) & ( C ≺ C(j)) (4)
C(i) = C(j). (5)
For any proper subset ∅ ̸ = S ⊂ V , we use the standard notation δ -(S) = {(i, j) ∈ E : i / ∈ S, j ∈ S}, δ + (S) = {(i, j) ∈ E : i ∈ S, j / ∈ S}, and δ(S) = δ + (S) ∪ δ -(S) for the appropriate incoming and outgoing cuts, and their union, respectively.

In the case of a singleton S = {v}, we use simple notation δ + (v) and δ -(v).

Without loss of generality, we assume that graph G has no isolated nodes after preprocessing. Furthermore, we can assume that, for any node v ∈ V , δ + (v) ̸ = ∅ and δ -(v) ̸ = ∅. As a simple consequence, we obtain that δ + (C) ̸ = ∅ and δ -(C) ̸ = ∅ for any cluster C as well.

Compact MILP model

To obtain a basic compact model for the considered problem, we extend the known L1PCATSPxy formulation, proposed in [START_REF] Subhash | New tighter polynomial length formulations for the Asymmetric Traveling Salesman Problem with and without precedence constraints[END_REF] for the PCATSP, which is the best performer among compact models in terms of LP-relaxation bounds for that problem.

For any (i, j) ∈ E and node v ∈ V , we introduce the following binary decision variables:

x ij =
1, if (i, j) belongs to the solution 0, otherwise,

z v = 1, if v is visited by the solution 0, otherwise.
In addition, we introduce auxiliary variables y pq and u pq :

y pq = 1, if cluster C p precedes C q
in the solution (not necessarily immediately) 0, otherwise, u pq = 1, if cluster C p immediately precedes C q in the solution 0, otherwise.

The proposed MILP model for the PCGTSP is as follows:

min (i,j)∈E c ij x ij , (6) s.t.
i∈C k z i = 1 (k ∈ {1, . . . , m}) (7)
(i,j)∈δ + (i)

x ij = z i (i ∈ V ) ( 8
) (i,j)∈δ -(i) x ji = z i (i ∈ V ) (9) m q=1,q̸ =p u pq = 1 (p ∈ {1, . . . , m}), m p=1,p̸ =q u pq = 1 (q ∈ {1, . . . , m}) (10) i∈δ + (Cp) j∈δ -(Cq)
x ij = u pq (p, q ∈ {1, . . . , m}, p ̸ = q) (11) (y pq + u qp ) + y qr + y rp ⩽ 2 (p, q, r ∈ {2, . . . , m}, p ̸ = q ̸ = r)

u pq -y pq ⩽ 0 (p, q ∈ {2, . . . , m}, p ̸ = q) (13)

y pq + y qp = 1 ({p, q} ⊂ {2, . . . , m}) (14)
y pq = 1 (p, q ∈ {2, . . . , m}, C p ≺ C q ) (15) x ij , z i ∈ {0, 1}, u pq ⩾ 0, y pq ⩾ 0 ( 16
)
The objective is to minimize the total traveling cost (6). Constraints (7) ensure that exactly one node from each cluster is visited. Constraints (8) and ( 9) are flow conservation constraints in terms of nodes, while constraints (10) are flow conservation constraints in terms of clusters. Technical constraints (11) establish the link between the decision and auxiliary variables. Similarly to the initial L1PCATSPxy model, constraints (12)-( 15) ensure subtour elimination and establish the given precedence constraints simultaneously.

By evolving the arguments of [START_REF] Subhash | New tighter polynomial length formulations for the Asymmetric Traveling Salesman Problem with and without precedence constraints[END_REF], it is easy to verify the following observation.

Observation 1. For any feasible solutions [x ′ , z ′ , u ′ , y ′ ] and [x ′′ , z ′′ , u ′′ , y ′′ ] of the model (6)-( 16),

(x ′ = x ′′ ) ∧ (z ′ = z ′′ ) ⇒ (u ′ = u ′′ ) ∧ (y ′ = y ′′ ).

Valid inequalities

In this section, we extend to the case of PCGTSP some known families of valid inequalities initially introduced in papers [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF]; [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF]; [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF] for the PCATSP. It is convenient to specify these inequalities in terms of the following standard notation. For any non-empty disjoint cluster subsets U ′ , U ′′ ⊂ C,

x(U ′ , U ′′ ) = Cp⊂U ′ Cq⊂U ′′ i∈Cp j∈Cq x ij ≡ Cp⊂U ′ Cq⊂U ′′ u pq .

Predecessor and successor inequalities

Proposition 1. For an arbitrary non-empty S ⊂ C \ {C 1 }, S = C \ S, the predecessor-inequality (π-inequality):

x(S \ π(S), S \ π(S)) ⩾ 1 ( 17)

is valid for the PCGTSP.

Proof. Let T be an arbitrary tour that satisfies the precedence constraints and C p be the last cluster in S visited by T . Then, C p ∈ S \ π(S) and for the next cluster visited by T , C q ∈ S \ π(S). Such a cluster exists, since the tour T should depart from and arrive at C 1 . Therefore,

x(S \ π(S), S \ π(S)) ⩾ u pq = 1.
Since the following two propositions can be treated similarly, we skip their proofs for the sake of brevity.

Proposition 2. For an arbitrary non-empty S ⊂ C \ {C 1 }, S = C \ S, the successor-inequality (σ-inequality):

x( S \ σ(S), S \ σ(S)) ⩾ 1 ( 18)

is valid for the PCGTSP.

Proposition 3. Let X , Y ⊂ C \ {C 1 } be non-empty subsets such that, for an arbitrary clusters

C ′ ∈ X and C ′′ ∈ Y, C ′ ≺ C ′′ , and let Q = {C 1 } ∪ π(X ) ∪ σ(Y).
Then for any S ⊂ C, S = C \ S such that X ⊆ S, Y ⊆ S, the (π, σ)-inequality:

x(S \ Q, S \ Q) ⩾ 1 (19)
is valid for the PCGTSP.

Precedence cycle breaking inequalities

For some natural t, consider a subset

C ′ = {C i1 , . . . , C i2t+1 } ⊂ C \ {C 1 }, such that C i1 ≺ . . . ≺ C i2t+1 . Introduce the subsets C ′ odd = {C i2s+1 : s ∈ {0, . . . , t}} and C ′ even = {C i2s : s ∈ {1, . . . , t}} of C ′ , that contain C ij
with odd and even j respectively. Proposition 4. For an arbitrary non-empty

S ⊂ C \ {C 1 }, S = C \ S, such that C ′ odd ⊂ S and C ′ even ⊂ S, x(S, S) ≥ t + 1 (20)
is valid for the PCGTSP.

Proof. Indeed, consider an arbitrary feasible tour T . Since clusters C i1 . . . C i2t+1 are linearly ordered and C 1 ̸ ∈ S, the tour T crosses the border from S to S at least t + 1 times.

Following [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF]), without loss of generality, we can assume that C ij ∈ π(C ij+1 ) for each j ∈ {1, . . . , 2t}. Furthermore, we can strengthen inequality (20) as follows.

Proposition 5. For an arbitrary non-empty S ⊂ C \ {C 1 }, S = C \ S, such that C ′ odd ⊂ S and C ′ even ⊂ S, the condition σ(C i2t+1 ) ̸ ⊂ S implies the validity of inequality

x(S \ S ′ , S \ S ′ ) ≥ t + 1, (21)
where

S ′ = π(C i1 ) ∪ σ(C i2t+1 ) \ σ(C i2t+1 ).

Single-option inequalities

In this subsection, we extend the family of simple (but powerful) inequalities proposed in [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF] for the PCATSP, whose validity can be easily obtained from ( 7)-( 11) and precedence constraints.

Proposition 6. For an arbitrary {C i , C j } ⊂ C \ {C 1 }, the following inequalities

u ij + u ji + u kl + u lk ≤ 1 (C k ∈ π(C i ), C l ∈ σ(C j )) (22)
u ij + u ji + C l ∈σ(Cj ) u kl ≤ 1 (C k ∈ π(C i )) (23)
u ij + u ji + C l ∈σ(Cj ) u lk ≤ 1 (C k ∈ π(C i )) (24)
u ij + u ji + C k ∈π(Ci) u kl ≤ 1 (C l ∈ σ(C j )) (25)
u ij + u ji + C k ∈π(Ci) u lk ≤ 1 (C l ∈ σ(C j )) (26)
are valid for the PCGTSP.

Strengthened precedence variables and network flow based inequalities

The authors of [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF]) introduced a novel exponential-size families of valid inequalities augmented with polynomial-time separation procedures, their strengthened counterparts, and the related formulations for the PCATSP. Comprehensive numerical analysis carried out there showed that more tight lower bounds were provided by the formulations based on strengthened inequalities. Therefore, in this paper, we restrict ourselves only on extension to the PCGTSP of these families.

Proposition 7. For an arbitrary clusters C p and C q not equal to C 1 , where p ̸ = q, the strengthened simple-cut inequality x(S, S) ≥ y pq is valid for the PCGTSP, for any partition

(S, S) of (C \ C 1 pq ) ∪ {C p , C q }, such that C p ∈ S, C q ∈ S, ( 27
) (S, S) of (C \ C 2 pq ) ∪ {C 1 , C p }, such that C 1 ∈ S, C p ∈ S, ( 28
) (S, S) of (C \ C 3 pq ) ∪ {C 1 , C q }, such that C q ∈ S, C 1 ∈ S, (29)
where

C 1 pq = {C 1 } ∪ π(C p ) ∪ σ(C q ), C 2 pq = {C q } ∪ σ(C p ) ∪ σ(C q ) and C 3 pq = {C p } ∪ π(C p ) ∪ π(C q ).
Proposition 8. For an arbitrary triple (C p , C q , C r ) of distinct clusters not equal to C 1 , the strengthened GDDL inequality1

x(S, S) ≥ y pr + y rq (30)

is valid for the PCGTSP for any partition (S, S)

of C \ C pqr ∪ {C 1 , C p , C q , C r }, such that {C 1 , C r } ⊂ S, {C p , C q } ⊂ S and C pqr = σ(C p ) ∩ σ(C q ) ∪ π(C r ) ∩ σ(C p ) ∪ σ(C q ) ∩ σ(C r ) .
Proposition 9. For an arbitrary triple (C p , C q , C r ) of distinct clusters not equal to C 1 , the strengthened Reversed GDDL inequality

x(S, S) ≥ y pr + y rq (31)

is valid for the PCGTSP for any partition (S, S)

of C \ C R pqr ∪ {C 1 , C p , C q , C r }, such that {C p , C q } ⊂ S, {C 1 , C r } ⊂ S and C R pqr = π(C p ) ∩ π(C r ) ∪ π(C p ) ∩ π(C q ) ∪ σ(C r ) ∩ π(C q
) . Proposition 10. For an arbitrary triple (C p , C q , C r ) of distinct clusters not equal to C 1 , the strengthened 2-path inequality x(S, S) ≥ y pq + y qr -1 is valid for the PCGTSP, for any partition

(S, S) of (C \ C 1 pqr ) ∪ {C 1 , C p }, such that C 1 ∈ S, C p ∈ S, ( 32
) (S, S) of (C \ C 2 pqr ) ∪ {C p , C q }, such that C p ∈ S, C q ∈ S, ( 33
) (S, S) of (C \ C 3 pqr ) ∪ {C q , C r }, such that C q ∈ S, C r ∈ S. ( 34
) (S, S) of (C \ C 4 pqr ) ∪ {C 1 , C r }, such that C r ∈ S, C 1 ∈ S, ( 35
)
where andC 4 pqr = {C p , C q }∪π(C p )∪π(C q )∪π(C r ), respectively. Proposition 11. For an arbitrary quadruple (C p , C q , C r , C s ) of distinct clusters not equal to C 1 , the strengthened 3v GDDL-like inequality x(S, S) ≥ y pq + y qr + y rs -1 is valid for the PCGTSP, for any partition:

C 1 pqr = {C q , C r } ∪ σ(C p ) ∪ σ(C q ) ∪ σ(C r ), C 2 pqr = {C 1 , C r } ∪ π(C p ) ∪ σ(C q ) ∪ σ(C r ), C 3 pqr = {C 1 , C p }∪π(C p )∪π(C q )∪σ(C r ),
(S, S) of (C \ C 1 pqrs ) ∪ {C p , C q , C r , C s }, such that {C p , C r } ⊂ S, {C q , C s } ⊂ S, ( 36
) (S, S) of (C \ C 2 pqrs ) ∪ {C 1 , C p , C q , C s }, such that {C p , C s } ⊂ S, {C q , C 1 } ⊂ S, (37)
(S, S) of (C \ C 3 pqrs ) ∪ {C 1 , C p , C r , C s }, such that {C 1 , C r } ⊂ S, {C p , C s } ⊂ S, (38)
where

C 1 pqrs = {C 1 } ∪ (π(C q ) ∪ π(C r ) ∪ σ(C s )) ∩ (π(C p ) ∪ σ(C q )) , C 2 pqrs = {C r } ∪ (π(C r ) ∪ π(C s ))∩(π(C p )∪σ(C q )∪σ(C r )) , and C 3 pqrs = {C q }∪ (σ(C p )∪σ(C q ))∩(π(C q )∪π(C r )∪σ(C s )
) . Proposition 12. For an arbitrary quintuple (C p , C q , C k , C r , C s ) of distinct clusters not equal to C 1 , the strengthened 4v GDDL-like inequality x(S, S) ≥ y pq + y qk + y kr + y rs -2 is valid for the PCGTSP, for any partition

(S, S) of C \ C pqkrs ∪ {C p , C q , C r , C s }, such that {C p , C r } ⊂ S, {C q , C s } ⊂ S, ( 39
)
where

C pqkrs = {C 1 , C k } ∪ (π(C p ) ∪ σ(C q ) ∪ σ(C k )) ∩ (π(C k ) ∪ π(C r ) ∪ σ(C s )) .
Proofs of all the propositions of this subsection can be obtained by extension of the arguments presented in [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF].

Separation procedures

All the aforementioned families of valid inequalities are augmented with polynomial-time separation procedures, which extend he seminal unit flow propagation approach introduced in Balas et al. (1995). In Algorithm 1, we present the proposed separation technique for π-inequalities (17).

For the sake of brevity, we restrict our further discussion to precedence cycle breaking inequalities (20). Other procedures evolve the similar results obtained in [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF]; [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF]) for the PCATSP and [START_REF] Yuan | A branch-and-cut algorithm for the generalized traveling salesman problem with time windows[END_REF]) for the GTSP with time windows and can be retrieved from the supplemented source code [START_REF] Khachai | Branch-and-cut algorithm for the precedence constrained generalized traveling salesman problem: Gurobi callbacks implementation[END_REF]).

Indeed, suppose we are given by the current fractional solution (x, z, u, y). For a sequence of non-depot clusters C i1 ≺ . . . ≺ C i2t+1 , we construct an auxiliary cluster digraph H = (C ∪ {s, t}, E ′ ), where s and t are artificial source and destination nodes connected by incapacitated arcs with clusters from C ′ odd and C ′ even ∪ {C 1 }, respectively. For each other arc (C p , C q ) ∈ E ′ , its capacity is defined by u pq . Next, if the value of the maximum s-t-flow in the digraph H appears to be less than t + 1, an arbitrary minimum cut (S, S), where S ⊂ C ∪ C ′ odd \ ({C 1 } ∪ C ′ even ) and S = C \ S, defines inequality (20) violated by the given solution.

2: find a maximum C-to-C1 flow F in the graph G C 3: if val(F ) < 1 then 4: find a minimum cut U ′ , U ′′ ⊂ C C 5: set S = U ′ ∪ π(C) and S = C \ S = U ′′ 6: return π-inequality x(S \ π(S)), S \ π(S)) ⩾ 1 7: end if

Facets of the PCGTS polytope

In this section, we study a polyhedral structure of the PCGTS polytope. To elaborate this task, we employ the classic approach relying on dimensions of the studied polytope and its faces.

By definition, for an arbitrary polytope P , its dimension is equal to the dimension of its affine hull dim P = dim (aff(P )), which in turn is one less than the number of affinely independent extreme points this polytope.

An intersection of a polytope P with an arbitrary support hyperplane is called a face of this polytope. Usually, for the sake of convenience, the family of faces of a polytope is extended by improper faces ∅ and P . A face F of a polytope P is called a facet (of this polytope), if dim F = dim P -1.

The PCGTSP is an extension of an Equality GTSP (E-GTSP) introduced in [START_REF] Fischetti | The symmetric generalized traveling salesman polytope[END_REF], where E-GTSP polytope was denoted by P = . Therefore, we keep the same notation for the PCGTS polytope, i.e. the convex hull of the incidence vectors [x, z] encoding all the feasible tours of the problem in question. As it follows from Observation 1, P = = conv{[x, z] ∈ R E∪V : (7) -(16) holds}. Since [x, z] could be obviously extended to the feasible solution [x, z, u, y] of ( 7)-( 16), the polytope P = is isomorphic to the convex hull of the feasible set of the initial non-relaxed MILP model from Subsection 2.2. In the sequel, for the simplicity, we will not distinguish them. Our goal is to derive conditions sufficient for an arbitrary inequality

α T x -β T z ⩾ γ (40)
to induce a facet of the polytope P = .

Dimension of the PCGTS polytope

In this section, we prove the following Theorem 1. For any instance of PCGTSP, the following equation:

dim (P = ) = |E| -n -m + 1 (41)
holds.

To prove Theorem 1, we employ an inductive approach similar to [START_REF] Fischetti | The symmetric generalized traveling salesman polytope[END_REF] on the number of excessive nodes ρ within clusters:

ρ = m h=1 (|C h | -1) = n -m. (42)
Here, the base case ρ = 0 corresponds to the Precedence Constrained Asymmetric Traveling Salesman Problem (PCATSP) and follows from

Theorem 2 [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF]). For an arbitrary instance of PCATSP, dimension of its polytope P = AT SP is as follows: dim P = AT SP = |E| -2n + 1. Remark 1. In the paper by [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF], the polytope is denoted in R E . However, it can be unambigiously extended to R E∪V by setting z v = 1 for each node v ∈ V as it was done in [START_REF] Fischetti | The symmetric generalized traveling salesman polytope[END_REF].

In order to prove the inductive step, we need additional notation and technical lemmas. Let inequality (40) be valid for P = , i.e.

P = ⊂ {[x, z] ∈ R E∪V : α T x ⩾ β T z + γ}. Consider the appropriate face H(α, β, γ) = P = ∩ {[x, z] ∈ R E∪V : α T x = β T z + γ} of the polytope P = .
Further, to any non-individual node v ∈ V , we assign: (i) a PCGTSP polytope P = v associated with the subgraph of G induced by V \ {v}, (ii) the v-restriction of inequality (40) obtained by dropping variables z v and x e for all e ∈ δ(v), (iii) the v-compatibility digraph of (40

) G * v = (V \ C(v), E * v )
, where

E * v = {(i, j) : i, j ∈ V \ C(v), i ̸ = j, ∃ [x, z] ∈ H(α, β, γ), x iv = x vj = 1},
(iv) its bipartite representation B * v (see [START_REF] Bang | Digraphs: Theory, Algorithms and Applications[END_REF] and Fig. 1). Lemma 3. For any valid inequality α T x ⩾ β T z +γ, and an arbitrary non

-individual node v ∈ V , dim H(α, β, γ) ⩾ dim H(α, β, γ) v +rank(B * v )
where H(α, β, γ) v is the face of polytope P = v induced by its v-restriction.

Proof. Consider the matrix M , whose rows are extreme points of the face H(α, β, γ) (Fig. 2). By construction, H(α, β, γ) is contained in a hyperplane of R E∪V not passing through the origin (due to equation ( 7)). Therefore, for any subset of rows of M , the affine independence is equivalent to the linear one. Thus, dim H(α, β, γ) = rank(M ) -1.

Matrix M can be represented as follows:

M = M 11 0 0 M 21 M 22 1 ,
where the last column corresponds to node v, and the columns left to it correspond to the arcs incident with v. By construction, block M 11 corresponds to the extreme points of face

H(α, β, γ) v . Thus, rank(M 11 ) = dim H(α, β, γ) v + 1.
On the other hand, matrix M 22 is located in the part of the tour visiting node v. By construction, it should visit it only once. Therefore, each row of M 22 has exactly two 1s. Consider an arbitrary row of block M 22 . Suppose that 1s are located in the columns (i, v) and (v, j). Hence, in graph B * v , nodes i and j are adjacent and the considered row is a column in the incidence matrix

M B * v of B * v . Thus, M 22 = M T B * v (see Fig. 3). Therefore, rank(M 22 ) = rank(B * v ) = N B * v -κ(B * v ), where N B * v is a size of the nodeset of bipartite graph B * v and κ(B * v )
is the number of its connected components (see e.g. [START_REF] Biggs | Algebraic Graph Theory[END_REF]). Proof. We prove Lemma 4 by enumeration of all the possible options to relate cluster C(v) with the given precedence constraints. In the sequel, we use the following notation. By π and σ, for cluster C(v), we denote subsets of nodes belonging to its direct parents and children, respectively.

Similarly, we introduce subsets π and σ of nodes that belong to other ancestors and descendants of this cluster. In addition, by r, we denote a union of all clusters except C Balas incompatible with C(v).

Observation 2. For any cluster, its parents (if any) are mutually incomparable. For its children the same claim is valid as well. v has a complete bipartite subgraph, whose parts are induced by clusters C(i) and C(j). In Fig. 5, we encode such subgraphs by straight line segments. By construction, all non-isolated nodes of B * v belong to the only connected component. Furthermore, the number of connected components is κ( B * v ) = 1 + |C 1 | + 2|π| + |π|. Indeed, for instance, verify the incidence of some i ∈ π and node j ′ corresponding to the only node of cluster C Balas . Take an arbitrary node v 1 ∈ C 1 from the depot and construct a feasible tour as follows. Departing from v 1 the tour visits all the clusters preceding C(v) such that the cluster C(i) is visited last, at node i. Then, we traverse arcs (i, v) and (v, j) directly, visit all the remaining clusters (respecting the precedence constraints) and complete the tour by returning to node v 1 .

Finally, rank( B *

v ) = N B * v -κ( B * v ) = |C 1 | + |π| + 2|r| + 1 = |δ(v)| -1.
Case 2 (σ ̸ = ∅ and π = ∅). This case is dual to Case 1, here C(v) is the maximal ancestor in the partial order. In the similar sense (see Fig. 6 and Fig. 7), we obtain |δ(v)| =

|C 1 | + |σ| + 2|r| + 2, N B * v = 2|C 1 | + 2|σ| + 2|σ| + 2|r| + 2, κ( B * v ) = 1 + |C 1 | + 2|σ| + |σ|, and finally, rank( B * v ) = |C 1 | + |σ| + 2|r| + 1 = |δ(v)| -1. Case 3 (π ̸ = ∅, σ ̸ = ∅).
The only difference here is that cluster C(v) has both parents and children, which slightly impacts the structure of B * v . Proceeding with the proof in a similar way, we obtain (Fig. 8 and Fig. 9

): |δ(v)| = |π|+|σ|+2|r|+2, N B * v = 2(|C 1 |+|σ|+|σ|+|π|+|π|+|r|+1), κ( B * v ) = 1 + 2|C 1 | + |σ| + |π| + 2|π| + 2|σ|, and rank( B * v ) = 2|π| + 2|σ| + 2|r| + 1 = |δ(v)| -1. Case 4 (π = ∅, σ = ∅).
Without loss of generality, we restrict ourselves to the case where the set of free clusters is exhausted by C(v) and C Balas (if the set of free clusters has more than two elements, the case is similar to this one). Since this case is different from the discussed above, we provide an argument in detail. Since v is a non-individual node, C(v) ̸ = C Balas . Again for cut δ(v), we have |δ(v)| = 2|C 1 | + 2|r| + 2. We show that in this case B * v is a connected bipartite graph. We skip the trivial option of the empty order, since here B * v is a complete graph. Otherwise, there are always at least two clusters C p and C q , such that C p is the parent of C q . Obviously, these clusters induce a complete bipartite subgraph of graph B * v . Since both copies of C Balas are incident with all other clusters from the opposite part, B * v is connected (see Fig. 10). Finally, we obtain

N B * v = 2|C 1 |+2|r|+2, κ( B * v ) = 1, and rank( B * v ) = 2|C 1 |+2|r|+1 = |δ(v)|-1.
Case 5 (C(v) = C 1 ). This is another unique case. To proceed with our proof, we need additional notation. By Σ, we denote the set of all nodes from minimal descendants, Π consists of all nodes from maximal ancestors in the given partial order. Also, let F be the set of all nodes from free clusters, except C Balas , and R are the remaining nodes. Then, |δ(v

)| = 2|F | + |Π| + |Σ| + 2.
As for the graph B * v , it is constructed in the same sense as for the previous cases. The only difference here, is that the depot is departure and arrival node at the same time. However, this won't be a problem, since any feasible tour is closed (see Fig. 11). Finally, Proof. By construction, the PCGTS polytope P = is a part of a solution set of inequality system (7)-(11). Hence, dim P = cannot be greater than dimension of this solution set. In turn, for an arbitrary feasible system of linear equations Ax = b with m × d coefficient matrix, dimension of its solution set is d -rank(A).

N B * v = 2(|R| + |Π| + |F | + 1 + |Σ|), κ( B * v ) = 1 + |Π| + |Σ| + 2|R|,
Let A be the coefficient matrix of system ( 7)-(11) (Fig. 12). By construction, rank(A) ⩾ rank(D) + rank(K) = rank(D) + m. We show that rank(D) = 2n -1. To the initial graph G, we assign cluster digraph G c = (C, E c ), for which (C ′ , C ′′ ) ∈ E c if and only if there exist i ∈ C ′ and j ∈ C ′′ , such that (i, j) ∈ E. Let B G and B Gc be bipartite representations of digraphs G and G c respectively.

Observation 3. Evidently, if (C ′ , C ′′ ) ∈ E c , then (i, j) ∈ E ∀i ∈ C ′ ∀j ∈ C ′′ .
Observation 4. By construction, D is the incidence matrix of B G . As a simple consequence, we obtain that graphs B G and B Gc have the same number of connected components.

Since the initial graph G has at least one free cluster, then by Proposition 5.3 from [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF], B Gc is connected, i.e. κ(B Gc ) = κ(B G ) = 1, rank(D) = 2n-1, and rank(A) ⩾ 2n+m-1. Therefore,

dim P = ⩽ |E| + |V | -rank(A) ⩽ |E| + n -2n -m + 1 = |E| -n -m + 1. ( 43
)
To complete the argument, we need to prove the lower bound

dim P = ⩾ |E| -n -m + 1. ( 44
)
We proceed with induction on the number of excessive nodes within clusters:

ρ = m h=1 (|C h | -1) = n -m
Base Case (ρ = 0) follows from Theorem 2 for the PCATSP.

Inductive

Step. Assume that inequality (44) holds for some ρ. To prove it for ρ + 1, take an arbitrary non-individual node v. By Lemma 3 and Lemma 4,

dim P = ⩾ dim P = v + rank( B * v ) = dim P = v + |δ(v)| -1.
Recall that P = v corresponds to the graph of n -1 nodes and |E \ δ(v)| arcs. By induction hypothesis, dim

P = v ⩾ |E| -|δ(v)| -n -m + 2
, and the claim follows. Combination of ( 43) and ( 44) concludes the proof.

Facet-inducing inequalities

By extending the results obtained in [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF], in this subsection we establish the sufficient conditions ensuring that π-and σ-inequalities (( 17) and ( 18)) introduced in Subsection 3.1 are facet-inducing. induces a facet of the polytope P = , if π(S) ⊂ S, σ(S) ⊂ S, and S contains at least 3 free clusters.

Similarly to Theorem 1, our proof is based on the inductive framework developed in [START_REF] Fischetti | The symmetric generalized traveling salesman polytope[END_REF] for the symmetric GTSP. The induction is carried out on the number of excessive nodes (42) in clusters. Since the base case corresponds to the classic PCATSP, our claim follows from the known result [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF], Theorem 5.5). In turn, proof of the inductive step relies on Lemma 3 and our adaptation of Lemma 4 to the case of the proper face H π = H(α, β, γ), where

β = 0, γ = 1, α i,j = 1, ∃C p ∈ S \ π(S), ∃C q ∈ S : i ∈ C p , j ∈ C q , 0, otherwise
induced by inequality (45).

Lemma 7. Let H π be the face of P = induced by π-inequality (45). The hypothesis of Theorem 5 implies that, for an arbitrary non-individual node v, rank(

B * v ) = |δ(v)| -1.
Proof. Our argument is based on enumeration of all the possible options to establish a relation between cluster C(v) and the given partial order. Previously, in the proof of Lemma 4, for each case, we explored properties of the associated cut δ(v) and bipartite graph B * v . Now, each of these options can be split into several sub-options in correspondence to the ways to locate C(v) with respect to the face H π (see Table 1). It is easy to verify that all subcases of any unique case presented at a single line of Table 1 share the same cut δ(v), while their associated bipartite graphs B * v are spanning subgraphs of graph B * v constructed in Lemma 4 for the entire polytope P = . In its proof, we showed that, for any v, graph B * v contains a single connected component. Therefore, to prove Lemma 7, it is sufficient to show that the same node subset induces a connected component in any mentioned graph B * v as well. For the sake of brevity, we restrict ourselves to cases 3 and 4 (see Table 1), since they appear to be the most common. For the other cases, the argument can be obtained in a similar way.

As in the proof of Lemma 4, by π, σ, and r, we denote the subsets of nodes (in graph G) belonging to parent, child and incomparable clusters with respect to cluster C(v), respectively.

Case 3 (π ̸ = ∅, σ ̸ = ∅). In both subcases, for C(v) ∈ π(S) and C(v) ∈ S, we verify the connectivity of the subgraphs induced by the connected component found in the proof of Lemma 4, Case 3. We present these subgraphs in Fig. 13 in more detail. To prove their connectivity, it is sufficient (a) to show that the single node from C Balas is adjacent to any other node from the opposite part of graph B * v ; (b) to present at least one additional arc connecting nodes from any two clusters other than C Balas .

(a) For instance, we establish the existence of an arc connecting node i ∈ C Balas and some node j belonging to some child cluster C ∈ S ′ = S \ π(S) of cluster C(v) (Fig. 13). Departing from the depot, we start with construction of a tour T by visiting all the clusters in S except C Balas (regarding the precedence constraints). Then, we proceed with all the ancestors of cluster C(j) except C(v). This is possible due to Proposition 2. Further, we traverse the i-v-j fragment and proceed with visiting all the remaining clusters in π(S). Finally, we randomly visit all the clusters in S ′ and return to the depot by a direct arc. By construction, it is the only arc in the proposed tour that belongs to the cut δ + (S \ π(S), S) (in graph G). Therefore, for this tour, inequality (45) becomes tight.

(b) Without loss of generality, provide an argument for subcase C(v) ∈ S (Fig. 13). Let i be any node from some parent C(i) of C(v), and j belongs to a free cluster C(j). Again, we consider the tour T departing from an arbitrary depot node. We visit all the ancestors of C(v), except C(i). Next, we pass through the i-v-j fragment and continue from C(j) by visiting all the clusters in π(S). Then, we proceed with traveling over the rest of S ′ . Finally, we return to S by an arc that belongs to the cut δ + (S \ π(S), S), and complete the tour by visiting the remaining clusters, arriving at the depot.

Case 4 (π = ∅, σ = ∅). Generally speaking, the argument for this case is close to the previous one. However, we mention it separately, since this case appears to be the only reason for requiring at least three free clusters from S ′ in the hypothesis of Theorem 5. As it follows from Fig. 14, for C(v) ∈ S ′ , cluster C Balas does no longer induce a dominating set in the considered subgraph (of graph B * v ). Instead, free clusters take its place. Furthermore, these free clusters ensure the connectivity of the subgraph. Indeed, consider free clusters C(i), C(j) ∈ S ′ , such that C(i) ̸ = C(v) ̸ = C(j). Construct a feasible tour T with the fragment i-v-j in graph G. Since C(i), C(v) and C(j) are free and belong to S ′ , we are allowed to move i-v-j directly after the departure from the depot. Then, after visiting all the clusters in π(S), we come to the remaining clusters from S ′ , cross the border between S ′ and S (at once), move through all the clusters in S and return to the depot.

In subcase C(v) ∈ S (Fig. 14), the proof can be obtained in a similar way to the Case 3. Lemma 7 is proved.

-M * 1 is M 1 augmented with π-, σ-, and (π, σ)-inequalities (17)-( 19), precedence cycle breaking inequalities ( 20) and ( 21), and inequalities ( 22)-( 26).

In order to increase the tightness of the lower bounds, we combine M * 1 with other best performers of our exploratory Experiment I (see Subsection 7.2):

-M * 3 , which is M * 1 + M 3 and -M * 5 = M * 1 + M 5 .
In all these models, families of valid inequalities are separated exactly, following to the incremental pattern proposed in [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF]. Although the models M 3 and M 5 clearly benefit from the combination with M * 1 in terms of the lower bounds, they still remain to be rather time-consuming.

Therefore, by evolving the well-known roulette-wheel sampling principle (see ex. [START_REF] Gendreau | Handbook of Metaheuristics[END_REF]) and simple online learning technique, we propose a novel heuristic separation procedure and the corresponding models M * 3s and M * 5s , which we call sampled as well. The main idea of the proposed procedure is as follows:

-to each family of valid inequalities, we assign an appropriate probabilistic measure; for instance, in the case of 3v GDDL-like inequalities ( 36)-( 38), it is sufficient to define a discrete distribution on the set of ordered quadruples (C p , C q , C r , C s ) of non-depot clusters; -given by a sample size, at each separation epoch, we apply cut generation technique at this epoch only to the entries of a sample drawn from the defined distribution; -each time, when a tuple managed to produce a cut, we increase its probability.

Generally speaking, the proposed separation heuristic is a compromise between the tightness of the LP-relaxation bounds and numerical performance. However, we decide to evaluate it in our experiments along with the known incremental separation pattern, because the sampling gives us an opportunity to adopt powerful but large families of valid inequalities from the very beginning of the LP-relaxation solution process.

Branch-and-Cut Algorithm

Our branch-and-cut algorithm extends the algorithm proposed in [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF] for the SOP and has a component-wise structure based on few main building blocks. Among them are instance preprocessing routine, primal heuristic, and a formulation of the problem in question that specifies a family of cutting planes.

In its current version, the proposed algorithm is restricted to use the same instance preprocessing routine. The arcs violating precedence constraints are excluded from the given graph by preprocessing rules ( 1)-( 5), previously introduced in [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF] for the PCATSP. In addition, as the only primal heuristic, the algorithm uses PCGLNS, proposed in Khachay et al. (2020) and briefly described in Subsection 6.1. Thus, all the proposed variants of the algorithm (refer to Subsection 7.3 for details) were obtained by varying the problem formulation.

PCGLNS Primal Heuristic

The PCGLNS heuristic extends the recent GLNS algorithm proposed in [START_REF] Smith | GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem[END_REF] for the common GTSP. PCGLNS is designed to take into account additional precedence constraints defined on a set of clusters. In a nutshell, PCGLNS appears to be an original implementation of the seminal Adaptive Large Neighborhood Search (ALNS) metaheuristic (see, e.g. [START_REF] Gendreau | Handbook of Metaheuristics[END_REF]) and combines the well-known ruin and recreate principle with online learning over a given sets of basic removal and insertion local search heuristics. n and m are the number of nodes and clusters respectively 'PC density' is the number of arcs in the transitively closed precedence DAG

Implementation

The proposed algorithm is implemented on top of the Gurobi 9.3 framework. Primal heuristic and cutting planes are provided as user callback functions. For the sampled models, all the parameters of the heuristic separation including sample sizes and learning rates are tuned within preliminary testing stage. All the built-in Gurobi heuristics and cutting plane algorithms are disabled, while other parameters of the solver keep their default values. The suggested implementation is carried out in Python 3 leveraging NetworkX software package for internal graph processing tasks and fully cross-platform. All source code together with the reported experimental results are open for public access at [START_REF] Khachai | Branch-and-cut algorithm for the precedence constrained generalized traveling salesman problem: Gurobi callbacks implementation[END_REF].

Numerical evaluation

In this section, we report results of the competitive numerical experiments that show how each proposed formulation and variant of the branch-and-cut algorithm could be useful for the PCGTSP. In particular, these results reveal the notable impact contributed by predecessor/successor inequalities in terms of accuracy and running time, which can be considered as an additional support of the theoretical results obtained in Section 4. We proceed with two separate experiments. In the former one, we evaluate the proposed formulations with respect to their LP-relaxation bounds and the time consumption. In turn, the purpose of the latter one is to compare the best performers of the first experiment with known results within the branch-and-cut setting. All the computations are carried out on the 16-core Intel Xeon 128G RAM server2 against the same public benchmark library PCGTSPLIB.

PCGTSPLIB Benchmark library

The PCGTSPLIB library was derived in [START_REF] Salman | Branch-and-bound for the Precedence Constrained Generalized Traveling Salesman Problem[END_REF] from the well-known SOPLIB library in order to provide a test-bed for PCGTSP. To the best of our knowledge, it is the only public library for the problem in question. We provide a short overview of this library in Table 2.

Since computational complexity of the PCGTSP depends mostly on the number of clusters m (rather than the size of a node set n, as it is for SOP), it is convenient to partition all 40 instances of this library into small (up to 30 clusters), medium (up to 70 clusters), large (up to 120 clusters), and huge ones (more than 120 clusters). In addition, the instances differ substantially in terms the density of the constituent partial orders.

For each instance, we round the transportation costs to the nearest integral values. For the sake of convenience, we provide the converted instances along with our source codes Khachai (2022).

Experiment I: Comparison of the LP-relaxations

Inspired by the results of [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF], we start with the comparison of the formulations M 1 -M 5 and M * 1 in terms of their LP-relaxation bounds and time complexity. In this experiment, for each competing model, computation time was limited to 10 hours (36000 seconds).

Since the separation procedures for M 2 -M 5 follow the incremental pattern initially proposed for the SOP, more complex formulations provide tighter lower bounds, perhaps with substantially increased computation time. Therefore, for each instance, whose optimum value is achieved by some M i model, we do not solve it by M j , for any j > i. As it follows from Table 3, the optimum values were found for 8 out of 40 instances: for ESC63 -by model M 1 , for br17.10 and br17.12 -by model M 2 , for other five -by model M * 1 (along with M 2 and M 5 for rbg048a and rbg050c, respectively). For the remaining instances, M 2 found the tightest lower bound once, M 3 three times as well as M 5 , and M * 1 -25 times. Although the model M * 1 appears to be the best performer for the most cases, there exist instances, e.g. ft53.4, ft70.4, and ry48.p4, where some other competitors found more tight lower bounds. Therefore, we evaluate models M * 3 and M * 5 obtained by combination M * 1 with M 3 and M * 1 with M 5 , where M 5 and M 3 are chosen for the combination as the most powerful and wellbalanced3 models among M 2 -M 5 respectively.

According to results presented in Table 4, formulations M 3 , M 5 and M * 1 collaborate quite well. In particular, for instances ft53.2, ft70.1 and p43.2, M * 3 provides better lower bounds than both initial models M 3 and M * 1 . The similar result can be observed for instances ry48p.3 and ft53.4 with respect to formulations M 5 , M * 1 and their combination M * 5 . While the combined models perform better than their initial counterparts, they still remain to be quite expensive to be applied in the branch-and-cut algorithm. On the other hand, comparing the model M * 3 with the sampled one M * 3s and excluding tiny instances ESC07, ESC12, br17.10 and br17.12, we observe the significant decrease of the time complexity, i.e. LP-relaxation was solved 16 times faster in average. Furthermore, the better lower bounds were obtained in 18 out of 36 remaining instances. For those instances where M * 3s found less accurate results, the lower bound decreased at most by 1.7%. In addition, we should emphasize one large instance rbg109a, where M * 3s found an optimum value of the LP-relaxation faster than all other competitors. As for the models M * 5 and M * 5s , we observe average speed-up by 59 times and better lower bounds in 22 out the same 36 instances. For that instances, where M * 5 outperform its sampled counterpart, the lower bound decreased at most by 5.2%. In addition, we should emphasize the instance ESC25, for which M * 5s was the only competitor, who found the optimum value. To summarize, we conclude that the addition of predecessor/successor inequalities and application of the proposed heuristic separation procedure can provide significant improvement in LP-relaxation of the PCGTSP.

Experiment II: Comparison of Branch-and-Cut Algorithms

This experiment is intended to assess variants of the branch-and-cut algorithm proposed in Section 6 induced by several formulations introduced in Section 5.

For the first competition, we choose variants bc * 1 , bc * 3s , and bc * 5s induced by the best performers of Experiment I, the models M * 1 , M * 3s , and M * 5s respectively. In addition, we consider the variant bc * MTZ induced by the formulation M * 1 , where the compact model is replaced with an adapted to the PCGTSP classic compact Miller-Tucker-Zemlin model [START_REF] Miller | Integer programming formulation of traveling salesman problems[END_REF]). It can be obtained from the considered compact model by replacing constraints ( 12)-( 15) with (m -1)u pq + v p ≤ v q + m -2 (C p , C q ∈ C \ {C 1 }, p ̸ = q), for 0 ≤ v p , v q ≤ (m -2), and exclusion of y variables. Such a model was chosen intentionally, as one of the lightest known compact models ensuring efficient enumeration of the nodes of branching tree. As baselines, we use:

-Gurobi solver applied to the model M 1 with default configuration (including built-in heuristics and cutting planes), -our PCGTSP adaptation bc * DFJ of the state-of-the-art branch-and-cut algorithm for the SOP proposed in [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF]. This algorithm tackles the similar partial classic Dantzig-Fulkerson-Johnson (DFJ) model [START_REF] Dantzig | Solution of a large-scale traveling-salesman problem[END_REF] ((6)-(11), and ( 16) without y variables) and separates corresponding families of valid inequalities ( 17)-( 26). In addition, we replace the initial primal heuristic with our GLNS-based heuristic PCGLNS, since GLNS appears to be more efficient for the GTSP-like problems (see [START_REF] Smith | GLNS: An effective large neighborhood search heuristic for the Generalized Traveling Salesman Problem[END_REF]). inequalities. Then, we established dimension of the PCGTS polytope and proved sufficient conditions for the predecessor/successor inequalities to be facet-inducing.

Further, we offered a sequence of novel formulations for the PCGTSP and proposed the first branch-and-cut algorithm relying on these fomulations. In the numerical evaluation, we reported the most efficient formulations in terms of LP-relaxation bounds and suggested several wellcollaborating variants of the proposed branch-and-cut. As a result, the number of PCGTSPLIB instances solved to optimality became 23 out of 40, where for 11 instances it was done for the first time.

In addition, the obtained results confirmed the importance of the predecessor/successor inequalities for the PCGTSP, both for LP-relaxation and branch-and-cut framework.

  In turn, by π(C) and σ(C) we denote the subsets of π(C) and σ(C) respectively consisting of the direct parents and children of the cluster C. Finally, by C + = m i=2 π(C i ) and C -= m i=2 σ(C i ) we denote the sets of all aforementioned predecessors and successors, respectively.

Algorithm 1

 1 Separation technique for π-inequalities Input: current (fractional) solution (xij , zi, upq, ypq), a non-depot cluster C ̸ = C1 Output: π-inequality for an appropriate S (if any) 1: create an auxiliary cluster digraph G C = (C C , E C ), where C C = C \ π(C) and (Cp, Cq) belongs to E C and has capacity upq if and only if upq > 0

Figure 1 :

 1 Figure 1: Example of a directed graph and its bipartite representation

Figure 2 :

 2 Figure 2: Matrix of extreme points of H(α, β, γ)

Case 1 (

 1 π ̸ = ∅ and σ = ∅). In this case, cluster C(v) is one of the minimal descendants in the given partial order. Here, for cut δ(v) in graph G (see Fig. 4), we have |δ(v)| = |C 1 | + |π| + 2|r| + 2, since |C Balas | = 1. Consider the appropriate bipartite graph B * v (Fig. 5). It has N B * v = 2|C 1 |+2|π|+2|π|+2|r|+2 nodes. By definition, an arbitrary node i from the left part and j ′ from the right part of graph B * v are incident if and only if there is a feasible tour with the fragment i-v-j. If such an arc exists, then graph B *

Figure 3 :Figure 4 :Figure 5 :

 345 Figure 3: Block M22 and the incidence matrix of B * v

  and rank( B * v ) = |δ(v)| -1. Lemma 4 is proved.

Figure 6 :Figure 8 :Figure 9 :Figure 10 :

 68910 Figure 6: Cut δ(v) for Case 2 Figure 7: Bipartite graph B * v for Case 2

Figure 11 :Figure 12 :

 1112 Figure 11: Representation of δ(v) and the connected components of the B * v for Case 5

Theorem 5 .

 5 For S ⊂ C \ {C 1 , C Balas } and S = C \ S, an inequality x(S \ π(S), S) ⩾ 1 (45) induces a facet of the polytope P = , if π(S) ⊂ S, σ(S) ⊂ S, and S contains at least 3 free clusters. Theorem 6. For S ⊂ C \ {C 1 , C Balas } and S = C \ S, an inequality x( S, S \ σ(S)) ⩾ 1(46)

  case # relation to the partial order relation to the face Hπ 1

Figure 13 :Figure 14 :

 1314 Figure 13: Connected components of B * v for Case 3. C(v) ∈ S (left) and C(v) ∈ S (right)

Table 1 :

 1 Options for cluster C(v).

Table 2 :

 2 PCGTSPLIB library.

	instance	n	m	PC density	instance	n	m	PC density
	ESC07	39	8	14	p43.1	203	43	53
	ESC12	65	13	23	p43.2	198	43	76
	ESC25	133	26	36	p43.3	211	43	138
	ESC47	244	48	79	p43.4	204	43	538
	ESC63	349	64	296	prob.100	510	99	139
	ESC78	414	79	361	prob.42	208	41	59
	br17.10	88	17	31	rbg048a	255	49	495
	br17.12	92	17	38	rbg050c	259	51	558
	ft53.1	281	53	64	rbg109a	573	110	5438
	ft53.2	274	53	82	rbg150a	871	151	10484
	ft53.3	281	53	269	rbg174a	962	175	14129
	ft53.4	275	53	811	rbg253a	1389	254	30434
	ft70.1	346	70	86	rbg323a	1825	324	48525
	ft70.2	351	70	117	rbg341a	1822	342	56644
	ft70.3	347	70	284	rbg358a	1967	359	56894
	ft70.4	353	70	1394	rbg378a	1973	379	63963
	kro124p.1	514	100	132	ry48p.1	256	48	59
	kro124p.2	524	100	169	ry48p.2	250	48	73
	kro124p.3	534	100	365	ry48p.3	254	48	179
	kro124p.4	526	100	2404	ry48p.4	249	48	643

Table 3 :

 3 Comparison of formulations M 1 -M 5 and M * 1 . Notes: column 'OPT' provides optimum values of the instances (if known) or the best bounds; columns M 1 -M 5 and M * 1 present LP-relaxation lower bounds and the corresponding running times; optimum values highlighted in bold, best lower bounds underlined

	Instance	OPT	LPB	M 1	t	LPB	M 2	t	LPB	M 3	t	LPB	M 4	t	LPB	M 5	t	LPB	M * 1	t
	ESC07	1730	1683		0	1730		0.28	1730		0.29	1730		0.29	1730		0.3	1730		0.09
	ESC12	1390	1238		0.02	1387		5.91	1387		7.1	1387		8.21	1387		9.97	1390		0.8
	ESC25	1383	1296		0.21	1362		229	1362		300	1362		364	1362		448	1363		7
	ESC47	1063	1001		8.46	1012		2982	1012		3545	1013		4655	1016		7420	1023		119
	ESC63	62	62		207.36	-		-	-		-	-		-	-		-	62		318
	ESC78	[14673, 14808]	14629		3829.32	14640		23287	14641		36000	14641		36000	14641		36000	14659		5477
	br17.10	43	15		0.05	43		6.81	-		-	-		-	-		-	32		5
	br17.12	43	15		0.05	43		6.54	-		-	-		-	-		-	35		6
	ft53.1	6194	4981		9.71	5780		7045	5781		9646	5781		10540	5781		12688	5833		400
	ft53.2

Table 4 :

 4 Performance of the combined and sampled formulations.

	Instance	OPT	LPB	M * 1	t	LPB	M 3	t	LPB	M 5	t	LPB	M * 3	t	LPB	M * 5	t	M * 3s LPB	t	M * 5s LPB	t
	ESC07	1730	1730		0.09	1730		0.29	1730		0.3	1730		0.29	1730		0.3	1730	0.04	1730	0.06
	ESC12	1390	1390		0.8	1387		7.1	1387		9.97	1387		7.2	1387		10	1390	0.35	1390	0.46
	ESC25	1383	1363		7	1362		300	1362		448	1362		205	1362		221	1363	13	1383	4.31
	ESC47	1063	1023		119	1012		2982	1016		7420	1014		5899	1018		6658	1026	247	1030	589
	ESC63	62	62		318	62		8491	62		36000	62		13790	62		16506	62	250	62	243
	ESC78	[14673, 14808]	14659		5477	14640		23287	14641		36000	14660		36000	14660		36000	14660	6106	14660	5312
	br17.10	43	32		5	43		7	43		12.63	43		6.87	43		8.1	35	6	33	5
	br17.12	43	35		6	43		7	43		35.05	43		6.69	43		7.99	34	5	34	4
	ft53.1	6194	5833		400	5781		9646	5781		12688	5803		4786	5803		6144	5895	910	5833	375
	ft53.2	[6581, 6619]	5982		174	5960		8084	5962		17774	6035		7282	6035		10144	5981	237	5982	124
	ft53.3	[8323, 8446] 7180 Notes: column 'OPT' provides optimum values of the instances (if known) or the best bounds; 7178 200 7169 8637 7169 13080 7169 7717 7171 10286 7176 300
		optimum values highlighted in bold

Table 5 (

 5 a): Comparison of the branch-and-cut algorithms

	Instance	OPT		Gurobi	bc * DFJ	bc * 1	bc * 3s	bc * 5s	bc * MTZ	bc 3s	bc MTZ
			UB	1730	1730	1730	1730	1730	1730	1730	1730
	ESC07	1730	LB gap	1730 0	1730 0	1730 0	1730 0	1730 0	1730 0	1730 0	1730 0
			t	0.05	0.06	0.09	0.04	0.06	0.05	0.06	0.05
			UB	1390	1390	1390	1390	1390	1390	1390	1390
	ESC12	1390	LB gap	1390 0	1390 0	1390 0	1390 0	1390 0	1390 0	1390 0	1390 0
			t	5.05	0.58	0.8	0.35	0.46	0.19	2.14	0.37
	ESC25	1383

Generalized Disaggregated Desrochers-Laporte inequality

provided by Supercomputer 'Uran' at Krasovsky Institute of Mathematics and Mechanics

with respect to accuracy and time consumption

Now, we are ready to establish the proof of Theorem 5.

Proof. Let H π be the face of polytope P = induced by π-inequality. By Theorem 1, we have dim H π ⩽ dim P = = |E| -n -m + 1. By induction on number ρ (see eqn. ( 42)), we show that dim H π ⩾ |E| -n -m.

(47)

Base case of (ρ = 0) is proved in [START_REF] Balas | The precedence-constraint asymmetric traveling salesman polytope[END_REF], since, in this case, the problem at hand is equivalent to the PCATSP.

Inductive step. Assuming that (47) holds for some ρ, prove it for ρ + 1. Combining claims of Lemma 3 and Lemma 7, we have dim To finalize the proof, we show that inequality (47) is tight. Indeed, suppose by contradiction that it is not. But, under this assumption, dim H π = dim P = and, consequently the face H π coincides with the polytope P = . However, we can always provide a feasible solution crossing the outgoing cut δ + (S \ π(S)) at least twice (see, e.g., Fig. 15). Theorem 5 follows from the obtained contradiction.

For the sake of brevity, we omit the proof of Theorem 6, which can be obtained in a similar way.

Formulations

In this section we describe novel MILP-models (formulations) for the PCGTSP. Almost all of them are extensions of the known formulations proposed initially in [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric traveling salesman problem[END_REF]; [START_REF] Gouveia | Load-dependent and precedence-based models for pickup and delivery problems[END_REF]; [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF] for the PCATSP and incorporate exponential size families of valid inequalities introduced for the PCGTSP in Section 3.

Following to [START_REF] Gouveia | Combining and projecting flow models for the (precedence constrained) asymmetric traveling salesman problem[END_REF], we start with the sequence of models obtained incrementally as follows:

-M 1 is our basic compact model described in Subsection 2.2, -M 2 is M 1 augmented with strengthened simple-cut ( 27)-( 29) and both strengthened regular (30), and reversed GDDL (31) inequalities, -M 3 is M 2 with strengthened 2-path inequalities (32)-( 35), -M 4 is M 3 enforced by strengthened 3v GDDL-like inequalities ( 36)-( 38), -M 5 is M 4 supplied with strengthened 4v GDDL-like inequalities (39).

In addition, we propose the model incorporating the inequalities described in Subsection 3. All the competitors are supplied with the same primal heuristic PCGLNS. The time limit is set to 20 hours (72000 seconds). We report cost of the best found solution (UB), the best lower bound (LB), an accuracy measure (gap, in percentage)

for the relative error ε of the obtained solution, and the elapsed time (in seconds).

As it follows from Tables 5(a)-5(d), both baseline algorithms solved to optimality 17 out of 40 instances in total, where the instances rbg150a and rbg174a (which are huge ones) were solved by Gurobi solely, and the instances ft53. 1, ft70.1, p43.1, p43.4, prob.42 -by bc * DFJ . In turn, the proposed algorithms bc * 1 , bc * 3s , bc * 5s , bc * MTZ managed to solve to optimality 23 out of 40 instances in total including all the mentioned above. Regarding to the new six instances, ft53.4 and ry48p.4 were solved by all of them, the instance rbg253a was solved by bc * 1 , the instance rbg323a -by bc * 3s , bc * 5s and bc * MTZ . Finally, the optimal solutions of the instances p43.2 and p43.3 were found by both bc * 3s and bc * 5s . In addition, each of 15 instances solved to optimality by bc * DFJ is also solved exactly by one of the proposed variants about 8 times faster in average. Nevertheless, we should mention instances ESC25, rbg048a, and rbg050c, where bc * DFJ outperforms other competitors in terms of the elapsed time.

In the residual 17 open instances, the proposed algorithms managed to significantly increase lower bounds and close the average gap value about 4.5 times better than both baselines and complement each other quite well.

Our second observation is related to the comparison of variants bc * 3s and bc * MTZ with the corresponding counterparts bc 3s and bc MTZ obtained by exclusion the predecessor / successor inequalities from the separation pipeline. Regarding to bc 3s and bc * 3s , we observe that inclusion of such inequalities allows to solve to optimality three additional instances (p43.2, p43.3, and rbg323a). Furthermore, for 12 out of 16 instances solved by both competitors exactly, we observe notable decrease of the running rime. In addition, for the remaining 21 instances, bc * 3s closed the gap by 1.7 times better in average. In turn, we should note that bc * MTZ significantly outperforms bc MTZ in terms of instances solved to optimality, gap values and elapsed time.

Therefore, the predecessor/successor inequalities are proved to be useful for the PCGTSP in the branch-and-cut setting as well.

Conclusion

In this paper, we addressed the Precedence Constrained Generalized Traveling Salesman Problem (PCGTSP) both in terms of the polyhedral study and algorithmic analysis. By evolving the results previously introduced for PCATSP, we proposed several novel families of the valid