Ma Yue

Shen Yuming

Sui Yuefei

Cao Cungen

The description logic for relational databases 1

Keywords: Relational database, Description logic, Translation

Description logics are widely used to express structured data and provide reasoning facility to query and integrate data from different databases. This paper presents a many-sorted description logic MDL to represent relational databases. We give a translation from relational databases to the description logic MDL, and show this translation completely and faithfully captures the information in the relational database. Moreover, we show that some relational algebra operations could be expressed in MDL.

Introduction

The Relational model is an important theoretic model of database management system. In a relational database, data are manipulated as a collection of relations or tables. In addition, a relational database provides a collection of methods to access the data in tables, and to modify and combine tables by using a set of relational algebra operations.

Description logic is a logic-based formalism of knowledge, focusing on concepts, individuals, roles, and the relationship between them. It is a proper choice to represent relational databases in DL, using its reasoning facility to implement the query of the information in databases, and to integrate different sources of data. There are many papers on represent structured databases in DL. Calvanese et al. [START_REF] Borgida | Description logics for data bases[END_REF] proposed a translation from ER-model to a description logic DLR. In this translation, tuple entities are implemented as constants in the model of DLR and the sets of entities are regarded as concepts. Moreover, the values of attributes are also described as constants, and there are concepts for attribute values. Unfortunately, in DLR these two kind of concepts could not be syntactically distinguished. There should be statements in DLR with form "an attribute value a is an instance of entity-concept R", which is meaningless in the corresponding databases.

Similar to Calvanese's work, we describe both the sets of attribute values and the sets of tuples in a relational database as concepts in DL. To distinguish these two kind of objects, we propose a many-sorted description logic MDL, in which the constants of attribute value and the constants of tuples are taken as different types of constant symbols. Similarly, we use different types of concept names representing concepts for attribute values and tuples. Based on the definition of MDL, we shall present a translation to represent a relational database in MDL: from a given database, we construct an MDL model and a knowledge base containing MDL statements which are satisfied in the MDL model. We will show that this translation completely and faithfully captures the information in the relational database. Moreover, we show that some relational algebra operations could be expressed in MDL using concept and role constructors.

This paper is organized as follows: in section 2 we give a brief introduction on relational databases and description logics; in section 3 we propose a manysorted description logic MDL, and give its formal definitions ; in section 4 we present the translation from relational database to MDL, and express relational algebra operations in MDL; in the last section we conclude the paper.

Preliminaries

This section will give the basic definitions on relational databases and description logics. The relational model is an important theoretic model of database management system. We present a brief formal definitions in relational database and relational algebra [START_REF] Simovici | Relational Database Systems[END_REF][START_REF] Kanellakis | Elements of relational database theory[END_REF]. Let U be a set of attributes called an universe. For each attribute A ∈ U , we assign a set of values dom(A) called the domain of A. Let dom = A∈U dom(A). Definition A relation schema R on U is a subset of U . A database schema D is a set of relation schema. Definition Let D = {R 1 , ...R n } be a database schema, R be a relation in D, and X be a set of attributes in U . An X-tuple t is a mapping from X to dom, such that for each A ∈ X, t(A) ∈ dom(A). A relation r over relation schema R is a finite set of R-tuples. A database d over database schema D is a set of relations {r 1 , ..., r n }, each r i is a relation over R i . We use α(r) to denote the set of attributes of r. Given a database d = {r 1 , ..., r n }, each r i ∈ {r 1 , ..., r n } is an atomic relation in d.

Based on the definition of tuples and relations, we now give the definition of the relational algebra. The relational algebra is an algebra on the set of relations, including several primitive operations on relations. We give the formal definitions of these operations as follows:

Definition Let t be an X-tuple and Y ⊆ X. The projection of tuple t on Y , denoted t[Y ], is the restriction of t on Y . Given relations r 1 , r 2 and a set of attributes Y , let α(r 1 ) = X 1 , α(r 2 ) = X 2 , • the projection of r 1 on Y , denoted π Y (r 1 ), fulfills: i) π Y (r 1 ) is defined if Y ⊆ X 1 . If π Y (r 1 ) is defined, α(π Y (r 1 )) = Y , ii) π Y (r 1 ) = {t[Y ]|t ∈ r 1 }. • the natural join of r 1 , r 2 , denoted r 1 r 2 , fulfills: i) α(r 1 r 2 ) = X 1 ∪ X 2 , ii) r 1 r 2 = {t|t is X 1 ∪ X 2 -tuple, such that t[X 1 ] ∈ r 1 , t[X 2 ] ∈ r 2 }. • the union of r 1 , r 2 , denoted r 1 ∪ r 2 , fulfills: i) r 1 ∪ r 2 is defined if X 1 = X 2 . If r 1 ∪ r 2 is defined, α(r 1 ∪ r 2 ) = X 1 , ii) r 1 ∪ r 2 = {t|t ∈ r 1 or t ∈ r 2 }. • the difference of r 1 , r 2 , denoted r 1 -r 2 , fulfills: i) r 1 -r 2 is defined if X 1 = X 2 . If r 1 -r 2 is defined, α(r 1 -r 2 ) = X 1 , ii) r 1 -r 2 = {t|t ∈ r 1 and t / ∈ r 2 }. • the renaming of r 1 from A to B, denoted ρ B|A (r 1 ), fulfills: i) ρ B|A (r 1 ) is defined if A ∈ X 1 , B / ∈ X 1 . If ρ B|A (r 1 ) is defined, α(ρ B|A (r 1 )) = X 1 -{A} ∪ {B}, ii) ρ B|A (r 1 ) = {t| there exists t ∈ r 1 such that t [A] = t[B], t [X 1 -{A}] = t[X 1 -{A}]}. • the selection on r 1 by ϕ , denoted θ ϕ (r 1 ), fulfills: i) ϕ has the form A = B|A = v|A op v, where A, B are attributes in α(r 1 ), v ∈ dom(A), op is a binary relation over dom(A). ii) α(θ ϕ (r 1 )) = X 1 , θ ϕ (r 1 ) = {t|ϕ is satisfied on t}.
From above we give the basic notions of relational database and relational algebra. Now we present a basic introduction of description logic. Description logic is a logic-based formalism for knowledge representing, focusing on describe individual, concept, role and the relationship between them. We give formal definition of a simple description logic ALC. Definition (syntax and semantics of ALC) The language L ALC for ALC contains the following primitive symbols:

• object names c 0 , c 1 , ...;

• concept names , C 0 , C 1 , ...;

• role names r 0 , r 1 , ...; The interpretation of concepts are defined as follows:

•
I = ∆; C I = I(C); (¬C) I = ∆ -C I ; (C D) I = C I ∩ D I ; (∃r.C) I = {x : Ey ∈ ∆((x, y) ∈ r I &y ∈ C I )}; • relation concept names R , R 0 , R 1 , ...; • value concept names V , V 0 , V 1 ,
(iv) V(v), R(t), a(t, v), op(v 1 , v 2 ), V W, R S, ¬ϕ, ϕ → ψ are statements.

Definition (semantics of MDL)

A model M is a tuple (∆, Σ, I) where ∆, Σ are non-empty sets such that ∆ ∩ Σ = ∅ and I is an interpretation such that for each relation concept name R, R I ⊆ ∆; for each value concept name V, V I ⊆ Σ; for each attribute role name a, a I ⊆ ∆ × Σ; for each value role name op, op I ⊆ ∆ × ∆; for each tuple constant name t, t I ∈ ∆ and for each value constant name v, v I ∈ Σ;

The interpretation of concepts and roles are defined as follows:

I R = ∆; I V = Σ; (¬R) I = ∆ -R I ; (R S) I = R I ∩ S I ; (¬V) I = Σ -V I ; (V W) I = V I ∩ W I ; (∃a.V) I = {x|exists y ∈ Σ, (x, y) ∈ a I &y ∈ V I }; (∃op.V) I = {x|exists y ∈ Σ, (x, y) ∈ op I &y ∈ V I }; ({v 0 , ...., v n }) I = {x|x = v I i for some i}; (¬a) I = ∆ × Σ -a I ; (a b) I = a I ∩ b I ;
The satisfaction of statements are defined as follows:

M |= R(t) iff t I ∈ R I ; M |= V(v) iff v I ∈ V I ; M |= a(t, v) iff (t I , v I ) ∈ a I ; M |= p(v 1 , v 2 ) iff (v 1 I , v 2 I ) ∈ p I ; M |= R S iff R I ⊆ S I ; M |= ¬ϕ iff M |= ϕ; M |= ϕ → ψ iff M |= ϕ ⇒ M |= ψ.

Represent information from relational databases in MDL

Based on the formal definition of MDL, We now present a translation σ from relational database to MDL, which could be divided into syntactical and semantical parts: given a database d, the syntactical part of σ translate d to a collection of MDL statements KB(d); the semantical part of σ translate d to an MDL model σ(d).

Definition (syntactical part of σ)

Given a database d = {r 1 , ..., r n }, for each tuple t ∈ ∪r i , the MDL sublanguage L d for d includes a corresponding tuple constant name t. Similarly, for each attribute value v, attribute name A, binary relation op and relation r i ; we have v as value constant, a as attribute role, R i as relation concept and op as value role in L d respectively. In addition, for each attribute A, we have D A as a value concept, denotes the concept containing values in the domain of A. For a relation r in database, we use σ(r) to denote the corresponding tuple concept in MDL; if r is the atomic relation in the original database, then σ(r) = R.

We construct KB(d) as follows:

• For each relation r ∈ d and tuple t such that t ∈ r i in relational database, the MDL statement R i (t) ∈ KB(d);

• For each tuple t, attribute value v and attribute A such that t

(A) = v, a(t, v) ∈ KB(d) and D A (v) ∈ KB(d); • For each relation r ∈ d such that α(r) = {A 1 , ..., A n } and U -α(r) = {B 1 , ..., B m }, R i ∃a 1 .D A 1 ... ∃a n .D A n ¬∃b 1 .D B 1 ... ¬∃b m .D B m ∈ KB(d).
From the definition of KB(d), we know that all the information about how tuples belong to relations and which value associated as an attribute value of a tuple, are translated into KB(d), KB(d) captures the complete static information of a relational database.

Definition (semantical part of σ)

Given a database d = {r 1 , ..., r n }, we construct an MDL model σ(d) = (∆, Σ, I), such that:

• ∆ = 1≤i≤n r i ,
that is, for each tuple t in database, t is an element of the domain of σ(d);

• Σ = 1≤i≤n A∈α(r i ) dom(A), including all the attribute value in the database;

• I is the interpretation fulfills:

• for each tuple constant t, I(t) = t, t is the corresponding tuple in relational database;

• for each value constant v, I(v) = v; • for each tuple concept R, I(R) = r; • for each attribute role a, I(a) = {(t, v)|t(A) = v} • for value concept D A , I(D A ) = dom(A); • for each value role op, I(op) = {(v 1 , v 2 )|v 1 op v 2 }.
The translation σ is faithful, that is, all the statements in KB(d) are satisfied in the MDL model σ(d). Formally, we have following theorem: Theorem For each ϕ ∈ KB(d), σ(d) |= ϕ. Proof. By induction on the construction of MDL statements, the detailed proof is omitted here.

The theorem above shows that we could use MDL to express the static information of a relational database. We now show some relational algebra operations could also be represented in MDL.

Firstly, we consider the set-theoretic operations: union ∪ and difference -. Let r 1 , r 2 be relations in relational database, and R 1 , R 2 be the corresponding tuple concept in MDL. Use the concept constructor , we obtain the tuple concept R 1 R 2 . It is straightforward to show the relation r 1 ∪ r 2 is the corresponding relation of tuple concept ¬(¬R 1 ¬R 2 ). Formally we have following proposition:

Proposition σ(r 1 ∪ r 2 ) = ¬(¬R 1 ¬R 2 ) . That is, if a tuple t is in relation r 1 ∪ r 2 , then (¬(¬R 1 ¬R 2 ))(t) ∈ KB(d), σ(d) |= (¬(¬R 1 ¬R 2 ))(t).
Similarly, we have the following proposition:

Proposition σ(r 1 -r 2 ) = R 1 ¬R 2 .

Note that the above proposition is satisfied only if

α(r 1 ) = α(r 2 ). If α(r 1 ) = α(r 2 ), the relation r 1 -r 2 is undefined, while R 1 ¬R 2 ≡ R 1 .
Besides of set-theoretic operations, the selection of relations could also be expressed in MDL. Given a relation r, an attribute A ∈ α(r) and a value v ∈ dom(A), we consider θ A=v (r). Using enumerate constructor {} of concept, we could obtain {v} as a singleton concept of value. It is easy to show the concept ∃a.{v} corresponds to the set of tuple in relational database, whose element has value v of attribute A. According to the definition of selection operator, R (∃a.{v}) is the concept corresponding to θ A=v (r). We could construct concepts for θ A op v and θ A=B in a similar way. We have following proposition: Proposition Selection operation could be expressed in MDL as follows:

σ(θ A=v (r)) = R (∃a.{v}); σ(θ A op v (r)) = R (∃a.(∃op.{v})); σ(θ A=B (r)) = R (∃(a b).D A ).
Notice that the set-theoretical operationa and selection are closed to the set of tuples in the original database. That is, there will be no new tuples due to these operations. We now consider the join operation. Given relations r 1 , r 2 , tuples in r 1 r 2 are differs from those tuples from the original relations r 1 , r 2 : the attribute set of r 1 r 2 is α(r 1 ) ∪ α(r 2 ). Since the domain ∆ of tuple only includes tuples which are from the original database, We cannot express the new tuple gained from join operation, like t ∈ r 1 r 2 . Similarly, the rename and projection operations are not closed to tuples. That means without making any extension to MDL, we cannot express these operations.

Conclusion

In this paper we present a many-sorted description logic MDL for relational databases. Based on MDL, we present a translation σ from relational database to MDL, which could be divided into syntactical and semantical parts: given a database d, the syntactical part of σ translate d to a collection of MDL statements KB(d); the semantical part of σ translate d to an MDL model σ(d). This translation is faithful, which means all the static information of tuples, relations and attribute values in database could be expressed in MDL. In addition, we show some relational algebra operations could be expressed in MDL as concepts.

  concept constructors: ¬, , ∃; • the subsumption relation: ; and • logical connectives: ¬, → . All the concept names and are atomic concepts; If C and D are concepts, c, d are object names, ϕ and ψ are statements, and r is a role name, then (i) ¬C, C D, C D, ∃r.C, ∀r.C are concepts; (ii) C(c), r(c, d), C D, ¬ϕ, ϕ → ψ are statements. A model M is a pair (∆, I) such that ∆ is a non-empty set, and I is an interpretation such that for each concept name C, C I ⊆ ∆; for each role name r, r I ⊆ ∆ × ∆; for each object name c, c I ∈ ∆.

  ...; • attribute role names a 0 , a 1 ,...; • value role names op 0 , op 1 , ...; • concept and role constructors: ¬, , ∃, {}; • the subsumption relation: ; and • logical connectives: ¬, → . All the relation concept names are atomic relation concepts, all the value concepts are atomic value concepts, all the attribute role names are atomic attribute roles. If R and S are relation concepts, V, W are value concepts, a, b are attribute roles , op is value role, ϕ and ψ are statements, then (i) ¬R, R S, ∃a.V are relation concepts;

(ii) ¬V, V W, ∃op.V, {v 0 , ...., v n } are value concepts; (iii) a b, ¬a are attribute role names;

The work is supported by the National Natural Science Foundation of China (60496326, 60573063, 60573064 and 60773059), the National High-Tech Research and Development Plan of China under Grant No.2007AA01Z325.

The satisfaction of statements are defined as follows:

By adding concept and role constructors, we could extend ALC to some complicated DL systems. In next chapter we present an extended DL for relational database.

Description logic MDL

In this section we present a description logic MDL for relational databases, then we propose a translation from relational database to MDL, and show that the translation preserves the information of tuples, relations in relational database.

Calvanese et al. [START_REF] Borgida | Description logics for data bases[END_REF][START_REF] Calvanese | Description logic framework for information integration[END_REF] proposed a translation from ER-schema to DLR. In his translation, a tuple entity is taken as a constant in DL, and entity sets are translated into concepts in DL. For each attribute, there is a special 2-arity role in DLR, whose first component is an entity and the second component is the attribute value of that entity. We use an similar way to express tuples and relations from relational databases in description logic. Tuples in relational database are interpreted as constants in DL, that is, elements of the domain of DL model. A relations, as a set of tuples with the same attributes set, is interpreted as a concept. Like the translation from ER-schemas to DLR, we take attribute values as constants, and for each attribute name there is a role associated. Binary relations on attribute values are also interpreted as roles.

Note that there are two kind of constants, one for tuple and the other for attribute value. Assume that there is a concept R in DL, associated with a relation R in a relational database. For a tuple constant t, statement R(t) means that tuple t is an element of relation R. But for a attribute value constant v, R(v) is just meaningless in the corresponding relational database, though that statement has no syntax error in the traditional DL system. For the similar reason, the role for the binary relations of attribute name, and the role for the tuple-attribute value association cannot be syntactically distinguished.

All of above show that it is necessary to propose a many-sorted logic to distinguish different types of object syntactically. We now present a many-sorted description logic MDL, the formal description is as follows: Definition (syntax of MDL) The language L MDL for MDL contains the following primitive symbols:

• tuple constant names t 0 , t 1 , ...;

• value constant names v 0 , v 1 , ...;


Maria Teresa Godinho
email: mtgodinho@ipbeja.pt

Luis Gouveia
email: legouveia@fc.ul.pt

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

Natural and Extended formulations for the Time-Dependent Travelling Salesman Problem

In this paper we present a new formulation for the Time-Dependent Travelling Salesman Problem (TDTSP). We start by reviewing well known natural formulations with some emphasis on the formulation by Picard and Queyranne (1978). The main feature of this formulation is that it uses, as a subproblem, an exact description of the n-circuit problem. Then, we present a new formulation that uses more variables and is based on using, for each node, a stronger subproblem, namely a ncircuit subproblem with the additional constraint that the corresponding node is not repeated in the circuit. Although the new model has more variables and constraints than the original PQ model, the results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested, gaps that are close to zero. Thus, the new model is worth investigating for solving TDTSP instances. We have also provided a complete characterization of the feasible set of the corresponding linear programming relaxation in the space of the variables of the PQ model. This characterization permits us to suggest alternative methods of using the proposed formulations.

Introduction

Consider a graph G=(V,A), where V ={1,2,..,n} and A={(i,j): i,j=1,..,n, i ≠ j}. The Time-Dependent Travelling Salesman problem (TDTSP) is to find a minimum cost Hamiltonian circuit, starting and ending on node 1, where arc costs depend on its 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 h ij c . Clearly, an arc (1,j) leaving the depot can be only in position 1 and an arc (i,1) entering the depot can be only in the last position. Every other arc (i,j), i,j ≠ 1, can be located in positions h=2,…,n-1.

The TDTSP was motivated by the following one-machine scheduling problem. Consider a set of n-1 jobs, corresponding to the nodes in the set V\{1}, to be performed on a single machine which can handle one job at a time. Transition costs h ij c occur when job i is to be processed at position h and in addition, is immediately followed by job j. We assume an idle state for the machine corresponding to the initial and final states of the machine and which will be represented by node 1.

Then, we have a set up cost for any job j, given by 1 1 j c , and a cooling cost for any job i given by 1 n i c . The problem is to find the cheapest sequence for performing all jobs.

Two special cases of the TDTSP are well known. The most well known case, the Asymmetric Traveling Salesman Problem (ATSP) (see, for instance, [START_REF] Lawler | The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization[END_REF]), is obtained when for every arc (i,j) we have h ij ij c c = for every h (that is, the cost of each arc does not depend on its position). The other case, the so-called Cumulative Traveling Salesman Problem (CTSP) also known as the traveling deliveryman problem, is obtained by considering ( )

h ij ij c n h c = -
for every arc (i,j) and every h, where ij c is a given "base" cost. The CTSP models the situation where one wants to minimize the sum of all distances from node 1 to any other node (excluding node 1). This model has applications in machine scheduling and delivery problems where one seeks to minimize the average arrival time at the customer locations. We note that in deliver applications, the cost of an arc (i,j) in position h is defined by (n-h+1) ij c since in this case one wants to compute in addition the total time that the distributor is out of the depot. We note that models presented for one case are quite easily adapted for the other one and the results taken from a small computational experiment performed with the models presented in this paper, indicate that no significant difference arises when either one of the two versions is tried. Thus, we will present our models with the first cost definition mentioned above.

Exact methods for solving the CTSP are described, among others, in [START_REF] Lucena | The Time-Dependent Traveling Salesman Problem -The Deliveryman Case[END_REF], [START_REF] Fischetti | The Delivery Man Problem and Cumulative Matroids[END_REF], [START_REF] Bianco | The Traveling Salesman Problem with Cumulative Costs[END_REF] and, more recently, in [START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF], Méndez-Dias et al (2008) and [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF]. [START_REF] Lucena | The Time-Dependent Traveling Salesman Problem -The Deliveryman Case[END_REF] proposes an algorithm based on a non-linear integer programming formulation by Picard and Queyranne in which lower bounds are obtained from a Lagrangean relaxation and presents computational results for problems up to 30 nodes. A similar approach was followed by [START_REF] Bianco | The Traveling Salesman Problem with Cumulative Costs[END_REF] which derive a Lagrangean relaxation scheme from an integer linear programming formulation also proposed by Picard and Queyranne (see next section). They solve instances with up to 35 nodes. [START_REF] Fischetti | The Delivery Man Problem and Cumulative Matroids[END_REF] provide a branch-andbound algorithm based on a new integer programming formulation. The paper contains results on the cumulative matroid that are used to derive lower bounds. Problems with up to 60 nodes are solved to optimality. [START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] use a branch-and-cut scheme based on a path formulation. This is equivalent to the Picard and Queyranne formulation strengthened with several classes of inequalities that are either taken from the ATSP problem (subtour elimination inequalities and 2matching inequalities) or taken from the node packing problem. The authors apply this procedure also to the Makespan Problem and to the Total Tardiness Problem. They present results for instances taken from the literature up to 50 nodes. Méndez-Dias et al (2008) propose a new formulation which uses flow based variables as well as variables from the linear ordering problem.

In the scope of a branch-and-cut algorithm they introduce several classes of valid inequalities (which are also shown to be facet defining). They produce computational results for instances with up to 40 nodes. In [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF], the authors present an approach that is similar to the one presented by [START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] in the sense that column generation applied to a path model is also used. However, [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF] use inequalities from the TDTSP. Some of these inequalities are lifted versions of inequalities from the TSP, making their method stronger in theory. They produce results taken from instances with up to 76 nodes. They also provide a polyhedral study of the TDTSP showing that one class of the inequalities used in their method are facet defining.

Several formulations for the TDTSP described in the literature (see Section 2) can be obtained by using the binary variables h ij z for all ( )

, i j A ∈ and 1,.., h n =
, indicating whether or not arc ( , ) i j A ∈ is in the th h position of the circuit. A formulation that uses only the h ij z variables is called a natural formulation. Natural formulations will be reviewed on Section 2 with some emphasis on the well known formulation by Picard and Queyranne (1978). The main feature of this formulation is that it uses, as a subproblem, an exact description of the n-circuit problem. An n-circuit is a circuit with n arcs which may repeat nodes and even arcs.

The new models discussed in this paper (see Sections 3 and 5) are built on two features: i) use a stronger subproblem, a n-circuit subproblem with the additional constraint that a given node is not repeated in the circuit and ii) combine these subproblems for all nodes. The new formulation will use extra variables (besides the h ij z variables) and thus, it will fall in the class of so-called extended formulations. Although the model has more variables and constraints than the original PQ model, the results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested, gaps that are close to zero. Thus, the new model is worth investigating for solving TDTSP instances, either by using it within available ILP packages or as the subject of determining what inequalities are implied by the linear programming relaxation of the new model and are not redundant in the linear programming relaxation of the Picard and Queyranne model. In fact, this is the topic of Section 4 and we will relate a set of such inequalities with the inequalities described in [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF]. We should emphasize that our goal is not to obtain a formulation that provides fast lower bounds. The main aim is to propose a formulation that produces very tight lower bounds permitting us to get more insight on the structure of the problem (eg., projected inequalities, which subproblems are strong for a given commodity).

However, in the conclusion, we will suggest some alternative ways for handling the proposed formulation."

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. Given an integer linear programming model P defined on two sets of variables x and z, we denote by Proj x (F(P L )) the projection of the polyhedron defined by P L into the space of the x variables, more precisely, Proj x (F(P L )) = {x: there exist z such that (x,z) is feasible for P L }

Natural formulations for the TDTSP -The Picard and Queyranne Formulation

The well known formulation by Picard and Queyranne (1978), denoted by PQ in the sequel, is as follows:

{ } { } { } { } ( , ) 1,..., 1 1 2,..., 1 \ 1 1 \{1} 1 1 ( 1) ( 2) ( 3) ( 4) 1 \ =1 \ 1 ; 1,..., 1 0,1 ( , ) ; 1,..., 1 h h ij ij i j A h n h j ij h n i V j j V h h ij ji i V i V h ij PQ PQ PQ PQ minimize c z z z for all j V z z z for all j V h n z for all i j A h n ∈ = = -∈ ∈ + ∈ ∈ = ∈ = ∈ = - ∈ ∈ = + ∑ ∑ ∑ ∑ ∑ ∑ ∑
Constraints (PQ1) guarantee that each node is visited exactly once. Constraints (PQ3) state that an arc enters node j in position h if and only if another arc emanates from this node in position h + 1. Constraints (PQ2) state 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 (PQ4) define the domain of the variables.

Other natural formulations for the TDTSP were proposed in [START_REF] Fox | A N-Constrained formulation of the (Time-dependent) Traveling Salesman Problem[END_REF]. The formulations proposed by Fox et al. have only O(n) constraints in contrast to the PQ formulation that has O(n 2 ) constraints. However, Gouveia and Voss (1995) have shown that the linear programming relaxation of the PQ formulation is at least as good (stronger in some cases) than the linear programming relaxation of the best model presented in [START_REF] Fox | A N-Constrained formulation of the (Time-dependent) Traveling Salesman Problem[END_REF]. Furthermore, an empirical study given in [START_REF] Gouveia | Uma análise comparativa de formulações para o Problema do Caixeiro Viajante[END_REF] has shown that the linear programming bound provided by the PQ model produces reasonable improvements on the linear programming bounds produced by the best model by [START_REF] Fox | A N-Constrained formulation of the (Time-dependent) Traveling Salesman Problem[END_REF].

In order to motivate the extended models defined in the next section, we look more closely to the system defined by (PQ2)-(PQ4). This system is composed by the network flow based equations defining a path in an adequate layered graph. We let G PQ = (V PQ , A PQ ) denote this graph where V PQ contains two copies of node 1, 1 1 and 1 n+1 , and n-1 copies j h (h=2,…,n) of each node j (j = 2,…,n).

The arc set A PQ is composed of all arcs (i h ,j h+1 ), for h=2,…,n-1 and (i,j) in A plus the arcs (1 1 , i 2 ) and (i n , 1 n+1 ) for all i in V\{1}. The previous remark implies that the linear programming relaxation of the model defined by (PQ2)-( PQ4) is exact since the associated constraint matrix is totally unimodular.

Any integer solution for the model defined by (PQ2)-( PQ4) is a path with n arcs (or a n-circuit in the original graph). Note, however, that the path may pass through several copies of the same original node or arc. Constraints (PQ1) impose that each node of the original graph is visited exactly once (and thus, no arc of the original graph can be used more than once) leading to a valid integer formulation for the problem. However, if we add these constraints to the system defined by (PQ2)-(PQ4), the new system is no longer integer. In fact, we lose integrality by just including a constraint (PQ1) for a single node k. In the new models proposed in this paper we will incorporate the condition "a node k is visited only once in the tour" in the n-circuit subproblem and we will also provide an exact formulation for this subproblem.

More precisely, the extended formulations discussed in this paper are based on the following two steps:

Step 1-Fixing a node k in V\{1} and strengthening the subproblem described by (PQ2)-(PQ4) in terms of the fixed node k, by requiring that this node is visited only once in the tour.

This step leads to several models with a stronger linear programming relaxation, each one based on a different node k in V\{1}. A model with a much stronger linear programming relaxation is obtained by

Step 2 -Considering together the subproblems for all

In the following, we denote by a n-circuit(k), a n-circuit starting and ending in node 1 and passing only once through node k.

k in V\[1}.

Extended Formulations for the TDTSP -The Single(k) Model

For a given node k in V\{1}, let It appears to be far from easy to write an exact model only with the h ij z variables, for this subproblem. Later on, we will give some evidence indicating that such a model will include an exponential sized set of constraints.

However, we can write a compact exact formulation by using extra variables (an extended formulation). We propose an exact formulation that is more compact than the one presented in

, ( 1
, ) i j A j 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 i) h = 1, i = 1, j ∈ V\{1}
. They are defined only on the following three cases:

ii

) h = 2,...,n-2, i ∈V\{1,k}, j ∈ V\{1}, i ≠ j iii) h = n-1, i ∈ V\{1,k}, j = k.
The variables 2 hk ij z indicate whether arc ( )

, ( ,
1) i j A j k i ∈ ≠ ≠
is in the h th position in the circuit, from node 1 to node 1 passing through node k and is after node k

i) h = 2, i = k, j ∈ V\{1,k}
. They are defined only on the following cases:

ii

) h = 3,...,n-1, i ∈ V\{1}, j ∈ V\{1,k}, i ≠ j iii) h = n, i ∈ V\{1}, j = 1.
Using these variables, we can write the following new model for the n-circuit(k) subproblem (C2a). Note that the definition 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 defined). We note that similar observations hold for most of the models presented in the remainder of the text.

{ } { } 1 1 \{1} 1, \{1} ; 1, ; ; 1, ; \{1} 1 1 ( 2 1 ) 1 1 0 \ 1 , , 1,.., 2 ( 2 2 ) 2 1 0 1,..., 1 ( 2 3 ) 2 2 0 \ 1 , , 2,.., k j k j V h k hk ij ji k j V j V j k h k hk kj jk k j V j k j V j k h k hk ij ji j V j k j V z H P z z for all i V i k h n H P z z h n H P z z for all i V i k h n ∈ + ∈ ∈ ≠ + ∈ ≠ ∈ ≠ + ∈ ≠ ∈ = - = ∈ ≠ = - - == - -= ∈ ≠ = ∑ ∑ ∑ ∑ ∑ ∑ ∑ { } { } { } 1 ( 2 4 ) 1 2 ( , ) , 1,..., ( 2 5 ) 1 0,1 ( , ) , , 1, 1,.., 1 ( 2 6 ) 2 0,1 ( , ) , 1, , 2,.., ( 2 7 ) 0,1 ( , ) , 1,.., ( 2 8
)

k hk hk hk ij ij ij k hk ij k hk ij k hk ij k H P g z z for all i j A h n H P z for all i j A i k j h n H P z for all i j A i j k h n H P g for all i j A h n H P - = + ∈ = ∈ ∈ ≠ ≠ = - ∈ ∈ ≠ ≠ = ∈ ∈ = Table 3.1 Modelling a n-circuit(k).
We can obtain a new formulation for the TDTSP by replacing (C2a) with this circuit formulation. We let Single(k) denote this model. We note that when creating this model, constraints 1 2

h hk hk ij ij ij z z z + = for all (i,j) A ∈ and h =1,…,n
For the sake of simplicity, we maintain the designation (H2P5 k ) for these transformed equalities. Note also that due to the definition of the variables, these constraints contain the following six particular cases that will be relevant for the Appendix.

1 1 1 1 1 1 2 2 1 1, 1 (1, ) ; 2 ( ,1) ; 1 ( , ) ; 2,.., 1 2 ( , ) ; 2,.., 1 1 ( , ) ; 2 ( , ) ; k j j n nk i i h hk ik ik h hk kj kj k ij ij n n k ij ij z z for all j A z z for all i A z z for all i k A h n z z for all k j A h n z z for all i j A k i z z for all i j A j k - - = ∈ = ∈ = ∈ = - = ∈ = - = ∈ ≠ = ∈ ≠ The model Single(k) becomes minimize ( , ) 1,..., h h ij ij i j A h n c z ∈ = ∑ ∑ subject to (PQ1), (H2P1 k )-(H2P7 k ), (PQ4).
Since the model in the 1 hk ij z and 2 hk ij z variables described in Table 3.1 define the path equations on the expanded network, its corresponding matrix is totally unimodular and we can conclude that its linear programming relaxation is integer. Using this fact together with the relation between the subproblems arising in Single(k) and PQ, we can state the following result

Proposition 3.1 -Let k ∈ V\{1}. Then, Proj z (F(Single(k) L )) ⊆F(PQ L ).
As a consequence, we obtain

Cor ollar y 3.1-v(Single(k) L ) > v(PQ L ).

We will show in Section 7 that the inequality can be strict for many instances.

The subproblem in the Single(k) model guarantees that node k is not visited more than once.

This suggests that the (PQ1) constraint for the same node can be eliminated from the model without altering the validity of the model. In fact, this is obvious from an integer point of view. We show next that the same happens with respect to the corresponding linear programming relaxation.

Pr oposition 3.2 -Let k ∈ V\{1}. Then, constraint (PQ1) for the same k is redundant in Single(k) L .

Proof: . To see this, we start by adding up constraints (H2P2 k ) for all i and h. After eliminating equal terms (note that many of the variables appear on each side of the resulting equality) we obtain Before showing this, we note that the (H2P5k) permits us to eliminate the z2 variables from the model. Consider the following formulation, denoted by PQ z,z1 + (k), and that is defined as follows: minimize ( , ) 1,...,

1 1 \{1}; 2,..., 1 \{1}; 1 1 k hk j jk j V j k h n j V j k z z ∈ ≠ = -∈ ≠ = ∑ ∑ ∑
h h ij ij i j A h n c z ∈ = ∑ ∑ subject to (PQ1), (PQ3),(PQ4) and { } ( ) ( ) ( ) 1 1 \{1} 1, \{1} ; 1 1 1 1 2 2 1 1 ( 2 1 ) 1 1 0 \ 1 , 1,.., 2 ( 2 2 ) 1 1, ; ( 2 9
k j k j V h k hk ij ji k j V j V j k k j j k k ij ij k hk h ij ij z H P z z for all i V i k h n H P z z for all j A H P z z for all i j A H P z z for all i j A i j k j h n H P ∈ + ∈ ∈ ≠ = - = ∈ ≠ = - = ∈ = ∈ ≤ ∈ ≠ ≠ = - ∑ ∑ ∑ ( ) { } ) 1 , ; 1, 2,.., 1 ( 2 12 ) 1 0,1 ( , ) , 1, 1,.., 1 ( 2 6 ) k hk h ik ik k hk ij k z z for all i k A i h n H P z for all i j A j h n H P = ∈ ≠ = - ∈ ∈ ≠ = -
We note that the original constraints (PQ3) from the PQ model where obtained after eliminating the z2 variables. The next result relates, in some sense, the linear programming relaxations of the two models, Single(k) and PQ z,z1 + (k). We skip the proof since a more general result will be proved in the Appendix. for all h guarantee that the path ends at a copy of node k.

We may use figure 2.1 to illustrate the difference between the linear programming relaxations of the models PQ and PQ z,z1 + (k). Assume that the value of the z variables associated to the arcs in the illustrated path, 1,3,4,5,4,1 is equal to 1/2 (the solution may be completed by considering, for instance, a 1/2 path 1,2,3,2,5,1). Clearly the first 1/2 path satisfies the constraint (PQ1) for k = 4 since 1/2 enters node 4 in position 2 and 1/2 enter node 4 in position 4. However, these values for the z variables do not allow a 1 unit of flow (defined on the z1 variables) going from node 1 to the copies of node 4. Let k be a fixed node of V. Consider the following inequality

1 1 1 2 1,..., 1 [ \ , ] 1 \ {1 ,1 } { ,..., } h h PQ h n n ij PQ h n i V S j S z for all S V such that k k S + + = - ∈ ∈ ≥ ⊆ ⊂ ∑ ∑ (Cut k )
These inequalities simply state that the solution defined in the z variables must contain at least one path from node 1 to a copy of node k. Note that it is not necessary to consider these inequalities for a set S containing copies of nodes other than k in levels 2 or n since such inequalities are easily seen to be implied by the same inequality without such copies. Note also that the same applies for a (Cut k ) inequality where S = {k h : h =2,…,n} since it is dominated by the (PQ1) inequality for node k. We denote by PQ z + (k) the PQ formulation augmented with the (Cut k ) inequalities.

Constraints (H2P1 k ) and (H2P2 k ) guarantee the existence of one unit flow between node 1 1 and one of the copies {k h : h =2,…,n} of node k with arc capacities given by the z variables and defined by the constraints (H2P9 k ) to (H2P12 k ). Thus, by the max flow / min cut theorem we can replace this system by the set (Cut k ) and vice versa. Consequently, we have just proved that = ∑ between time-dependent variables and the design variables of the ATSP,

[ \ , ] 1 h ij h i V S j S z for all ∈ ∈ ≥ ∑ ∑ S ⊆ V\{1} (TD-Cut)
These constraints are (Cut k ) constraints for S' = {i h : i ∈ S and h =2,…,n}. As observed before, these constraints are dominated by other (Cut k ) constraints. We note that this situation of having inequalities in an extended space that are stronger than facet defining inequalities in a projected space is not uncommon, see, for instance the paper by [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF]. Several such inequalities were also discussed in [START_REF] Gouveia | Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs[END_REF] in the context of a different problem. In fact, a suitable combination of such constraints has led to new facet defining inequalities in the projected space.

The second remark follows from the derivation of the constraints (Cut k ). We could have obtained another reduced model by eliminating the z1 variables. Then, by projection we would be able to obtain the following symmetric form of the (Cut k ) inequalities

+ = ∈ ∈ ≥ ⊆ ∈ = ∑ ∑ (RCut k )
Since the two reduced models are equivalent to the original model, in terms of the associated linear programming relaxations, it is natural to assume that the two sets of inequalities, (Cut k ) and (RCut k ), are equivalent. In fact, a given (RCut k ) constraint for a set S can be obtained from the (Cut k ) constraint for the same set S combined with the (PQ3) constraints for all the nodes in set S.

That is, the fact that the (PQ3) inequalities are implied by the model guarantees that the second set is not needed. This fact is worth mentioning because in time-dependent models with a weaker linear programming relaxation and that do not imply the (PQ3) inequalities, such as the models presented in Fox et al., this equivalence is not valid and thus the two sets should be used to tighten the linear programming relaxation (although, as we stated, it might be easier to include the (PQ3) constraints and consider only one set).

Next we relate the class of the (Cut k ) inequalities with a large class of inequalities introduced in Abeledo et al ( 2010), the Admissible Flow Constraints (AFC). To make easier this relation we will use, instead, an equivalent form of the (RCut k ) inequalities.

Let S be a subset of nodes such that {k h : h =2,…,n} ⊂ S ⊂V PQ \ {1 1 ,1 n+1 } and that does not contain any node at level 2 or n except for k 2 and k n respectively. By using the equalities (PQ3) for

node k and all h we can rewrite (PQ1) for node k in a symmetric form as follows:

1 1 1 2,..., 1 2,..., 1 \ 1 h h PQ n h h k ki ki h n h n i S i V S z z z + + = - = - ∈ ∈ = + + ∑ ∑ ∑ ∑
Combining this equality with the (RCut k ) inequality for the set S we obtain 2 1 1 2 2,..., 1 2,..., 1 \{ ,..., } \ \{ ,..., }

h n h h n PQ h h ji ki h n h n j S k k i V S i S k k z z + + = - = - ∈ ∈ ∈ ≥ ∑ ∑ ∑ ∑ ∑
Note that the given conditions on the set S, guarantee that the set S \ { k h : h =2,…,n} does not contain any nodes at level 2 and n. Thus, the previous inequality can be rewritten as follows leading to the equivalent form of the inequalities (RCut k )

2 1 1 2 1 1 2 3,..., 1 2,..., 2 \{ ,..., } / \{ ,..., } : { ,..., } \ {1 ,1 } n n PQ h n h h n PQ h h ji ki h n h n j S k k i V S i S k k for all S k k S V z z + + + = - = - ∈ ∈ ∈ ⊂ ⊂ ≥ ∑ ∑ ∑ ∑ ∑ (ERCut k )
The (AFC) inequalities can be defined as follows. Consider the graph G PQ that is used to define the system (PQ2)-(PQ4) in the PQ formulation. Let X a set of nodes in that graph and E a set of arcs entering that node subset. Let C(X,E) be the set of arcs leaving X with the property that if f is an arc in this subset, then there exists an arc e in E and a path P in X such that the path (f,P,e) is elementar. The AFC inequality for the subsets X and E is as follows ( , )

f e f C X E e E z z ∈ ∈ ≥ ∑ ∑ (AFC)
Now, it is easy to see that the (ERCut k ) are AFC inequalities, we simply let X = S and E be the set of arcs entering the set X and leaving a copy of node k.

However, there are AFC inequalities that are different from (ERCut k ). Consider the simple inequality obtained by having X containing node j h+1 and another node p h+2 (note that we are referring to the layered graph defining the PQ equations). Let E = {(i,j)} with i ≠ p. Then, the corresponding AFC inequality can be written as follows

1 2 , , h h h ij jk pk k i p k i j z z z + + ≠ ≠ ≤ + ∑ ∑
It is easy to see that these inequalities are not implied by the linear programming relaxation of the PQ z + (k) model. These inequalities are a special case of the r-cycle inequalities also suggested by [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF] and which are also contained in the AFC set. With exception to the case with r = 2, the r-cycle inequalities are not contained in the set defined by the (ERCut k ) inequalities. The inequality described above is an r-cycle inequality for r = 3. These inequalities are considered in the branch-and-cut method described in [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF].

To conclude this section we note that a special case of the (Cut k ) inequalities are already known from the literature. This case is obtained by letting S = {k 2 ,…,k n } ∪ {p h } with p ≠ 1,k and h ≠ 2,n.

The inequality becomes 1 , , 1, 3, .., 1

h h pi kp i p k for all p k h n z z - ≠ ≠ = - ≥ ∑ (SCut k )
for the same k as used in the model Single(k). These constraints simply state that if arc (k,p) is in the solution in position h-1, then the next arc cannot go to node k. As far as we know, these constraints were first proposed in the context of tree problems, see [START_REF] Godinho | Formulations for the ATSP: contextualizing a strong time dependent flow based formulation (in preparation)[END_REF], and later on in [START_REF] Costa | Models and Branch-and-Cut Algorithms for the Steiner Tree Problem with Revenues, Budget and Hop Constraints[END_REF]. More precisely, it was their symmetric form that is proposed for these problems since the form (SCut k ) is valid only if the outdegree of any node is equal to one and thus, it is not valid for tree problems. Later on they were used as valid inequalities in the context of models for routing problems (see, eg., [START_REF] Godinho | On Time-Dependent Models for Unit Demand Vehicle Routing Problems[END_REF] and [START_REF] Abeledo | The Time Dependent Traveling Salesman Problem: Polyhedra and Branch-Cut-and-Price Algorithm[END_REF]). The results in these two last papers indicate that these constraints are very helpful for improving the linear programming bound of formulations similar to the PQ formulation. However, these improvements are not comparable to the full strength obtained by using all the (Cut k ) inequalities.

Extended Formulations for the TDTSP -The All-k Model

1 1 \ 1 ( 2 1) 1 1 0 , \ 1 , 1,.., 2 ( 2 2) 1 1, ; \ 1 ( 2 9) 1 , ; \ 1 ( 2 10) 1 , ; , 1 k j j V h k hk ij ji j V j V j k k j j k ij ij hk h ij ij z for all k V H P z z for all i k V i k h n H P z z for all j A k V H P z z for all i j A k V H P z z for all i j A i j ∈ + ∈ ∈ ≠ = ∈ - = ∈ ≠ = - = ∈ ∈ = ∈ ∈ ≤ ∈ ≠ ∑ ∑ ∑ { } ( ) { } { } { } , \ 1, , ; 3,.., 2 ( 2 11) 1 , ; 1, \ 1, ; 2,.., 1 ( 2 12) 1 0,1 ( , ) , , 1, \ 1 ; 1,.., 1 ( 2 6) hk h ik ik hk ij k V i j h n H P z z for all i k A i k V i h n H P z for all i j A i k j k V h n H P ∈ = - = ∈ ≠ ∈ = - ∈ ∈ ≠ ≠ ∈ = -
As before we note that by using (H2P9), ( H2P10) and (H2P12) we can eliminate some of the variables z1 (e.g., variables 1 1 1 k j z and 1 hk ik z ) and constraints (e.g., all the constraints (H2P1)) from the model. Note also that, as shown in Section 3, inequalities (PQ1) are not needed in the model (neither in its linear programming relaxation). In fact we do this in our computations, but the reduced model as it is, is easier to explain.

The new formulation has a similar interpretation to the one given in Section 3 to formulation PQ z,z1 + (k) .It can be interpreted as a combination of i) a model for a n-circuit model defined on the h ij z variables with ii) n-1 path models, one for each node k in V\{1} and defined on the variables 1 hk ij z . The linking constraints (H2P9) to (H2P12) guarantee that the n-1 paths use the arcs contained in the n-circuit. For each k, the equations (H2P1) guarantee that the corresponding path starts on the depot node 1 and the constraints (H2P2) guarantee that the path ends in a copy of node k.

In the Appendix we prove the following result . In a similar way that was used for Proposition 4.2 and the subsequent Corollary, we can show the following result

We observe that a model presented in [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] can be seen as an aggregated version of the All-k model. model in Godinho et al. also uses an exact, although less compact, model for the the n-circuit(k) subproblem (C2a). However, the linking constraints result from adding in h, the constraints (C2b) for all arc (i,j) and k in V\{1}.Thus, the linear programming relaxation of the All-k model is at least as good as the linear programming relaxation of the previous model and empirical results show that a strict domination arises for many instances.

It is interesting to contextualize this formulation in terms of the particular case of the Travelling Salesman problem (TSP). The multicommodity flow model proposed by [START_REF] Wong | Integer programming formulations of the traveling salesman problem[END_REF], for each node k, uses a commodity from node 1 to node k and another from node k to node 1. The combined systems model, for each k, a circuit passing through node k only once. However, as shown later on in [START_REF] Langevin | Classification of travelling salesman formulations[END_REF], a simpler and standard multicommodity flow model, proposed by [START_REF] Claus | A new formulation for the travelling salesman problem[END_REF], using only a single system (either a system representing a flow from node 1 to node k or a system representing a flow from node k to node 1), for each k, produces the same linear programming bound. The All-k model, as our computational results of Section 7 will show, produces reasonable improvements on the previous bounds. The reason for this is that the All-k model uses, for each k, an exact representation of the n-circuit(k) problem. We emphasize that the model by Wong implicitly contains a constraint stating that, for each k, the two flows are routed on exactly n arcs (this constraint is obtained by adding constraints in the model). Thus, the condition "n-circuit" is not sufficient for improving the linear programming bound. As we said before, for the improvement we need to use an exact model for the n-circuit(k) subproblem, for each k. The relations between all of these models and others, are more detailed in the forthcoming Godinho et al (2011).

Strengthening the All-k model

Our results will show that the linear programming relaxation of the All-k model is quite strong (for many of the instances tested we have obtained linear programming bounds that were equal to the optimal integer value). In this section we present one set of valid inequalities that permit us to improve the linear programming bounds of the All-k model (when needed to be improved). As noted in Section 4, one candidate set is the one given by the r-cycle inequalities for r > 2.

Here we propose a different set of inequalities which are taken from the linear ordering problem. The connection between this problem and the TSP has already been explored in other papers (e.g., [START_REF] Gouveia | The Asymmetric Travelling Salesman Problem: on Generalisations of Disaggregated Miller-Tucker-Zemlin Constraints[END_REF], [START_REF] Sarin | New Tighter Polynomial Length Formulations for the Asymmetric Travelling Salesman Problem with and without Precedence Constraints[END_REF] and [START_REF] Gouveia | On extended formulations for the precedence constrained asymmetric Travelling Salesman Problem[END_REF]) and with the CTSP in Méndez-Dias et al (2008). The linear ordering problem uses binary precedence pair variables, k j v indicating whether j is before k in the tour. The precedence-pair variables can be related to the variables used in our models as follows 1,.., 2 ;

1 , 2,.., ;

k hk j pj h n p V p k v z for all j k n k j = -∈ ≠ = = ≠ ∑ ∑ (LO1)
Thus, any inequality known from the linear ordering problem can be added to our models by using the constraints linking the two sets of variables. In particular, the equalities 1

k j j k v v + =
stating that for any given pair of nodes, one is before the other in the tour, have been very useful to tighten the linear programming relaxation of several models using this set of variables. Using the previous equalities that relate the two sets of variables, these constraints can be rewritten as 1,..,

hj

hk pk pj h n p V p k h n p V z z for all j k n k j = -∈ ≠ = -∈ + = = ≠ ∑ ∑ ∑ ∑ (LO2)
and then, added to the All-k model. We denote by E-All-k the augmented model. Our computational results will show that these equalities are also useful in the context of the model presented in this paper and lead to further reductions on the gaps, without increasing significantly the corresponding CPU times for the CTSP and "pure" time-dependent ATSP instances. For the ATSP, the increase in CPU times is, however, significant.

Computational Results

In this section we empirically evaluate the quality of the lower bounds given by the models presented in the previous sections. For comparing the models, we use data for complete graphs instances in set S and A are randomly generated instances. The difference between these two sets lies in the fact that instances in S are symmetric (that is arc costs for (i,j) and (j,i) are equal), while instances in A are asymmetric. For either set A, D and S, five instances are generated for every value of n considered, with 20 < n < 40. The models that we are comparing are the models PQ, Allk, and its stronger version E-All-k when needed.

The instances taken from [START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] and Méndez-Dias et al (2008) are used to show that our model produces quite good gaps (close to zero, and equal to zero for many instances) for instances suggested by others. All of these instances refer to the cumulative TSP. In fact, the instances in Méndez-Dias et al (2008) refer to the cumulative TSP with the objective (n-h)*c ij while the instances in [START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] refer to the cumulative TSP with the objective (n-h+1)*c ij . However, as pointed out before, it is quite easy to change our models for the two different cases and we will compare accordingly.

We have also created pure TDTSP instances by using the costs of the instances taken from We start by producing results for the CTSP. In the next table we present the results produced by the linear programming relaxation of our model for known ATSP instances and we compare the given gaps with best known gaps from the literature. The results for the SD (see [START_REF] Sherali | On Tightening the Relaxations of Miller-Tucker-Zemlin Formulations for Asymmetric Traveling Salesman Problems[END_REF]) and SST formulations were obtained by [START_REF] Sherali | A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints[END_REF], using a Dell Workstation PWS 650 Double 2,5 GHZ CPU with the AMPL (Vs. 8.1) and CPLEX MIP Solver (V.s 9,0). The results for the well known multicommodity flow (MCF) formulation were obtained by [START_REF] Oncan | A Comparative analysis of several asymmetric traveling salesman problem formulations[END_REF], using a Pentium IV 3GHZ CPU with the CPLEX BARRIER Solver (Vs. 9.0) The results obtained from our computational experiment show that the All-k model produces quite good gaps for the cumulative version as well as the pure time-dependent version of the ATSP.

-k E -All-k C=2 C=3 C=5 C=2 C=3 C=5 PQ TEST C=2 C=3 C=5       = 2 n C       = 3 n C       = 2 n C       = 3 n C       = 2 n C       = 3 n C TEST Best Gap PQ All -K E-All-K gr17
It should be stressed that for many of the instances tested, the gaps given by the linear programming relaxation of the model are equal to zero. The results also indicate that these bounds are significantly better than the ones given by the previous known models including the PQ model.

For the ATSP, the results are not as good, but the reported gaps are, as far as we know, the best gaps produced by known compact models, for the reported instances taken from TSP Lib.

In terms of solution times, the reported CPU times (including the solution times for solving the integer problem) indicate that the model may be difficult to use in practice for larger sized instances. However, the reported results suggest that the model can be used solely as a lower bounding method for larger instances.

Several alternative ways of using the proposed formulations are suggested next. First, by taking advantage of the projection result given in Proposition 5.1, the (Cut k ) inequalities, that are implied by the extended model on the z variables, can be separated in polynomial time, using a maximumflow algorithm. In consequence, the linear programming relaxation of the projected formulation can be computed in polynomial time in the framework of a cutting plane algorithm. An extension of such algorithm in a Branch-and-Cut scheme should permit to solve larger instances. Note that a similar approach of separating cut inequalities defined in a layered graph has already been suggested by [START_REF] Gouveia | Modelling Hop-Constrained and Diameter-Constrained Minimum Spanning Tree Problems as Steiner Tree Problems over Layered Graphs[END_REF] in the context of a different problem.

Second, the structure of the models allows us to suggest alternative decomposition techniques based on Lagrangean relaxation for obtaining the linear programming bound. Consider, for instance, the original All-k model and a method based on relaxing the constraints (H2P5), solving a simple problem on the z variables, n-1 enhanced n-circuit(k) subproblems on the z1 and z2 variables, and updating the multipliers by using subgradient optimization. A similar method can be devised from the reduced model. In this case, after relaxing the linking constraints, we obtain a ncircuit subproblem on the z variables and n-1 shortest path subproblems on the z1 variables.

Third, in order to try to overcome the size of the All-k model we can devise an iterative method where we start with the Single(k) model for a given k, and iteratively add different systems (H2P1 k )-(H2P7 k ) for different values of k. The main idea is to reach a model with a smaller size than the All-k model but with a linear programming bound that is close to the bound given by All-k. This idea follows closely the iterative method suggested in Van Vyve and Wolsey (2010) where a multicommodity flow model is used to strengthen a model based on the Miller-Tucker and Zemlin (MTZ) constraints (1960) to solve ATSP instances. That is, the authors start with a MTZ based model and iteratively add the commodities and corresponding systems of a multicommodity flow model. Note, however, that the first model in the iterative approach proposed by us is already valid for the problem while for the model given in Van Vyve and Wolsey (2010) this is true only because the MTZ constraints are already included in the model. That is, the multicommodity flow model alone is not valid unless we consider all the commodities. In both cases, a max-flow/min cut problem needs to be solved to decide how to add a new commodity. In our case, however, we need to solve the problem in a more complicated graph as specified in Section 4.

Conclusion

In this paper we have presented a new formulation for the Time-Dependent Travelling Salesman problem (TDTSP). The main feature of this formulation is that it uses, as a subproblem, an exact description of a slightly stronger version of the n-circuit subproblem arising on the well known Picard and Queyranne formulation. Although the new model has more variables and constraints than the original PQ model, the results given from our computational experiments show that the linear programming relaxation of the new model gives, for many of the instances tested and known from the literature, gaps that are close to zero. The results indicate that the new model is worth investigating for solving TDTSP instances, either by using it within available ILP packages or as the subject of further investigation in terms of new inequalities implied on the space of the variables of the PQ model. In a companion work we plan to provide a theoretical proof of the reported dominances for the ATSP.

Figure 2

 2 Figure 2.1 -A layered graph modeling a 5-circuit problem.

  [START_REF] Godinho | Combined Route Capacity and Route Length Models for Unit Demand Vehicle Routing Problems[END_REF] which have also addressed this subproblem in the context of a formulation for the vehicle routing problem. The previous formulation has O(n 4 ) variables and constraints. The new formulation has O(n 3 ) variables and constraints (thus, we gain a decrease of one order of complexity both in the number of variables and constraints) and is based on a two-layered hopindexed graph. The first 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. Figure3.1 illustrates the adequate graph for an instance on 5 nodes and for k=4. The part below, designated by "first 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.

Figure 3 .

 3 Figure 3.1 -A two-layered graph modeling a 5-circuit(4).

(

  H2P5 k ) permit us to rewrite the linking constraints g h ij hk ij z = (C2b) from the generic model describing the Single(k) model, using only the 1 hk ij z , 2 hk ij z and h ij z variables. Thus, we can eliminate the ij hk g variables (and constraints (C2b) from the model) and the transformed linking constraints become as follows:

  By adding the equality (H2P1 k ) to the previous equality and by the using (H2P5 k ) for node k we obtain the (PQ1) equality for the same node k and thus, we can eliminate it from the Single(k) model. ∆ 4. Inequalities in the space of the h ij z variables implied by the Single(k) Model One point of interest is to know what inequalities are implied by the Single(k) model in the space of the variables of the PQ formulation. Before giving a partial answer to this question we try to put in evidence the difference between the two models. The PQ formulation contains an extended description of the polyhedron describing a circuit with n arcs. The Single(k) model contains an extended description of the polyhedron describing a circuit with n arcs but with the additional constraint that node k is not repeated in the circuit. As we shall show next, the additional requirement on the Single(k) model, namely that "node k is visited exactly once" implies an exponential sized set of constraints on the space of the h ij z variables.

Proposition 4. 1 -

 1 Let k ∈ V\{1}. Then, Proj z,z1 (F(Single(k) L )) = F(PQ z,z1 + (k) L ).. As a conclusion, the linear programming bounds given by the two models, Single(k) and PQ z,z1 + (k), are equal. This new formulation, PQ z,z1 + (k), can be interpreted as a combination of i) a model for a n-circuit model defined by the PQ formulation with ii) a model for a path from node 1 to node k in V\{1} and defined on the variables 1 hk ij z , The linking constraints (H2P9 k ) to (H2P12 k ) guarantee that the path to node k uses the arcs contained in the n-circuit. The equations (H2P1 k )guarantee that the corresponding path starts on the depot node 1. Constraints (H2P1 k ) and (H2P2 k )

  We return, now, to the question of finding out what constraints are implied by the Single(k) model on the space of the h ij z variables. Clearly we will use the new model, PQ z,z1 + (k), for deriving the inequalities. It is easier to present these inequalities in terms of the layered graph G PQ associated to the PQ formulation.

  Proposition 4.2 -Let k ∈ V\{1}. Then, Proj z,z1 (F(PQ z,z1 + (k) L )) = F(PQ z + (k) L ).. By combining propositions 4.1 and 4.2, we obtain Corollary 4.1 -Let k ∈ V\{1}. Then, Proj z (F(Single(k) L )) = F(PQ z + (k) L ).. Two remarks should be done after these results. The first remark refers to the following normal cut constraint known from the ATSP, lifted into the space of the

  z,z1 denote the model PQ augmented with the (Cut k ) inequalities for all k in V\{1} Proposition 5.2 -Proj z (All-k L )) = F

  taken from the papers by[START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] andMéndez-Dias et al (2008). The instances from[START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] are instances taken from the TSP library. Mendez-Dias et al (2008) created 120 test instances, grouped in sets named A, D and S. Instances in set D are Euclidian instances;

  Bigras et al. and defining the cost of arc (i,j) in the h th position of the circuit as constant C and where ij c denotes the cost of arc (i,j) in the original instance. In our experiments, we have considered C to be equal to 2that when C=1 we obtain the CTSP and when C = n we obtain the ATSP. Thus, with these costs, we create several TDTSP instances that could be considered as being between ATSP instances and CTSP instances.Tables1 to 3present the average linear programming gaps (computed as [(Optimal Valuev(P L ))/Optimal value]*100 where P denotes the model) and the CPU times for solving the corresponding linear programming relaxations, for each group of instances. The average CPU times are given in brackets below the corresponding average gaps. The linear programming relaxations were solved using the Barrier Solver of the CPLEX 11.2 software package on a Intel CoreDuo processor at 1.33 GHz computer with 4Gb of RAM. For comparison terms, the best gaps reported in the papers by Méndez-Dias et al (2008) and. by Bigras et al (2008) will also be presented (they are given in the column "BestGap"). The Mendez-Diaz et al. (2008) computational experiments were carried out on a SUN UltraSparc III workstation with 2GB of RAM running at 1Ghz. The optimal solutions were obtained by running the model PQ with the inequalities (SCut k ) for a given k (which are in a polynomial number), mentioned at the end of Section 4, within the branch-and-bound algorithm of CPLEX. To solve the Méndez-Dias et al (2008) instances we used a Intel Xeon with 16 cores (on 4 processors) at 2.8 Ghz and 24 Gb of RAM, running Linux and Parallel CPLEX 12. To solve the Bigras et al (2008) and the pure TDTSP instances, we used the Intel CoreDuo processor at 1.33 GHz computer with 4Gb of RAM mentioned above.

Table 1 -

 1 Results from the CTSP instances used inMéndez-Dias et al (2008)

Table 2 -

 2 Results from the CTSP instances used in[START_REF] Bigras | The Time-Dependent Traveling Salesman Problem and Single Machine Scheduling problems with Sequence Dependent Setup Times[END_REF] instances

	TEST	Best Gap	PQ	All -k	E-All-K	TEST	Best Gap	PQ	All -k	E-All-k	TEST	Best Gap	PQ	All -k	E-All-k
	D-20	4,46 (6,35 )	11,48 (0,14)	0,00 (26,57)	-	A-20	0,00 (3,28)	0,55 (0,14)	0,00 (25,5)	-	S-20	0,00 (8,69)	23,73 (0,14)	0,00 (26,82)	-
	D-22	0,50 (21,08)	16,30 (0,23)	0,00 (56,54)	-	A-22	0,00 (4,46)	1,19 (0,22)	0,00 (48,75)	-	S-22	0,00 (21,42)	19,86 (0,26)	0,00 (53,80)	-
	D-24	0,61 (50,57)	17,03 (0,35)	0,00 (99,18)	-	A-24	0,15 (16,10)	2,73 (0,34)	0,00 (89,24)	-	S-24	0,11 (63,17)	30,54 (0,33)	0,00 (130,33)	-
	D-26	0,25 (100,00)	15,52 (0,54)	0,00 (183,58)	-	A-26	0,00 (14,17)	1,04 (0,49)	0,00 (157,54)	-	S-26	0,23 (52,99)	25,02 (0,50)	0,07 (231,54)	0,00 (381,75)
	D-28	0,68 (166,94)	18,94 (0,75)	0,00 (317,88)	-	A-28	0,47 (64,06)	2,31 (0,86)	0,08 (329,24)	0,00 (685,72)	S-28	0,05 (124,1)	27,02 (0,82)	0,00 (433,36)	-
	D-30	0,64 (221,39)	16,43 (1,17)	0,00 (1473,67)	-	A-30	0,58 (69,46)	4,25 (1,23)	0,52 (502,16)	0,00 (861,39)	S-30	0,22 (221,22)	28,87 (1,16)	0,00 (585,47)	-
	D-35	1,29 (694,50)	20,05 (2,95)	0,00 (421,29)	-	A-35	0,10 (176,04)	0,77 (3,02)	0,09 (1568,55)	0,00 (3271,18)	S-35	0,07 (704,96)	34,61 (2,68)	0,01 (2210,27)	0,00 (3691,26)
	D-40	1,54 (2090,91)	21,62 (6,27)	0,21 (5368,66)	0,00 (25845,9)	A-40	1,90 (1043,7)	5,49 (7,09)	1,16 (9905,29)	0,26 (25672,51)	S-40	1,35 (2566,65)	33,23 (6,12)	0,26 (7757,29)	0,00 (30292,88)

Table 3 -

 3 Results for the pure TDTSP instances.

		0,27	16,13 (0,03)	0,00 (5,49)	-
	gr21	0,00	16,29 (0,16)	0,00 (27,32)	-
	gr24	0,00	14,68 (0,30)	0,00 (99,18)	-
	bays29	0,70	13,77 (0,95)	0,14 (76,10)	0,00 (721,07)
	bayg29	1,87	13,10 (0,76)	0,15 (346,18)	0,00 (729,24)
	rbg016a	0,00	0,98 (0,06)	0,00 (5,46)	-
	rbg031a	0,00	1,32 (1,84)	0,00 (5368,66)	-
	rbg050b	0,00	-	0.00 (12148.10)	-

Table 4 -

 4 Results for ATSP instances.

This terminates the determination of the reduced model. We could go further by eliminating some of the z1 variables by using (B) and (C). However, for the sake of simplicity and to have some intuition on the new model we kept them in the model.

The Single(k) model can be generalized by considering together the n-circuit(k) systems for every k in V\{1} as follows

As before, we consider the system in Table 3.1 for the generic part and we denote by All-k the model obtained in this way. For the All-k model, we will use the designation of the constraints of

Appendix

In this appendix we show how to eliminate the entire set of the z2 variables and obtain a model with fewer variables and with a linear programming relaxation equivalent to the original All(k) model. Consider the All-k model rewritten explicitly as follows:

As we noted in section 4 the linking constraints (H2P5) permit us to obtain the following linking constraints

)

)

We show next how to use equalities (A) to (E) to eliminate the entire set of the z2 variables and obtain a model with fewer variables and with a linear programming relaxation equivalent to the original All(k) model. This transformation is described next.

i) Constraints (H2P1):

Constraints (H2P1) and (H2P2) remain unchanged.

iii) Constraints (H2P3 k ):

Now, note that by (A) we obtain 1 2

Thus, by doing a simple substitution, the inequalities (H2P3) for h=1,…,n-2 become 1 1 0

iii) Constraints (H2P4):

We show next that the inequalities that are obtained by using (A)-(E) in (H2P4) lead to redundant inequalities in the enhanced model.

Consider constraints (H2P4) for a given ,

Rearranging both hand sides, we obtain finally:

that can easily be seen to be redundant in the presence of (H2P2) and (PQ3) .

For h = n-2 we use (D) and (A) in (*) to obtain:

Rearranging, we obtain:

Finally, adding 1 n ik z -to both hand sides of the equation, we obtain

which can also be seen to be redundant in the presence of (H2P2) and (PQ3).

As for h = n-1 variables 2 nk ij z are not defined for 1 j ≠ , we can write (H2P4) as follows:

∑ By using (E) and (D) in the previous inequality we obtain:

∑ which is one of the (PQ3) equalities and, therefore, redundant in the reduced model. However, these inequalities are redundant in the presence of (PQ1), and thus we omit them from the reduced model.