CP-AI-OR
2005 Invited TalkMonday, 30th May 2005, 9:30 - 10:30 |

**Models
for Solving the Travelling Salesman Problem**

H.P. Williams (London School of Economics, U.K.)

*Abstract:*- The Travelling Salesman Problem is a classic problem of Combinatorial Optimisation and involves routing around a number of cities in order to cover the minimum total distance. It is notoriously difficult to solve practical sized instances optimally. The classical Integer Programming formulation involves an exponential number of constraints. Alternative formulations will be given which use less constraints (a polynomial number). These rely on (often ingenious) ways of introducing extra variables with a variety of real-life interpretations. Most (but not all) of these formulations have weaker LP Relaxations than the Classical formulation. However their compactness and the existence of extra variables suggest they could be valuable if a CP approach is adopted. This aspect is still to be investigated.

*Biography:*- Paul Williams
is a Professor of Operational Research at the London School of Economics.
After his degree in mathematics at Cambridge he studied Mathematical Logic
under the late Professor R.L. Goodstein. He previously worked in other universities
such as University of Southampton, University of Edinburgh, and the University
of Sussex. He also worked for IBM developing software for Linear and Integer
Programming where he got particularly interested in Modelling, realising that
it is possible to formulate Integer Programming models in different ways.
He is
particulary well known for his books "Model Building in Mathematical
Programming" (first published in 1978 and now in a 4th edition) and "Model
Solving in Mathematical Programming" (1993).