Exactly solving TSP using the Simplex algorithm
Petar Veličković, Thomas Sauerwald
CST Part II
Advanced Algorithms

13 May 2016

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Dynamic programming approach

Travelling Salesman Problem (http://xkcd.com/399/)

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Dynamic programming approach

Aside: Held-Karp algorithm
I Dynamic programming approach; main idea: solve the slightly

simpler problem of the shortest path visiting all nodes, thenroute the end to the beginning.
I Assume wlog that the path starts from node 1. Maintain thesolution dp(x, S) as the shortest path length starting from 1,visiting all nodes in S, and ending in x.
I Base case: dp (1, {1}) = 0.
I Recurrence relation:dp(x, S) =min dp (y, S \ {x}) + cyx

x∈S∧1∈S+∞otherwisey∈S

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Dynamic programming approach

Aside: Held-Karp algorithm
I Finally, dp(x, V ) will give the shortest path visiting all nodes,

starting in 1 and ending in x.
I Now the optimal TSP length is simply:

min dp(x, V ) + cx1x∈VThe cycle itself can be extracted by backtracking.
I The set S can be efficiently maintained as an n-bit number,with the ith bit indicating whether or not the ith node is in S.
I Complexity: O(n2 2n ) time, O(n2n ) space.

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Formulating as a linear program

LP formulation
I We will be using indicator variables xij , which should be set to

1 if the edge i → j is incluced in the optimal cycle, and 0otherwise.
I An adequate linear program is as follows:
Pn Pi−1
minimise
i=1
j=1 cij xij
subject toPP∀i. 1 ≤ i ≤ n
j<i xij +j>i xji = 2∀i, j. 1 ≤ j < i ≤ nxij ≤ 1∀i, j. 1 ≤ j < i ≤ nxij ≥ 0
I This is intentionally an incompletely specified problem:
II

We allow for subcycles in the returned path.
We allow for “partially used edges” (0 < xij < 1).

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Formulating as a linear program

LP solution

I If the Simplex algorithm finds a correct cycle (with nosubcycles or partially used edges) on the underspecified LP
instance, then we have successfully solved the problem!

I Otherwise, we need to resort to further specifying the problem

by adding additional constraints (manually or automatically).

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Formulating as a linear program

Further constraints: subcycles
I If the returned solution contains a subcycle, we may eliminate

it by adding an explicit constraint against it, and then attemptsolving the LP again.
I For a subcycle containing nodes from a set S ⊂ V , we may

demand at least two edges between S and V \ S:
Xxmax(i,j),min(i,j) ≥ 2
i∈S,j∈V \S

I There are exponentially many such constraints in the fully

specified problem! However, we often don’t need to add all theconstraints in order to reach a valid solution.
Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Formulating as a linear program

Further constraints: partially used edges
I If the returned solution contains a partially used edge, we may

attempt a branch&bound strategy on it.
I For a partially used edge a → b, we initially add a constraint

xab = 1, and continue solving the LP.
I Once a valid solution has been found, we remove all theconstraints added since then, add a new constraint xab = 0,and solve the LP again.
I We may stop searching a branch if we reach a worse objective

value than the best valid solution found so far.
I The optimal solution is the better out of the two obtained

solutions! If we choose the edges wisely, we may often obtain avalid solution in a complexity much better than exponential.
Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Demonstration

Demo: abstract
SOLUTION OF A LARGE-SCALE TRAVELING-SALESMAN
PROBLEM*AND S. JOHNSON
R. FULKERSON,
G. DANTZIG,The Rand Corporation, Santa Monica, California(Received August 9, 1954)
It is shown that a certain tour of 49 cities, one in each of the 48 states andWashington, D. C., has the shortest road distance.

THETRAVELING-SALESMAN PROBLEM might be described asfollows: Find the shortest route (tour) for a salesman starting from agiven city, visiting each of a specified group of cities, and then returning tothe original point of departure. More generally, given an n by n symmetric matrix D= (d1i), where doi represents the 'distance' from I to J,
arrange the points in a cyclic order in such a way that the sum of the d1j
between consecutive points is minimal. Since there are only a finite(n - 1)!) to consider, the problem isnumber of possibilities (at mostto devise a method of picking out the optimal arrangement which isreasonably efficient for fairly large values of n. Although algorithms havebeen devised for problems of similar nature, e.g., the optimal assignment
problem,3"78little is known about the traveling-salesman problem. We
do not claim that this note alters the situation very much; what we shall do
is outline a way of approaching the problem that sometimes, at least, enables one to find an optimal path and prove it so. In particular, it will beshown that a certain arrangement of 49 cities, one in each of the 48 statesand Washington, D. C., is best, the djj used representing road distances as
taken from an atlas.
* HISTORICAL
Exactly solving TSP using the Simplex
algorithm
NOTE:

The origin of this problem is somewhat

obscure. Petar
It Veličković, Thomas Sauerwald

TSP
Demonstration

Demo: nodes
Now we will make advantage of these techniques to solve the TSP
problem for 42 cities in the USA—using the Held-Karp algorithmwould require ∼ 4 hours (and unreasonable amounts of memory)!

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSPDemonstration

Demo: adjacency matrix

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Demonstration

Demo: final solutionUl)~~~~~~0~~~~~~~~~~0*~_~~~~~~~~~40M

400<~IV|./H

fCs CCE

4*0X40C)~~~A'-A
Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Demonstration

Demo: materials

I The full implementation of this TSP solver in C++ (along withall the necessary files to perform this demo) may be found at:https://github.com/PetarV-/Simplex-TSP-Solver

I Methods similar to these have been successfully applied forsolving far larger TSP instances. . .

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Demonstration

13,509 largest towns in the US

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSP
Demonstration

15,112 largest towns in Germany

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

TSPDemonstration

All 24,978 populated places in Sweden

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSPDemonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald

World TSP
Demonstration

World TSP – 1,904,711 places, error ≤ 0.05%

Exactly solving TSP using the Simplex algorithm

Petar Veličković, Thomas Sauerwald