M T Godinho
email: mtgodinho@ipbeja.pt

L Gouveia
email: legouveia@fc.ul.pt

P Pesneau
email: pierre.pesneau@math.u-bordeaux1.fr

On a Time-Depedent Formulation and an updated classication of ATSP formulations

 for the time-dependent traveling salesman problem (TDTSP). The previous paper provides one way of viewing the new model, the time-dependent TSP point of view where it is put in evidence how to obtain the new model by tightening the linear programming relaxation of a well known formulation for the TDTSP. In this chapter, we will present the ATSP point of view and will show how to obtain the model by i) enhancing the subproblem arising in the standard multicommodity ow (MCF) model for the ATSP and then ii) by using modelling enhancement techniques. We will compare the linear programming relaxation of the new formulation with the linear programming relaxation of the three compact and non-dominated formulations presented in Oncan et al. [19]. As a result of this comparison we present an updated classication of formulations for the asymmetric traveling salesman problem (ATSP).

Introduction

In this chapter we present an updated classication of formulations for the asymmetric traveling salesman problem (ATSP). In the past, several papers have produced a classication of formulations for the ATSP, in terms of the associated linear programming relaxations. Among others, we may consider the papers by Gouveia and Voss [START_REF] Gouveia | A classication of formulations for the time-dependent Traveling Salesman Problem[END_REF], Langevin et al [START_REF] Langevin | Classication of traveling salesman formulations[END_REF], Gouveia and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem and a Reformulation of the Miller-Tucker-Zemlin Constraints[END_REF],

Orman and Williams [START_REF] Orman | A Survey of Dierent Integer Programming Formulations of the Traveling Salesman Problem[END_REF] and Oncan et al [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF]. These papers fall among two classes. Either they produce new results between formulations known from the literature, or they use the fact that new formulations are also being presented in the paper in order to upgrade a classication already known from the literature. Our chapter falls in the second category in the sense that we are going to contextualize, in terms of the ATSP, a recent compact formulation presented in Godinho et al [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] for the time-dependent traveling salesman problem (TDTSP).

Let G = (V, A) be a graph where V = {1, 2, .., n} and A = {(i, j) : i, j = 1, .., n, i = j}. In the ATSP we consider costs c ij associated to each arc (i, j) and we want to nd a minimum cost Hamiltonian circuit, starting and ending on node 1. In the TDTSP, we also want to nd a minimum cost Hamiltonian circuit, starting and ending on node 1. However, the arc costs depend on their position in the tour. Thus, to each arc (i, j) in A and each possible position h of the arc in the tour we associate a cost c h ij . Clearly, formulations for the TDTSP can be used for the ATSP by simply considering c h ij = c ij for every arc (i, j) and every position h.

The paper by Godinho et al [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] provides one way of viewing the new model. We call it the time-dependent TSP point of view where it is put in evidence how to obtain the new model by tightening the linear programming relaxation of the Picard and Queyranne [START_REF] Picard | The Time-dependent Traveling salesman problem and its application to the tardiness in one-machine scheduling[END_REF] formulation. In this chapter, we will present the ATSP point of view and will show how to obtain the model by enhancing the subproblem arising in the standard multicommodity ow (MCF) model for the ATSP (see Wong [START_REF] Wong | Integer programming formulations of the traveling salesman problem[END_REF] and Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF]). These enhancements lead to a model with a linear programming relaxation that is tighter than the one produced by the MCF model but still weaker than the one given in Godinho et al. [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF]. Then, by using variable redenition and constraint disaggregation we make a bridge to the TDTSP, enhance the linear programming relaxation of the model and obtain the model of Godinho et al [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF]. Finally, we present further enhancements on the model and show that these enhancements have a natural interpretation in terms of constraints that arise in a dierent class of extended formulations for the ATSP, that is, formulations with precedence variables.

We will compare the linear programming relaxation of the new formulation with the linear programming relaxation of the three compact and non-dominated formulations presented in Oncan et al. [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF]. The three formulations are the one with the best linear programming relaxation presented in Fox et al. [START_REF] Fox | A N-Constrained formulation of the (Time-dependent) Traveling Salesman Problem[END_REF], the one with the best linear programming relaxation presented in Sherali and Driscoll [START_REF] Sherali | On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems[END_REF] as well as the one with the best linear programming relaxation presented in Sherali et al. [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF] which we denote respectively by FGG, SD and SST.

Gouveia and Voss [START_REF] Gouveia | A classication of formulations for the time-dependent Traveling Salesman Problem[END_REF] have shown that the linear programming relaxation of the Picard and Queyranne [START_REF] Picard | The Time-dependent Traveling salesman problem and its application to the tardiness in one-machine scheduling[END_REF] formulation, denoted by PQ in the remaining of the chapter, is known to strictly dominate the linear programming relaxation of the FGG formulation. Thus, we will show that the linear programming relaxation of the new model is at least as good as the linear programming relaxation of the PQ formulation. This is the topic of Section 3. Section 4 makes a short introduction to the SD model and provides a proof that the linear programming relaxation of the new model is at least as good. In these two cases, the new model provides much better bounds for many of the instances tested. We will show that there is no dominance relationship between the linear programming relaxations of the new model and the model SST. However, we will also show how to slightly enhance the new model in order to obtain a theoretical dominance. This comparison will be discussed in Section 5. Section 6 concludes the chapter and presents numerical results on the linear programming bounds from the dierent models for instances coming from the TSP-lib.

Flow based formulations

In this section we show how to develop the formulation described in Godinho et al. [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] from an ATSP point of view. In Section 2.1 we review a standard framework for presenting formulations for the ATSP. In the remaining sections we describe the several enhancement steps to obtain the new formulation from the multicommodity ow model.

A Generic Model

Consider the binary variables x ij indicating whether arc (i, j) is in the solution and the following generic formulation for the ATSP: minimize

(i,j)∈A c ij x ij subject to x = (x ij ) ∈ Assign (1)
{(i, j) :

x ij = 1} is connected (2)
with Assign denoting the feasible set of the assignment relaxation:

i∈V x ij = 1 for all j ∈ V (3) j∈V x ij = 1 for all i ∈ V (4)
x ij ∈ {0, 1} for all (i, j) ∈ A.

(

) 5
Many works on formulations for the ATSP start with this generic formulation and then describe dierent ways of expressing [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF]. The derived formulations may be classied into two classes: natural formulations and extended formulations. In the rst class, we include formulations that use only the design variables x ij and in the second class we include formulations that use linear inequalities on an extra set of variables to model the connectivity requirements. This second class may also be divided into sub-classes, according to the kind of extra variables used. In fact, in the next subsections we will review and introduce network ow based models based on paths, circuits and n-circuits, time-dependent network ow based models and we will establish a connection between these models with models using precedence variables.

Note that the denition of the variables in these models can lead to particular cases for the constraints where some terms do not appear (because they correspond to variables that are not dened). For each formulation, we will precise which variables are dened or not.

In the following we denote the linear programming relaxation of a given model P by P L and its linear programming bound by v(P L ). We will use the designation exact model for a model whose linear programming relaxation only has integral extreme points. We let F (P) denote the set of feasible solutions of an integer (linear) program P.

Path-based formulations

Constraints [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF] can be modelled by using extra variables to express the connectivity requirements.

For each node k ∈ V \ {1}, we dene path variables y k ij ((i, j) ∈ A, j = i and i = k) that indicate whether arc (i, j) is in the path from node 1 to node k. Let path(k) denote a path from node 1 to node k. Then, we can rewrite the non-explicit part (2) of the generic formulation as follows:

{(i, j) : y k ij = 1} contains a path(k) for all k ∈ V \ {1}, ( 6
)
y k ij ≤ x ij for all (i, j) ∈ A, j = 1, k ∈ V \ {1}, i = k. ( 7
)
We can represent the previous condition (6) on the variables y k ij as follows:

j∈V y k ij - j∈V y k ji =    1 i = 1 0 i = 1, k -1 i = k for all k ∈ V \ {1} (8) y k ij ∈ {0, 1} for all (i, j) ∈ A, j = 1, for all k ∈ V \ {1}, i = k. ( 9
)
By using this ow/path model together with [START_REF] Fox | A N-Constrained formulation of the (Time-dependent) Traveling Salesman Problem[END_REF] for replacing [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF] in the generic formulation, we obtain the standard multi-commodity ow formulation for the ATSP (see Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF]), which will be denoted by P-MCF in this chapter. One important remark for the proofs that will appear later on is that for the linear programming relaxation of the P-MCF model, constraints [START_REF] Fox | A N-Constrained formulation of the (Time-dependent) Traveling Salesman Problem[END_REF] are satised as equalities when k = j or when i = 1 (this follows easily from the constraints ( 8)-( 9) together with the assignment constraints on the x ij variables).

By using the max-ow min-cut theorem it is easy to show that the projection of the feasible set of the linear programming relaxation of the MCF model into the subset of the x ij variables is completely described by non-negativity variables on the x ij variables, (1) and the cut constraints

[i∈V \S,j∈S]
x ij ≥ 1 for all S ⊆ V \ {1} [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] Thus, if we use the constraints [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] to express (2) we obtain a natural formulation for the ATSP that, based on the previous projection result, provides the same linear programming bound as the P-MCF model.

Circuit-based formulations

One way of attempting to improve the linear programming relaxation of the models described in subsection 2.2 is to replace the concept of path(k) by the concept of circuit(k). Let circuit(k) denote a circuit starting and ending at node 1 and passing through node k only once. Consider the circuit variables g k ij that indicate whether arc (i, j) is in a circuit(k). In contrast to the P-MCF model, because the circuit passing through node k does not terminate at that node, the new models contain both the variables g k kj and g k i1 . Furthermore, since we are modeling a circuit, we can use equalities g k ij = x ij to relate the g k ij variables with the x ij variables.

Consider the generic formulation given as follows:

{(i, j) : g k ij = 1} contains a circuit(k) for all k ∈ V \ {1}, ( 11
)
g k ij = x ij for all (i, j) ∈ A, k ∈ V \ {1}. ( 12
)
It does not seem easy to model the non-explicit part [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] of the formulation with only the g k ij variables without allowing circuits disconnected from the depot. One alternative is to follow Wong [START_REF] Wong | Integer programming formulations of the traveling salesman problem[END_REF] and decompose the circuit subproblem into two path subproblems, for each k ∈ V \ {1}. Then, instead of using one set of circuit variables, we could use two sets of path variables yt k ij (t = 1, 2), one associated with the path from node 1 to node k and the other associated with the path from node k to node 1. The variables in the rst set, y1 k ij (i = k and j = 1), have the same interpretation as the variables in the previous set y k ij while the variables in the second set y2 k ij (j = k and i = 1) indicate whether arc (i, j) is in the path from node k to node 1. With these two sets of variables we can rewrite the non explicit part [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] as follows:

j∈V y1 k ij - j∈V y1 k ji =    1 i = 1 0 i = 1, k -1 i = k j∈V y2 k ij - j∈V y2 k ji =    1 i = k 0 i = 1, k -1 i = 1 (13) for all k ∈ V \ {1} y1 k ij + y2 k ij = g k ij for all (i, j) ∈ A, k ∈ V \ {1} (14) yt k ij ∈ {0, 1} for all (i, j) ∈ A, k ∈ V \ {1}, t = 1, 2. (15)
For each k ∈ V \ {1}, the constraints on the left-hand side ensure that there is a path from node 1 to node k. The constraints on the right-hand side ensure that there is a path from node k to node 1. Note also that the way the variables are dened guarantees that the cycle does not visit node k more than once. The coupling constraints y1 k ij + y2 k ij = g k ij guarantee that, for each k, an arc is used in the circuit passing through node k if and only if it is in the path fron node 1 to node k or in the path from node k to node 1. Note however, that feasible solutions to the system (13)- [START_REF] Gouveia | A classication of formulations for the time-dependent Traveling Salesman Problem[END_REF] allow circuits disconnected from the depot. These subcircuits will be not allowed when we consider all the dierent circuit(k) models together with the constraints involving the x ij variables.

We can obtain a formulation for the ATSP by using the previous system in the place of [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF].

We denote by 2P-MCF the formulation just dened. We note that by using [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Traveling Salesman Problem[END_REF] and the coupling constraints from the model above, we can eliminate the g k ij variables from the model. This formu- lation is exactly the formulation presented by Loulou [START_REF] Loulou | On multicomodity ow formulations for the TSP[END_REF] which, as shown in Langevin et al [START_REF] Langevin | Classication of traveling salesman formulations[END_REF] is also equivalent to the P-MCF formulation and other versions of the 2P-MCF model including the original version proposed by Wong [START_REF] Wong | Integer programming formulations of the traveling salesman problem[END_REF].

These results indicate that we have not gained anything by replacing the path subproblem by a circuit subproblem. In the next subsection we introduce models using the stronger subproblem where we add the condition the circuit has n arcs to circuit(k). Before, describing models based on this subproblem and as a sort of introduction to the next section, we consider the eect of adding the cardinality constraint

(i,j)∈A y1 k ij + (i,j)∈A y2 k ij = n ( 16
)
to the model ( 13)-( 15). The constraint states that the number of arcs used in any feasible solution to the model ( 13)-( 15) is equal to n. However, we observe that the inclusion of this constraint does not imply that the circuit starting and ending in node 1 has n arcs since any feasible solution to the model ( 13)-( 15) may have circuits disconnected from node 1. Thus, what the constraint guarantees is that the total number of arcs included in the circuit passing through node 1 and node k and eventually in any other disconnected circuits that may exist in the solution is equal to n.

A dierent observation is that the model ( 13)-( 15) is exact. This property is lost when the cardinality constraint ( 16) is added to the model.

A nal observation is that although the cardinality equality ( 16) tightens the set of feasible solutions of the model ( 13)-( 15), it does not tighten the linear programming relaxation of the whole 2P-MCF model. In fact, we can easily see that if for a xed j and a xed commodity k, we add the linking constraints y1 k ij + y2 k ij = x ij for i = 1, . . . , n and use the assignment constraints (3) for node j, we obtain i=1,...,n y1 k ij + i=1,...,n y2 k ij = 1 for the same j and k. Then, by adding the previous equality for all j = 1, . . . , n, we obtain the equality (16).

n-Circuit-based formulations

Godinho et al. [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] have suggested a formulation for the ATSP where the subproblem associated to each node k is a circuit(k) with exactly n arcs (which we will denote by n-circuit(k)). Consider the circuit variables g k ij that indicate whether arc (i, j) is in a n-circuit(k) (for simplicity we use the same variables as in the model described in the previous subsection).

Consider the generic formulation given as follows

{(i, j) : g k ij = 1} is a n-circuit(k) for all k ∈ V \ {1}, ( 17
)
g k ij = x ij for all (i, j) ∈ A, k ∈ V \ {1}. ( 18
)
As before, it does not seem easy to model the non-explicit part (17) of the formulation with only the g k ij variables. However, this subproblem can be solved as an unconstrained shortest path in appropriate graphs, as it has been done in Godinho et al. [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] and previously by Godinho et al. [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF]. The usual path equations for the unconstrained shortest path problem rewritten in these graphs give valid formulations for the n-circuit(k) subproblem. Since the graph used in Godinho et al [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] is more compact than the graph used in the previous Godinho et al [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] paper, it leads to a more compact formulation and for this reason we will describe it here and omit the previous formulation. The Godinho et al. [11] formulation is based on a two-layered hop-indexed graph.

The rst layer represents the path before node k while the second one describes the path after node k. The two layers are linked by several copies of node k, depending on its position in the path. Figure 1 illustrates the adequate graph for an instance on 5 nodes and for k = 4. The part below, designated by rst part of the circuit in the remaining of the text, models the path from node 1 to node k and the part above, designated by second part of the circuit in the remaining of the text, models the path from node k to node 1.

1 hk z 2 hk z 1 z , ( 1
, ) i j A j i k " # # 2 hk z , ( ,
1) i j A j k i " # #
A straightforward shortest path reformulation based on this two-layered graph provides a compact hop-indexed (time-dependent) model for the underlying n-circuit(k) subproblem for a given node k. We associate binary variables z1 hk ij (resp. binary variables z2 hk ij ) to the arcs of the sub- graph modeling a path in the rst part (resp. in the second part) of the circuit. That is, the variables z1 hk ij indicate whether the arc (i, j) ∈ A (j = 1, i = k) is in the h th position in the circuit from node 1 to node 1 passing through node k and is before node k. They are dened only on the following three cases:

1. h = 1, i = 1 and j ∈ V \ {1}, 2. h = 2, . . . , n -2, i ∈ V \ {1, k} and j ∈ V \ {1}, i = j, 3. h = n -1, i ∈ V \ {1, k}, and j = k.
The variables z2 hk ij indicate whether arc (i, j) ∈ A (j = k, i = 1) is in the h th position in the circuit, from node 1 to node 1 passing through node k and is after node k. They are dened only on the following cases:

1. h = 2, i = k and j ∈ V \ {1, k}, 2. h = 3, . . . , n -1, i ∈ V \ {1} and j ∈ V \ {1, k}, i = j, 3. h = n, i ∈ V \ {1}, and j = 1.
Using these variables, we can write the following new model for the n-circuit(k) subproblem [START_REF] Loulou | On multicomodity ow formulations for the TSP[END_REF] for a given k. As mentioned at the end of the introduction, the denition of the variables can lead to particular cases for the constraints where some terms do not appear (because they correspond to variables that are not dened).

j∈V \{1} z1 1k 1j (19) j∈V \{1} z1 h+1,k ij - j∈V ; j =k z1 hk ji = 0 for all i ∈ V \ {1}, i = k, h = 1, . . . , n -2 (20) j∈V ; j =k z2 h+1,k kj - j∈V ; j =k z1 hk jk = 0 for h = 1, . . . , n -1 (21) j∈V ; j =k z2 h+1,k ij - j∈V \{1} z2 hk ji = 0 for all i ∈ V \ {1}, i = k, h = 2, . . . , n -1 (22) g k ij = h=1,...,n (z1 hk ij + z2 hk ij ) for all (i, j) ∈ A ( 23
)
z1 hk ij ∈ {0, 1} for all (i, j) ∈ A, i = k, j = 1, h = 1, . . . , n -1 (24) z2 hk ij ∈ {0, 1} for all (i, j) ∈ A, i = 1, j = k, h = 2, . . . , n (25)
g k ij ∈ {0, 1} for all (i, j) ∈ A (26)
We can obtain a formulation for the ATSP by replacing [START_REF] Loulou | On multicomodity ow formulations for the TSP[END_REF] with this circuit formulation for each k. We let C-MCF denote this model. We note that when creating this model, constraints [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF] enable us to rewrite the linking constraints g k ij = x ij using only the z1 hk ij , z2 hk ij and x ij variables, and so we can eliminate the g k ij variables (and constraints ( 23)) from the model. The transformed linking constraints become as follows: h=1,...,n

(z1 hk ij + z2 hk ij ) = x ij for all (i, j) ∈ A, for all k ∈ V \ {1}.
For the sake of simplicity, we maintain the designation [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF] for these transformed equalities.

Since the model ( 19)- [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF] in the g k ij , z1 hk ij and z2 hk ij variables denes the path equations on the ex- panded network, its corresponding matrix is totally unimodular and we can conclude that its linear programming relaxation is integer. Since ( 19)-( 26) is integral and models a toughter subproblem than the subproblem modeled by ( 13)-( 15), we have

Propositon 2.1 v(C-MCF L ) ≥ v(2P-MCF L ).
We will show in Section 6 that the inequality can be strict for many instances.

Since v(2P-MCF L ) = v(P-MCF L ) this dominance also holds with respect to the original P-MCF model and equivalent formulations such as the one obtained by using the constraints [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] in place of [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF].

We observe that this model produces the same linear programming bound of a model presented in Godinho et al. [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF]. The equivalence simply follows from the fact that the latter model also uses an exact, although less compact, model for the the n-circuit(k) subproblem (17). Proposition 2.1 motivates the question of knowing which inequalities are implied by the linear programming relaxation of the C-MCF model in the space of the x ij variables. Clearly, constraints [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] are included in the class of projected inequalities. We can use the previously mentioned equivalence to a model in Godinho et al. [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] to give a partial answer to this question since some such new inequalities are already described in this paper. These inequalities, called double-jumps, are related to the jump inequalities introduced by Dahl [4] and correspond to a weaker version of the lifted cycle inequalities proposed by Balas and Fischetti [START_REF] Balas | On the monotonization of polyhedra[END_REF] which are known to be facet dening for the ATSP polytope. However, nding out what the remaining inequalities are seems to be much more dicult. The reason for this is the fact that hop-constrained path subproblems are included in the whole model and it is well known that nding the projection in the natural space of related polyhedra is not easy (see, for instance the paper by Dahl et al. [START_REF] Dahl | A note on hop-constrained walk polytopes[END_REF].)

Enhancing the C-MCF model (using time-dependent variables)

The model described in the previous section can be enhanced by using variable redenition and constraint disaggregation. Furthermore, with the idea suggested in this section we will make a bridge between the resulting enhanced formulation with time-dependent formulations for the ATSP (see next section).

Consider the binary variables z h ij for all (i, j) ∈ A and h = 1, . . . , n, indicating whether or not arc (i, j) ∈ A is in the h th position of the circuit. Note that when dening these variables we have i = 1 i h = 1 (the arc leaving node 1 is in position 1) and j = 1 i h = n (the arc entering the depot is in position n). The original arc variables and the time-dependent variables are related as follows:

h=1,...,n z h ij = x ij for all (i, j) ∈ A ( 27
)
Note that as before, we have special cases for these equalities depending on whether i = 1, j = 1 or i, j = 1. The interest of using these variables arises when we use the previous equality to rewrite [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF] as follows h=1,...,n

(z1 hk ij + z2 hk ij ) = h=1,...,n z h ij for all (i, j) ∈ A.
Until, now, we have not tightened the previous formulation. However, the previous equalities can be disaggregated into

z1 hk ij + z2 hk ij = z h ij for all (i, j) ∈ A, h = 1, . . . , n. ( 28
)
We denote by EC-MCF the model obtained from the model C-MCF by adding the constraints [START_REF] Wong | Integer programming formulations of the traveling salesman problem[END_REF] and by replacing ( 23) with (28) for all positions h. Clearly, we have that Propositon 2.2 v(EC-MCF L ) ≥ v(C-MCF L ).

We will show in Section 6 that the inequality can be strict for many instances (in fact, the improvements are substantial in most cases).

We can give an intuitive and dierent interpretation to the disaggregated equalities (28). In the previous subsections the emphasis on modelling was set on nding good formulations for the subproblems associated to each node k, each one seen as an independent subproblem -the subproblems are related to each other only through the linking constraints. However, when we analyse a solution for the ATSP we realize that there is a great deal of information regarding the way the sub-problems are related to each other and that might be used to derive improved formulations. In fact, what the disaggregated constraints are saying is that one arc (i, j) is the h th arc of the circuit associated to a given node k if and only if it is in the same position in the other n -2 circuits associated to nodes p ∈ V \ {1}, p = k.

Enhancing the C-MCF model (using precedence variables)

The enhancements described in this subsection can be viewed independently of the enhancements described in the previous one. Thus, they can be used either to strengthen the C-MCF model or even to strengthen the stronger EC-MCF model.

We start by presenting a new set of equalities that relate the two sets of variables z1 and z2.

Then, we will show that these equalities have a natural interpretation in terms of constraints that arise in a dierent class of extended formulations for the ATSP. Consider, the following equalities (29)

The validity of these equalities is easily explained by looking at Figure 1. What the equality states, for a given pair of nodes j and k, is that node j is in the rst part of the circuit through node k if and only if node k is in the second part of the circuit through node j. In fact this equality illustrates an idea explored in the previous subsection where information between dierent commodities is explored.

We present next an alternative motivation for these equalities. The motivation will be given in terms of extended formulations for the ATSP using binary precedence variables v k j indicating whether j is before k in the tour. As far as we know, the rst such model was proposed by Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF] leading to an enhanced version of the P-MCF model (see also Section 5). Later on, Gouveia

and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem and a Reformulation of the Miller-Tucker-Zemlin Constraints[END_REF] present several models which can be viewed as a disaggregation (and tightening) of the well known Miller-Tucker-Zemlin [START_REF] Miller | Integer programming formulations and traveling salesman problems[END_REF] model. Formulations using these variables were further explored in Gouveia and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem: on Generalisations of Disaggregated Miller-Tucker-Zemlin Constraints[END_REF], Sarin et al. [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints[END_REF], Sherali et al [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF], and Gouveia and Pesneau [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Traveling Salesman Problem[END_REF]. Oncan et al. [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF] compare the linear programming relaxation of most of these formulations.

It is easy to see that the precedence variables can be related to the variables used in our models either as

v k j = h=1,...,n-2 p∈V ; p =k z1 hk pj for all j, k ∈ V \ {1}, k = j (30)
or as

v k j = h=2,...,n-1 p∈V ; p =k z2 hj kp for all j, k ∈ V \ {1}, k = j (31)
Note that the equalities (29) are obtained by considering (30) together with (31). Let us assume, now, that we will use only (30) to relate the two sets of variables. We will show next that adding (31) (or equivalently, adding the equalities (29)) is equivalent to adding a well known set of equalities dened on the v k j variables, namely the equalities

v k j + v j k = 1 for all j, k ∈ V \ {1} (32)
which state that for any given pair of nodes, one is before the other in the tour. These equalities were rst used in the paper by Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF] and are also known from model of the linear ordering problem. As noted in the previous papers, the inclusion of these equalities lead to reasonable improvements on the lower bounds produced by most of the models using this type of variables.

To prove this equivalence (that is, that adding (31) to (30) is equivalent to adding the equalities (32) to (30)) we consider the equalities [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF] h=1,...,n

(z1 hk ij + z2 hk ij ) = x ij for all (i, j) ∈ A, for all k ∈ V \ {1}
from the C-MCF model. If we x nodes j and k and sum up for all i we obtain (the last equality follows from the assignment constraint (3) for node j) i∈V h=1,...,n

(z1 hk ij + z2 hk ij ) = i∈V x ij = 1 for all j, k ∈ V \ {1}
which can be rewritten as

v k j = i∈V h=1,...,n z1 hk ij = 1 - i∈V h=1,...,n z2 hk ij for all j, k ∈ V \ {1}.
Now, if (31) is valid then the right-hand side term of the previous equation becomes 1 -v j k and (32) holds. The reverse holds in a similar way and we can conclude that (31) is valid if and only if (32) is, and thus, we have given an interpretation to the equalities given at the beginning of this section in terms of the v k j variables. We denote by EC-MCF+ the model obtained by having (30) and (32) added to the EC-MCF model. Similarly, we denote by C-MCF+ the model obtained by adding the same constraints to the mdoel C-MCF. Our computational results will show that (30) and (32) are useful to produce further reductions on the gaps. Clearly, constraints (30) enable us to use many other inequalities that have been suggested in the referred papers using models with the v k j variables. One class of such inequalities will be discussed in Section 5.

3

Comparing with the Picard and Queyranne formulation

In this section we compare the linear programming relaxation of the EC-MCF model with the linear programming relaxation of the Picard and Queyranne [START_REF] Picard | The Time-dependent Traveling salesman problem and its application to the tardiness in one-machine scheduling[END_REF], PQ, formulation that is dened on the previously presented z h ij variables: minimize

(i,j)∈A c ij h=1,...,n z h ij h=1,...,n i∈V z h ij = 1 for all j ∈ V \ {1} (33) j∈V \{1} z 1 1j = 1 (34) i∈V z h ij = i∈V z h+1 ji for all j ∈ V \ {1}, h = 1, . . . , n -1 (35) z h ij ∈ {0, 1} for all (i, j) ∈ A, h = 1, . . . , n (36)
Constraints (33) guarantee that each node is visited exactly once. Constraints (35) state that an arc enters node j in position h if and only if another arc emanates from this node in position h + 1. Constraint (34) states that one arc leaves node 1 in position 1 (similar constraints stating that one arc enters node 1 in position n are not needed). Constraints (36) dene the domain of the variables.

In order to compare it with the models of the previous section we note that any integer solution for the model dened by ( 34)-( 36) is a circuit with n arcs in the original graph. Thus, the model can be rewritten as minimize

(i,j)∈A c ij h=1,...,n z h ij (33) and {(i, j) : z h ij = 1} denes a n-circuit.
Furthermore, the model dened by ( 34)-(36) corresponds to the path equations in a layered graph and thus, it is exact since the associated constraint matrix is totally unimodular. Thus, the PQ model is, in terms of linear programming bounds, the best model that can be built by using the generic formulation given above. Using the equations ( 27) that link the two sets of variables

y ij = h=2,...,n-1 (h -1)z h ij for all (i, j) ∈ A, i, j = 1 (49)
(these constraints do not improve the linear programming bound) and then showed that the linear programming relaxation of the PQ model augmented with (49) implies all the constraints in the linear programming relaxation of the SCF model.

The z h ij variables can be related with the u i variables in a similar way by using the following equalities:

u j = i∈V h=1,...,n-1 hz h ij for all j ∈ V \ {1} (50)
Again, the inclusion of (50) into PQ does not alter its LP bound. These two equalities enable us to relate the linear programming relaxations of the SD and PQ+ formulations. Based on the previous result mentioned in Gouveia and Voss [START_REF] Gouveia | A classication of formulations for the time-dependent Traveling Salesman Problem[END_REF] it is sucient to prove that Propositon 4.1 The linear programming relaxation of PQ+ implies the constraints (40), ( 42), ( 43) and (45).

Proof. Clearly, (45) is obvious. Consider the PQ+ model augmented with ( 49) and ( 50). We will show next that this augmented model implies constraints (40), ( 42) and (43).

1. Constraint (40) for a given node j ∈ V \ {1}.

Consider a given node j ∈ V \ {1} and the following trivial equality: i∈V h=1,...,n-1

hz h ij = i∈V \{1} h=2,...,n-1 hz h ij + z 1 1j
By extracting z 1 1j in (33) for node j and replacing its value in the previous expression, we obtain:

i∈V h=1,...,n-1

hz h ij = i∈V \{1} h=2,...,n-1 hz h ij + 1 - i∈V \{1} h=2,...,n-1 z h ij = i∈V \{1} h=2,...,n-1 (h -1)z h ij + 1.
Now, by using (49) on the right-hand side and (50) on the left-hand side we obtain (40) for the same node j.

2. Inequality (42) for a pair of nodes i, j ∈ V \ {1}.

(a) Lower bound:

u j + (n -2)x ij -(n -1)(1 -x ji ) ≤ y ij + y ji
Consider the inequalities (38) associated to arc (i, j) for h = 2, . . . , n -2:

z h ij ≤ p∈V \{i} z h+1 jp h = 2, . . . , n -2.
Multiplying by (n -h + 1) and summing up the resulting inequalities for h = 2, . . . , n -2, we obtain: h=2,...,n-2

(n-h-1)z h ij ≤ p∈V \{i} h=2,...,n-2 (n-(h+1))z h+1 jp = p∈V \{i} h=3,...,n-1 (n-h)z h jp
By considering (n -2)z 2 jp ≥ 0 for all p ∈ V \ {1, i} and observing that for h = n -1 we have (n -h -1)z h ij = 0, we obtain: h=2,...,n-1

(n -h -1)z h ij ≤ p∈V \{i} h=2,...,n-1 (n -h)z h jp . ( 51
)
Consider now the constraints (35) for node j:

p∈V z h pj = p∈V z h+1 jp h = 1, . . . , n -1.
Multiplying both sides by h and summing up the resulting equalities for h = 1, . . . , n -1,

we obtain:

p∈V h=1,...,n-1 hz h pj = p∈V h=1,...,n-1 hz h+1 jp = p∈V h=2,...,n (h -1)z h jp = p∈V h=2,...,n-1 (h -1)z h jp + (n -1)z n j1 = p∈V \{i} h=2,...,n-1 (h -1)z h jp + h=2,...,n-1 (h -1)z h ji + (n -1)z n j1 (52)
Now, adding (51) to (52) leads to: h=2,...,n-2

(n -h -1)z h ij + p∈V h=1,...,n-1 hz h jp ≤ p∈V \{i} h=2,...,n-1 (n -h + h -1)z h jp + h=2,...,n-1 (h -1)z h ji + (n -1)z n j1 . Now, since n -h -1 = n -2 -(h -1) we obtain: (n -2) h=2,...,n-2 z h ij + p∈V h=1,...,n-1 hz h jp -(n -1)
p∈V \{i} h=2,...,n-1

z h jp -(n -1)z n j1 ≤ h=2,...,n-1 (h -1)z h ij + h=2,...,n-1 (h -1)z h ji .
Now, by using (50) on the second term of the left-hand side, and using (49) on the terms on the right-hand side we obtain

(n -2) h=2,...,n-2 z h ij + u j -(n -1)   p∈V \{i} h=2,...,n-1 z h jp + z n j1   ≤ y ij + y ji .
Then, by using the constraints [START_REF] Wong | Integer programming formulations of the traveling salesman problem[END_REF] we have

(n -2)x ij + u j -(n -1)
p∈V \{i}

x pj ≤ y ij + y ji .

Finally, using the assignment constraints on the third term of the left-hand side leads to the desired inequality.

(b) Upper bound:

y ij + y ji ≤ u j -(1 -x ji ).
We rst note that by using (40) in the upper bounding expression of (42), we obtain

y ji ≤ p∈V \{1,i} y pj + x ji .
We prove, now, that the previous inequality is implied by the linear programming relaxation of PQ+. Consider constraints (38) associated to arc (j, i):

z h+1 ji ≤ p∈V \{i} z h pj h = 1, . . . , n -2.
Multiplying by (h-1) and adding the resulting inequalities for h = 1, . . . , n-2 we obtain:

h=2,...,n-1 (h -2)z h ji = h=1,...,n-2 (h -1)z h+1 ji ≤ p∈V \{i} h=2,...,n-1 (h -1)z h pj .
Since for h = 1, we have h -1 = 0, and by adding (n -2)z n-1 pj ≥ 0 for all p ∈ V \ {1, i},

we obtain: h=2,...,n-1 (h -1)z h ji - h=2,...,n-1 z h ji ≤ p∈V \{i} h=2,...,n-1 (h -1)z h pj .
Then, by using the constraints (49) and the ( 27) the result follows.

3. Inequality (43) for a given node j ∈ V \ {1}.

(a) Lower bound:

u j ≥ 1 + (1 -x 1j ) -(n -3)x j1 .
Since the z h ij variables are nonnegative, we have that i∈V \{1} h=2,...,n-2

(h -2)z h ij ≥ 0 .
Multiplying by 2 the equality (33) for node j and adding the resulting equality to the previous inequality, we obtain:

2 i∈V h=1,...,n-1 z h ij + i∈V \{1} h=2,...,n-2 (h -2)z h ij ≥ 2.
Next, by extracting the terms for h = 1 and h = n -1 of the rst summation, we obtain:

2z 1 1j + 2 i∈V \{1} h=2,...,n-2 z h ij + 2 i∈V \{1} z n-1 ij + i∈V \{1} h=2,...,n-2 (h -2)z h ij ≥ 2
which is equivalent to

2z 1 1j + 2 i∈V \{1} z n-1 ij + i∈V \{1} h=2,...,n-2 (2 + h -2)z h ij ≥ 2
which, in turn, is equivalent to

z 1 1j + ((n -1) -(n -3)) i∈V \{1} z n-1 ij + z 1 1j + i∈V \{1} h=2,...,n-2 hz h ij ≥ 2 and to (n -1) i∈V \{1} z n-1 ij + i∈V h=1,...,n-2 hz h ij ≥ 1 + (1 -z 1 1j ) + (n -3) i∈V \{1} z n-1 ij
and, nally, equivalent to i∈V h=1,...,n-1

hz h ij ≥ 1 + (1 -z 1 1j ) + (n -3) i∈V \{1} z n-1 ij .
Next, we use the inequalities (35) for h = n -1 and node j in the last term to obtain: i∈V h=1,...,n-1

hz h ij ≥ 1 + (1 -z 1 1j ) + (n -3)z n j1 .
Finally, we use the constraints (50) and ( 27) and the result follows.

(b) Upper bound:

u j ≤ (n -1) -(n -3)x 1j -(1 -x j1 ).
Since the z h ij variables are nonnegative, we have that i∈V \{1} h=2,...,n-2

(h + 1 -n)z h ij ≤ 0.
Multiplying by 2 the equality (33) for node j and adding the resulting equality to the previous inequality, we obtain:

i∈V h=1,...,n-1 2z h ij + i∈V \{1} h=2,...,n-1 (h + 1 -n)z h ij ≤ 2.
By extracting the term for h = 1 of the rst summation, we obtain:

i∈V \{1} h=2,...,n-1 2z h ij + 2z 1 1j + i∈V \{1} h=2,...,n-1 (h + 1 -n)z h ij ≤ 2
which can be written as

2z 1 1j + i∈V \{1} h=2,...,n-1 (2 + h + 1 -n)z h ij ≤ 2
and as

z 1 1j + i∈V \{1} h=2,...,n-1 hz h ij -(n -3) i∈V \{1} h=2,...,n-1 z h ij ≤ 2 -z 1 1j
and as i∈V h=1,...,n-1

hz h ij ≤ 2 -z 1 1j + (n -3) i∈V \{1} h=2,...,n-1 z h ij .
By using the constraints (49), ( 50) and ( 27) the previous inequality can be rewritten as

u j ≤ 2 -x 1j + (n -3) i∈V \{1}
x ij . Now, use the assignment constraints on the previous inequality to obtain:

u j ≤ 2 -x 1j + (n -3)(1 -x ij ) = 2 -x 1j + (n -3) -(n -3)x 1j = (n -1) -(n -3)x 1j -x 1j .
Since (1 -x j1 ) ≥ 0 and x 1j ≥ 0, we obtain the desired inequality.

Thus, we have just proved that Propositon 4.2 v(PQ+ L ) ≥ v(SD L ).

Combining this result with Proposition 3.2 we obtain Propositon 4.3 v(EC-MCF L ) ≥ v(SD L ).

5

Comparing with the Sherali, Sarin and Tsai Formulation

Several extended formulations for the ATSP that have been proposed in the literature use the binary precedence variables v k j indicating whether j is before k in the tour. As noted before, the rst such model was proposed by Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF] leading to an enhanced version of the P-MCF model (see below). However, this model uses the precedence variables as a mean to tighten the linear programming relaxation of the P-MCF model (in fact, from a strictly point of view, the precedence variables are not even needed since they are related to the ow variables by equalities; however, their inclusion make the model easier to read). As far as we know, the rst models that use the two sets of variables {x ij , v j i } alone to describe (2) of the generic formulation were proposed by Gouveia and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem and a Reformulation of the Miller-Tucker-Zemlin Constraints[END_REF]. These models can be viewed as a disaggregation (and tightening) of the Miller-Tucker-Zemlin model. Later on Gouveia and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem: on Generalisations of Disaggregated Miller-Tucker-Zemlin Constraints[END_REF], use the relation between ow variables of the P-MCF model and the v j i variables to strengthen the previous models as well as to strengthen the P-MCF model. Sarin et al. [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints[END_REF] improve the models of the earlier paper by including inequalities from the related linear ordering problem (see, section 2.6). Gouveia and Pesneau [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Traveling Salesman Problem[END_REF] strengthen these models by using several classes of exponential sized sets of constraints involving the two sets of variables. Max ow / min cut computations are used to separate constraints from these classes. Sherali et al [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF] present formulations for the ATSP that also use the three sets of variables y k ij , v j i and x ij (in this sense, they are similar to the models presented in Gouveia and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem: on Generalisations of Disaggregated Miller-Tucker-Zemlin Constraints[END_REF]). The formulations they use are again obtained by applying the Reformulation-Linearization Technique (RLT) of Sherali and Adams [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF][START_REF] Sherali | A Hierarchy of Relaxations and Convex Hull Characterizations for Mixed-integer Zero-one Programming Problems[END_REF]. However, they apply it to the strongest formulation with precedence variables that has been presented in Sarin et al [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints[END_REF]. Thus, the procedure starts with a formulation including the two sets of variables {x ij , v j i } and ends up with formulation using the same two sets plus the variables y k ij as dened in section 2.2 for the P-MCF model. The variables y k ij result from linearizing nonlinear terms arising in the reformulation linearization procedure (in this sense, the approach is similar to the approach used to derive the SD formulation described in the previous section where a formulation starting with two sets of variables {x ij , u i } leads to a formulation with three sets of variables). The main dierence with the formulations in Gouveia and Pires [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem: on Generalisations of Disaggregated Miller-Tucker-Zemlin Constraints[END_REF] which use the same sets of variables is that Sherali et al. [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF] use the linear ordering inequalities (which, as shown in Sarin et al. [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints[END_REF], were, in general, stronger than the ones used in [START_REF] Gouveia | The Asymmetric Traveling Salesman Problem: on Generalisations of Disaggregated Miller-Tucker-Zemlin Constraints[END_REF]).

Before presenting their model with the strongest linear programming relaxation, we note that Oncan et al. [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF] have related the linear programming relaxation of several of these formulations.

The part of their strongest model corresponding to (2) of the generic model given in subsection 2.1 is as follows:

j∈V \{1} y k ij - j∈V y k ji =    1 i = 1 0 i = 1, k -1 i = k for all k ∈ V \ {1} (62) y k ij ≤ x ij for all (i, j) ∈ A, j = 1, i = k (63) v j i = p∈V y j pi for all i, j ∈ V \ {1} (64) v j i + v i j = 1 for all i, j ∈ V \ {1} (65) y k ij ∈ {0, 1} for all (i, j) ∈ A, j = 1, for all k ∈ V \ {1}, i = k (66) v j i ∈ {0, 1} for all i, j ∈ V \ {1}. ( 67
)
First, note that as noted in Section 2.2, the constraints (63) are satised as equalities when k = j and when i = 1. Thus we will use them explicitly as

y k 1j = x 1j for all j, k ∈ V \ {1} (68) or y j ij = x ij for all (i, j) ∈ A, j = 1. (69)
Propositon 5.1 v(P-MCF+ L ) = v(W-SST L ).

Proof. We prove rst that v(P-MCF+ L ) ≥ v(W-SST L ). It is sucient to show that (53)-( 56) are redundant in the linear programming relaxation of P-MCF+.

Obtaining (53) -Consider the inequality (68) for a pair j, k ∈ V \ {1}, y k 1j = x 1j . By the non-negativity constraints of the y k ij variables we obtain: p∈V \{1,k}

y k pj + y k 1j ≥ x 1j
Now use constraint (64) on the left-hand side to obtain (53) for the same pair j, k.

Obtaining (54) -Let i, k ∈ V \ {1}. By adding constraint (63) for j = 2, . . . , n, j = i, we obtain:

j∈V \{1} y k ij ≤ j∈V \{1}
x ij .

Using (62) for j = 1, k in the previous constraint we obtain

j∈V y k ji ≤ j∈V \{1}
x ij .

By using (64) on the previous inequality, we obtain:

v k i ≤ j∈V \{1}
x ij . Now, by using the assignment constraints (4) associated to node i, and rewriting we have

v k i ≤ 1 -x i1 .
By using (65) we obtain nally (54) for the same pair of nodes.

Obtaining (55) and (56) -Let i, j ∈ V \ {1} and consider constraint (64) for this pair of nodes v j i = p∈V y j pi .

Observe that by extracting the term for p = 1 from the summation and using (68), we obtain (55) for the same pair of nodes.

On the other hand by using (62) with (64), we obtain

v j i = p∈V \{1} y j ip .
Extracting the term for p = j from the summation and using (69), we obtain (56) for the same pair of nodes.

And thus (53)-( 56) are implied by the linear programming relaxation of the P-MCF+ model.

We prove now that v(P-MCF+ L ) ≤ v(W-SST L ). It is sucient to show that (62), ( 64), ( 68) and ( 69) are redundant in the linear programming relaxation of W-SST.

First, we note that the W-SST model does not include variables y k 1j for all j, k ∈ V \ {1} and variables y j ij for all (i, j) ∈ A, i, j = 1. Thus we introduce those variables in the model and we relate them to variables x ij as follows:

y k 1j = x 1j for all j, k ∈ V \ {1} and y j ij = x ij for all (i, j) ∈ A, j = 1.
and obtaining, respectively (68) and (69). Note that in the context of W-SST, these two sets of equalities only dene the new variables and do not modify its linear programming bound.

Obtaining (64) -Let i, j ∈ V \ {1} and consider constraint (55). By using (68) in (55), we obtain (64) for the same pair of nodes.

Obtaining (62) -Let i, k ∈ V \ {1}. By using (69) in (56) we obtain

v j i = p∈V \{1,j} y j ip + y j ij = p∈V \{1} y j ip
Combining with (64) we obtain constraint (62) for i ∈ V \ {1, k}. By considering a given node k ∈ V \ {1} and summing up equality (68) for all j ∈ V \ {1}, we obtain:

j∈V \{1} y k 1j = j∈V \{1}
x 1j .

Using the assignment constraint for node 1 on the right-hand side, we obtain (62) for i = 1.

Finally, by summing up equality (69) for all j ∈ V \ {1}, we obtain:

j∈V \{1} y k jk = j∈V \{1}
x jk .

Adding equality (68) written for node k to the previous equality, we obtain:

j∈V y k jk = j∈V x jk .
Using the assignment constraint on the right-hand side, we obtain (62) for i = k.

) ≥ v(W-SST L ). Propositon 5.3 v(C-MCF+ L ) ≥ v(W-SST L ).
Clearly, if we use (59) in the two models EC-MCF+ and C-MCF+, (let us denote by EC-MCF++ and C-MCF++ the two models obtained in this way) we obtain the stronger results

Propositon 5.4 v(EC-MCF++

L ) ≥ v(SST L ). Propositon 5.5 v(C-MCF++ L ) ≥ v(SST L ).

Computational Results and Conclusions

In this section we empirically evaluate the quality of the lower bounds given by the models discussed in the previous sections. As noted before, in this chapter we are concerned with the strength of the linear programming relaxations and not with the time needed to solve it or the corresponding integer program. For comparing the models, we use the known ATSP instances taken from TSP Lib (http://comopt.ifi.uni-heidelberg.de/software/TSPLIB95/).

In this chapter we compare the linear programming relaxation of the following models: SD, PQ+, P-MCF, P-MCF+, SST, EC-MCF and EC-MCF+. The linear programming relaxations where solved with the barrier solver CPLEX 12.

The next table gives the linear programming relaxation gaps of these models. The gaps are computed as [(Optimal Value -v(P L ))/Optimal value] * 100 (where P denotes the model) for each instance.

Several comments are interesting. First, the results obtained from our computational experiment show that the EC-MCF+ model produces, as far as we know, the best gaps produced by known compact models, for the reported instances.

Second, it is also worth to compare the eect of the linear ordering equalities LO1 in the P-MCF model (leading to P-MCF+ which is one of the models presented by Claus) and in EC-MCF (leading to EC-MCF+). We can conclude that these equalities lead to reasonable improvements when added either to the P-MCF or EC-MCF model. In particular in the later case, they lead to the best bounds.

Third, it is interesting to analyze the eect of adding the lifted 3-cycle inequalities (59) in the models. The addition of (59) to the model P-MCF+ results in the SST model and thus, as can be seen in Table 1, leads to some improvements. Adding, (59) to EC-MCF+ also may lead to further reduction on the gaps, for instance, for ftv35, the addition of these constraints to EC-MCF+ leads to a gap of 0.17 which is a reduction of more than 50% of the gap obtained without including these constraints). However, the EC-MCF+ model with constraints (59) is dicult to use for larger instances.

We also note that the gaps from SD and PQ+ have been included only for the sake of completeness, however, they are substantially weaker than the gaps given by the other formulations.

In terms of comparing ideas from these formulations, it is worth noting the two parallel and dierent strategic approaches leading to SST and to EC-MCF: 2. the one leading to the EC-MCF and EC-MCF+ models that can be seen as moving from a path subproblem to a n-circuit subproblem combined with the disaggregation specied in section 2.3 (or alternatively, moving from a path subproblem to a n-circuit subproblem in the space of the time-dependent variables as originally done in Godinho et al [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF]).

It is also interesting to note that both approaches are also very relevant (or even more relevant)

for versions of the ATSP that capture information given by the extra variables. As shown in Godinho et al [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF], the approach 2. leads to very tight models for the time-dependent TSP and the cumulative TSP. As shown in Sarin et al. [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints[END_REF] and Gouveia and Pesneau [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Traveling Salesman Problem[END_REF], approach 1. leads to tight models for the Precedence Constrained TSP problem. Furthermore, Gouveia and Pesneau [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Traveling Salesman Problem[END_REF] also propose several ideas worth exploring in order to strengthen this class of models. Finally, equalities (30) also enable us to use the models of approach 2. for Precedence Constrained TSP.

We conclude this chapter by presenting a table which gives a relative relation of the strength of the linear programming relaxations of the relevant models mentioned in this chapter. We have also contextualized this table in terms of the one from Oncan et al [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF] taking from here the relevant models for the new comparison.

Figure 2 . 1 -

 21 Figure 2.1 -A two-layered graph modeling a 5-circuit(4).

Figure 1 :

 1 Figure 1: A two-layered graph modeling a 5-circuit(4).

  h=1,...,n p∈V ; p =k z1 hk pj = h=1,...,n p∈V ; p =k z2 hj kp for all j, k = 2, . . . , n, k = j.

Figure 6 . 1 -

 61 Figure 6.1 -Relative strength of the corresponding linear programming relaxations

Figure 2 :

 2 Figure 2: Relative strength of the corresponding linear programming relaxations

Table 1 :

 1 Results for ATSP instances.

	And thus (62), (64), (68) and (69) are implied by the linear programming relaxation of the
	W-SST model.

* Supported by FCT research project [MATH-LVT-Lisboa-152] † Supported by FCT research project [MATH-LVT-Lisboa-152] ‡ Supported by the ANR project number ANR-09-blan-0373-01

x ij and z h ij , the variables x ij can be eliminated from the EC-MCF model (described in Section 2.3) leading to the following model (for simplicity, we skip this derivation from this chapter): minimize (i,j)∈A c ij h=1,...,n z h ij (33) and {(i, j) : g hk ij = 1} denes a n-circuit(k) for all k ∈ V \ {1} [START_REF] Loulou | On multicomodity ow formulations for the TSP[END_REF] z h ij = g hk ij for all (i, j) ∈ A, h = 1, . . . , n, k ∈ V \ {1} (37) z h ij ∈ {0, 1} for all (i, j) ∈ A, h = 1, . . . , n

where the constraints in ( 17) are ( 19)- [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF] and constraints (37) are a disaggregation of the constraints [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF]. In fact, the new model presented in Godinho et al. [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF] was given in this form.

Consider, now, a weaker version of this model, where we consider [START_REF] Loulou | On multicomodity ow formulations for the TSP[END_REF] only for a given single k ∈ V \ {1}. The fact that the system ( 19)-( 26) is exact and the relationship between the two subproblems enables us to show that the linear programming bound of this reduced model is at least as good as the linear programming bound of the PQ model. Thus, we have just shown that

Note that this result has already been proved in dierent way in Godinho et al. [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF]. We will show in Section 6 that the inequality can be strict for many instances. In Godinho et al. [START_REF] Godinho | Natural and Extended formulations for the Time-Dependent Traveling Salesman Problem[END_REF], the authors have given a complete description of the projection of F (EC-MCF L ) into the space of the z h ij variables. This description includes a large set of cut-like inequalities dened in an appropriate layered graph. In particular, and with relevance for the follow-up of this chapter, we consider the following particular cases

These constraints simply state that if arc (k, p) is in the solution in position h, then the arc in position h + 1 cannot go to node k. As far as we know, these constraints were rst proposed in the context of tree problems, see Gouveia [START_REF] Gouveia | Using Hop-Indexed Models for Constrained Spanning and Steiner Tree Problems Telecommunications Network Planning[END_REF], and later on in Costa et al. [START_REF] Costa | Models and Branch-and-Cut Algorithms for the Steiner Tree Problem with Revenues, Budget and Hop Constraints[END_REF]. We denote by PQ+ the PQ model augmented with these inequalities. This model will be relevant for the dominance proof of the next section and we also have that Propositon 3.2 v(EC-MCF L ) ≥ v(PQ+ L ).

4

Comparing with the Sherali and Driscol Formulation One of the earliest ideas for obtaining an extended formulation for the ATSP is to use additional variables u i representing the position of node i ∈ V with the generic meaning that u j = u i + 1 whenever x ij = 1. In this way subtours are prevented. Adding constraints stating this condition to the assignment relaxation (3), ( 4) and ( 5) guarantees the extra constraints (2) since it is well known that the condition (2) is equivalent to {(i, j) : x ij = 1} does not contain subtours. Miller, Tucker

and Zemlin [START_REF] Miller | Integer programming formulations and traveling salesman problems[END_REF] proposed a well known set of linear constraints with the intended interpretation.

Later on Desrochers and Laporte [START_REF] Desrochers | Improvements to the Miller-Tucker-Zemlin subtour elimination constraints[END_REF] have shown how to strengthen these inequalities, obtaining models with a tighter linear programming relaxation.

The development of the formulation given by Sherali and Driscoll [START_REF] Sherali | On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems[END_REF] starts with a similar framework. However, they consider rst a set of non-linear equalities in order to guarantee the previously stated condition u j = u i + 1 whenever x ij = 1. Then, they apply a specialized version of the Reformulation-Linearization Technique (RLT) of Sherali and Adams [START_REF] Sherali | A Hierarchy of Relaxations Between the Continuous and Convex Hull Representations for Zero-One Programming Problems[END_REF][START_REF] Sherali | A Hierarchy of Relaxations and Convex Hull Characterizations for Mixed-integer Zero-one Programming Problems[END_REF] to this nonstandard restatement of the Miller-Tucker-Zemlin constraints [START_REF] Miller | Integer programming formulations and traveling salesman problems[END_REF]. After introducing new variables to linearize non-linear terms, and after some constraint manipulation they obtain a model using the same u i variables and new variables y ij representing the position of arc (i, j) ∈ A in the circuit. As it is assumed that the circuit starts on node 1, we have u 1 = 0 and y 1j = 0 for any arc (1, j). The constraints in the SD model corresponding to (2) are given by j∈V \{1}

In this section we compare the linear programming relaxation of the EC-MCF model with the linear programming relaxation of the Sherali and Driscol [START_REF] Sherali | On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems[END_REF] formulation, SD for short. More precisely we will show the stronger result that the linear programming relaxation of the PQ+ formulation (that is the PQ formulation plus inequalities (38)) dominates the linear programming relaxation of the SD model. Then, using the results from the previous section we conclude that the linear programming relaxation of the EC-MCF model dominates the linear programming relaxation of the SD model.

Oncan et al. [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF] have shown that the linear programming relaxation of the SD model implies the linear programming relaxation of single commodity ow (SCF) model proposed by Gavish and Graves [START_REF] Gavish | The traveling salesman problem and related problems[END_REF]. Here, we elaborate more on this relation by rewriting the SD model as the SCF model augmented with extra constraints. In fact, by combining (39) with (40) and introducing the variables y j1 such that y j1 = (n -1)x j1 for all j ∈ V \ {1}, the SD model can be rewritten as follows

Observe that the constraints (46)-( 48) and ( 44) dene the SCF model. Thus, as stated above, we can view the SD model as the SCF augmented with constraints (40), ( 42), ( 43) and (45).

The interest of viewing the SD model in this way is due to a result in Gouveia and Voss [START_REF] Gouveia | A classication of formulations for the time-dependent Traveling Salesman Problem[END_REF] where it is shown that the linear programming relaxation of the PQ model dominates linear programming relaxation of the SCF model. More precisely, Gouveia and Voss have added the following constraints to the PQ model:

x 1i + p∈V \{1,j}

p∈V \{1,j}

In this section we compare the linear programming relaxation of the EC-MCF+ model with the linear programming relaxation of the Sherali, Sarin and Tsai [START_REF] Sherali | A class of lifted path and ow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF] formulation, SST for short. We will rst consider a variant of the SST that is obtained by removing one set of constraints from the SST model namely the constraints (59) (we will denote this variant by W-SST). The constraints (59) belong to the class of constraints mentioned at the end of section 2.6. As far as we know, they were rst proposed by Letchford (see also Sarin et al. [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Traveling Salesman Problem with and without Precedence Constraints[END_REF] and Gouveia and Pesneau [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Traveling Salesman Problem[END_REF]). These inequalities are a lifted version (obtained by considering the extra term +x ji on the left-hand side) of the 3-cycle inequalities known from the linear ordering polytope.

We will show that:

1. The linear programming relaxation of the W-SST model is equivalent to the linear programming relaxation of an enhanced version of the P-MCF model which has already been presented by Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF]. For this reason we will denote this variant by P-MCF+. 4. Then, we will reintroduce the missing constraints in SST. In particular we point out that by adding these missing constraints to EC-MCF+ or to the C-MCF+ model we will obtain a strict dominance over SST. And, we will make some comments about the eect of using computationally these constraints in the SST and in the EC-MCF+ models. In particular we will point out that these constraints are very eective in SST but are not in EC-MCF+ (although they are not dominated).

Consider the P-MCF model presented in section 2.2. Claus [START_REF] Claus | A new formulation for the traveling salesman problem[END_REF] has introduced an enhanced version of this formulation by adding constraints linking the y k ij and v j i variables and by adding the linear ordering equalities (32) discussed in subsection 2.6 (for simplicity, we will relabel the equalities). As noted before, we denote by P-MCF+ model this enhanced version.