Shortest route problem

Find the shortest route from the starting point (p1) to the ending point (p6).

1. Set optimization variables

For each "link" in the graph, we set one variable. For example, there's a "link" from P1 to P2, so we set a variable x12. Notice that there are two variables associated with points P2 and P3, they are x23 and x32. If the value of a variable is 1, it means the "route" will pass through this link. Value 0 means this link will not be taken by the route.

vars = {x12,x13,x23,x32,x24,x25,x35,x54,x46,x56};

2. Set the objective function

We would like to minimize the total "distance" (cost) of the chosen route :

f = 15*x12 + 13*x13 + 9*x23 + 9*x32 + 11*x24 + 12*x25 + 16*x35 + 4*x54 + 17*x46 + 14*x56;

3. Set the constraints

To make sure the route is a connected path from the starting point to the ending point, we need to following constrains:

(1) for each point other than the starting and the ending points, the total entering links (inflow) should be equal to the total leaving links (outflow).

g2 = x12+x32 == x24+x25+x23;
g3 = x13+x23 == x32+x35;
g4 = x24+x54 == x46;
g5 = x35+x25 == x54+x56;

(2) for the starting point,   out flow - inflow = 1

g1 = x12+x13 == 1;

(3) for the ending point,  inflow - outflow = 1

g6 = x46+x56 == 1;

(4) we also need to set all variables greater than or equal to 0

NonNegativeness = And @@ Thread[vars ≥ 0]

4. Solve the problem

(1) First, we can use the command "Minimize", which accepts equations/inequalities as inputs

Minimize[{f, g1 && g2 && g3 && g4 && g5 && g6 && NonNegativeness},vars]

The aboce solution tells us that the shortest route is   P1 ->  P2  ->  P5  ->  P6,  and the total cost is 41.

(2) Mathematica also provides a function "LinearProgramming", which is more efficient. However, it only accepts matrices/vectors in the standard LP form as inputs. Therefore, we first need to derive the coefficients in the standard form  minimizing  f = (c^t)x,   subject  to constraints Ax >= b, x>=0.  Notice that Mathematica uses Ax >= b, different from the Ax=b in the text book. Hence when we feed the command with inputs, we have to specify for each RHS value (Subscript[b, i]) that it is an exact "equal". This can be down by setting a matrix of the form {{(Subscript[b, 1]), 0}, {(Subscript[b, 2]), 0}, ... {(Subscript[b, k]),0}}.

c = Normal[CoefficientArrays[f,vars] ] [[2]]

A = Normal[CoefficientArrays[{g1,g2,g3,g4,g5,g6},vars]] [[ 2]];
MatrixForm[A]

b = {{1,0},{0,0},{0,0},{0,0},{0,0},{1,0}}

LPSol = LinearProgramming[c,A,b]

LinearProgramming[c,A,b, Method->"Simplex"]

LinearProgramming[c,A,b, Method->"RevisedSimplex"]

LinearProgramming[c,A,b, Method->"InteriorPoint"]

Again, the above results indicate that the Shortest route is  x12=1, x25=1, x56=1. The cost is

f /. Thread[{x12,x13,x23,x32,x24,x25,x35,x54,x46,x56}->LPSol]