Variation on the travelling salesman problem

Hello Matlab community,

Recently I've encountered a problem that has been reduced to what I believe is a variation of the TS problem.

The situation:

From a 12 by 12 matrix filled with certain numbers (between 0 and 3000), I would like to have a combination of elements that is confined by two rules:

- Only one element from a row

- The sum of the numbers of the chosen elements needs to be as close to a specific total

Do you think this problem can be solved with the help of a travelling salesman?

I greatly appreciate help, since digging books is all I have done recently.

Luuc Duijm

Answer 1

[Walter Roberson]

I don't know if Traveling Salesman is appropriate here. It reminds me a bit of source/flow problems, and it reminds me more strongly of knapsack problems.

It also appears to me to be suitable for Dynamic Programming (does anyone still do that? ;-) )

I guess these days, people would be told to solve it using GA or Ant Colony Optimization...

The good news is that there is a deterministic solution in only 12^11 operations ;-)

Answer 2

[Derek O'Connor]

It can be solved as a Zero-One Linear Program:

Let xij = 1 if the number aij is chosen for row i, zero otherwise.

First Rule: Sum(j=1:n, xij) = 1 for i = 1:n, one element per row constraint.

Second Rule: Min(i,j=1:n, aij*xij - N) = Min(i,j=1:n, aij*xij). Objective function.

Note that the second rule is not a constraint. It is a desideratum (Wow!), and that the "specific total" has no bearing on the answer.

However, there is a much simpler solution: just pick the minimum element from each row.

[Walter Roberson]

Could you go over again why the "specific total" has no bearing on the answer? If I have a matrix that is, say, 10*eye(5), and my "specific total" goal is (say) 48, then picking the minimum for each row (0) is going to give a total of 0, whereas if I picked the 10 from each row the total would be 50, the closest possible total with that matrix to the desired 48.

Answer 3

[Derek O'Connor]

@Walter, you're right, I mis-interpreted the problem. So back to the Zero-One LP solution. Given

         2     3     1
A =      4     8     3
         3     1     6

Use LPSolve on the Binary LP formulation below.

/* Answers -- Variation on TSP */

min:S1;

/* Constraints */
D1: M = 3;
O1:  2*x11 +3*x12 +1*x13 4*x21 +8*x22 +3*x23 +3*x31 +1*x32 +6*x33 - M <= S1;
O2: -2*x11 -3*x12 -1*x13 4*x21 -8*x22 -3*x23 -3*x31 -1*x32 -6*x33 + M <= S1;
R1: x11+x12+x13 = 1;
R2: x21+x22+x23 = 1;
R3: x31+x32+x33 = 1;
binary
x11 x12 x13 x21 x22 x23 x31 x32 x33
end;

Line D1 defines the value of M, the "specific total".

Lines O1 and O2 define the objective function S1 = abs(sum(i,j=1:n, aij*xij) - M)

Lines R1, R2, R3, are the one-number-per-row constraints.

This gives S1 = 0 for any M in [5:17], i.e., there are three elements, one per row, that add exactly to M in this range. Outside that range S1 > 0, with S1 = 3 for M = 2 or 20, for example.

The free LPSolve and the interface to Matlab are here

http://sourceforge.net/projects/lpsolve/files/lpsolve/5.5.2.0/

I still think there may be an easier solution.

Answer 4

[Luuc]

Thank you Derek O'Connor and Walter Roberson, my solution was in the dynamic programming section. I appreciate your answers!