MathGroup Archive 2010

[Date Index] [Thread Index] [Author Index]

Search the Archive

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


  • Prev by Date: Re: local variables - Module, For loop
  • Next by Date: Re: double loop
  • Previous by thread: Travelling Salesman Problem with LinearProgramming
  • Next by thread: How to solve this differential equation? (harmonic oscillator)