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