Re: Travelling Salesman Problem with LinearProgramming
- To: mathgroup at smc.vnet.net
- Subject: [mg113047] Re: Travelling Salesman Problem with LinearProgramming
- From: Daniel Lichtblau <danl at wolfram.com>
- Date: Tue, 12 Oct 2010 04:25:22 -0400 (EDT)
Hans-Peter Schrei wrote:
> I am trying to solve the following integer program, which is an
> instance of a Travelling Salesman Problem. However, Mathematica
> returns a soution that does not satisfy some constraints.
>
> The vector of cost coefficients is
>
> c = {0, 2, 5, 3, 7, 3, 0, 2, 4, 4, 2, 1, 0, 4, 5, 1, 3, 3, 0, 5, 5, 5,
> 2, 2, 0};
>
> The upper part of the restrictions matrix, that guarantees that
> exactly one city is following another, has the following structure:
>
> A1 = {{1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1,
> 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0,
> 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1}, {1,
> 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
> 0, 0}, {0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
> 0, 0, 1, 0, 0, 0}, {0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
> 0, 0, 1, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0,
> 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 1, 0, 0,
> 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1}};
>
> The lower part is generated with the command permutations and should
> guarantee that there are no sub-tours in the solution.
>
> A2 = Join[Permutations[{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0,
> 0, 0, 0, 1, 1, 1, 1}],
> Permutations[{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 1, 1, 1}],
> Permutations[{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
> 0, 0, 0, 0, 0, 1, 1}]];
>
> The corresponding right side of the restrictions takes the following
> form:
>
> b1 = Table[{1, 0}, {i, 1, 10}];
> b2 = Join[Table[{3, -1}, {i, 1, 12650}], Table[{2, -1}, {i, 1, 2300}],
> Table[{1, -1}, {i, 1, 300}]];
>
> Since the variable values should be from {0,1}, I add the bounds
>
> lu = Table[{0, 1}, {i, 1, 25}];
>
> If I try to find the solution with
>
> A = Join[A1, A2];
> b = Join[b1, b2];
>
> LinearProgramming[c, A, b, lu, Integers]
>
> then Mathematica returns the zero vector as a solution, which
> contradicts the first ten constraints. Looking through
> comp.soft-sys.math.mathematica, I found that Mathematica seems to have
> a lot of problems with integer programming. What I would like to find
> out is if the mistake is my own or if there is a bug in Mathematica
> and if it's a Mathematica bug, what possible workarounds exist.
>
> Best regards,
> HPS
LinearProgramming issues a warning to the effect that it seems to be
infeasible. The ILP constraint set appears to be infeasible. I
furthermore checked this by recasting as a Minimize problem (below).
Minimize uses exact simplex for solving relaxations, hence it will not
lose feasible solutions due to numerical error.
vars = Array[x,Length[c]];
obj = c.vars;
c1 = Map[0<=#<=1&, vars]
c2 = Thread[Take[A,10].vars==1];
c3 = Thread[Drop[A,10].vars<=b2[[All,1]]];
constraints = Join[c1,c2,c3];
In[19]:= Timing[min = Minimize[{obj, constraints}, vars, Integers];]
Minimize::infeas:
There are no values of {x[1], x[2], x[3], x[4], x[5], x[6], x[7], x[8],
x[9], x[10], x[11], x[12], x[13], x[14], x[15], x[16], x[17], x[18],
x[19], x[20], x[21], x[22], x[23], x[24], x[25]} for which the
constraints 0 <= x[1] <= 1 && 0 <= x[2] <= 1 && 0 <= x[3] <= 1 &&
0 <= x[4] <= 1 && 0 <= x[5] <= 1 && 0 <= x[6] <= 1 && <<15276>> &&
x[1] + x[4] <= 1 && x[1] + x[3] <= 1 && x[1] + x[2] <= 1 are satisfied
and the objective function 2 x[2] + 5 x[3] + 3 x[4] + 7 x[5] + 3
x[6] +
2 x[8] + 4 x[9] + 4 x[10] + 2 x[11] + x[12] + 4 x[14] + 5 x[15] +
<<2>> + 3 x[18] + 5 x[20] + 5 x[21] + 5 x[22] + 2 x[23] + 2 x[24]
is real
valued.
Out[19]= {335.067, Null}
Do you happen to have a distance matrix that would recast this as an
explicit TSP problem?
Daniel Lichtblau
Wolfram Research