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