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