|
|
 |
|
Jeudi 6 Octobre
| Heure: |
10:30 - 11:30 |
| Lieu: |
Salle B107, bâtiment B, Université de Villetaneuse |
| Résumé: |
Solving the Asymmetric Travelling Salesman Problem |
| Description: |
Luis Gouveia There are many ways of modelling the Asymmetric Traveling Salesman Problem (ATSP) and the related Precedence Constrained ATSP (PCATSP).
In this talk we present new formulations for the two problems that can be viewed as resulting from combining precedence variable based formulations, with network flow based formulations. As suggested in [1], the former class of formulations permits to integrate linear ordering constraints.
The motivating formulation for this work is a complicated and "ugly" formulation that results from
the separation of generalized subtour elimination constraints presented in [2] (see also [1]).
This so called "ugly" formulation exhibits, however, one interesting feature, namely the "disjoint subpaths" property that is further explored to create more complicated formulations that combine two (or three) "disjoint path" network flow based formulations and have a stronger linear programming bound.
Some of these stronger formulations are related to the ones presented for the PCATSP in [3] and can be viewed as generalizations in the space of the precedence based variables.
Several sets of projected inequalities in the space of the arc and precedence variables and in the spirit of many presented in [1] are obtained by projection from these network flow based formulations.
Computational results will be given for the ATSP and PCATSP to evaluate the quality of the new
models and inequalities.
References:
[1] L. Gouveia and P. Pesneau. On extended formulations for the precedence constrainted asymmetric
traveling salesman problem. Networks, 48(2):77{89, 2006.
[2] L. Gouveia and J. M. Pires. The asymmetric travelling salesman problem: On generalizations of
disaggregated Miller-Tucker-Zemlin constraints. Discrete Applied Mathematics, 112:129{145, 2001.
Joint work with Pierre Pesneau (University of Bordeaux), Mario Ruthmair (University of Vienna) and Daniel Santos (University of Lisbon) |
|
|
