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).