Services & Resources / Wolfram Forums / MathGroup Archive
-----

MathGroup Archive 2010

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

Search the Archive

Travelling Salesman Problem with LinearProgramming

  • To: mathgroup at smc.vnet.net
  • Subject: [mg113024] Travelling Salesman Problem with LinearProgramming
  • From: Hans-Peter Schrei <hanspeter.schrei at gmail.com>
  • Date: Mon, 11 Oct 2010 05:17:34 -0400 (EDT)

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


  • Prev by Date: Re: Shading in Plot3D
  • Next by Date: Re: double loop
  • Previous by thread: Re: Efficient Histogram Algorithm?
  • Next by thread: Re: Travelling Salesman Problem with LinearProgramming