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