CORMSIS/APOLLO Tutorial: A Tutorial on Formulations for the (Time-Dependent) Travelling Salesman Problem Event
- Time:
- 15:00 - 17:00
- Date:
- 3 March 2016
- Venue:
- Room 3041 Building 2, Southampton Business School
For more information regarding this event, please email Dr Yuan Huang at yuan.huang@soton.ac.uk .
Event details
Abstract: In the first part of the talk, we introduce the concepts of natural and extended formulation for a 0/1 combinatorial optimization problem. We use the maximum node/edge weighted problem to illustrate these concepts. We then revisit the well known travelling salesman problem. For modelling the sub-tour elimination constraints we revisit the concepts of natural and extended formulation. We describe flow based formulations, aggregated and disaggregated and equivalent projected inequalities, weak and strong, cut constraints. Via the technique of discretization, we relate the aggregated flow model with a time(load) dependent formulation known from the literature. In the final part of the talk, we show how view the time(load)-dependent formulations in terms of an extended layered graph, leading to stronger models.
Speaker information
Professor Luis Gouveia,Faculty of Sciences, University of Lisbon,Bio: Luis Gouveia is Full Professor at the Faculty of Sciences, University of Lisbon. He holds degrees in applied mathematics (diploma) from the University of Lisbon and a Ph.D. In Operations Research. His current research interests are in network design and ILP model reformulation. He was Coordinator of the Operations Research Center at the Faculty of Sciences since 2004 to 2014 and is author of numerous papers in various journals. Luis Gouveia serves on the editorial board of some journals, including Associate Editor of Networks and of Computers & OR. He also frequently organizes various workshops and conferences.