TSP Linear Programming

Linear Optimization Example

The LinearOptimization function finds values of variables that minimize a linear objective function subject to linear constraints.

The syntax is: LinearOptimization[ function, constraints, variables ]

For example:

LinearOptimization[x+2y,{2x+3y>=5,x>=0,y>=0},{x,y}]

TSP example with 8 points

Consider the following 8 points:

n=8;
points={{0.986012,0.900751},{0.0289531,0.340082},{0.535395,0.104843},{0.566854,0.842849},{0.607774,0.389083},{0.681787,0.119416},{0.827889,0.250604},{0.211519,0.138331}}
pointPlot=ListPlot[points->Range[n],PlotRange->{{0,1},{0,1}},AspectRatio->1]

First we need to list all possible edges:

edges=

The edges determine the variables that we need for our linear programming problem. Create a list of the variables:

variables=

We need the distances along all of the edges:

dists=

With the distances and the variables, we can define our objective function:

objFn=

Now we have to define the constraints. First, we have the bounds that each variable satisfies 0<=x<=1:

boundConstraints=

Second, we have the degree constraints: the number of edges incident to each vertex must be 2.

degreeConstraints=

Now we can finally solve the linear optimization problem.

sol=LinearOptimization[objFn,Union[boundConstraints,degreeConstraints],variables]

It would be nice to draw the tour that we found, but first we must convert the solution above to a list of edges. The following loop makes a list of all edges {i,j} such that x[i,j]=1.

circuit={};
Do[
If[(x@@edge/.sol)==1,AppendTo[circuit,edge]]
,{edge,edges}]
circuit

Now we can plot the points and the tour.

graphPlot=Graph[UndirectedEdge@@@circuit,VertexCoordinates->Table[i->points[[i]],{i,1,n}]];
Show[pointPlot,graphPlot]

TSP example with 10 points

Consider the following 10 points:

n=10;
points={{0.0551931,0.468747},{0.968187,0.954793},{0.889877,0.352755},{0.459271,0.834423},{0.728395,0.983081},{0.603279,0.304738},{0.891479,0.901683},{0.0952945,0.740506},{0.134569,0.395625},{0.193813,0.0574463}}
pointPlot=ListPlot[points->Range[n],PlotRange->{{0,1},{0,1}},AspectRatio->1]

Use linear optimization to find a TSP tour among these points.

TSP example with 12 points

Consider the following 12 points:

n=12;
points={{0.916009,0.818153},{0.0768939,0.0640083},{0.184496,0.59922},{0.541404,0.00960212},{0.209695,0.0286443},{0.597839,0.273414},{0.0158134,0.914114},{0.659457,0.342847},{0.699361,0.496086},{0.324549,0.287037},{0.0738247,0.806729},{0.113852,0.927407}}
pointPlot=ListPlot[points->Range[n],PlotRange->{{0,1},{0,1}},AspectRatio->1]

Try a larger TSP example!

n=20;
points=RandomReal[1,{n,2}]
pointPlot=ListPlot[points->Range[n],PlotRange->{{0,1},{0,1}},AspectRatio->1]