MATLAB Answers

Luuc
0

Variation on the travelling salesman problem

Asked by Luuc
on 2 Mar 2012
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

  0 Comments

Sign in to comment.

4 Answers

Answer by Walter Roberson
on 2 Mar 2012
 Accepted Answer

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 ;-)

  0 Comments

Sign in to comment.


Answer by Derek O'Connor on 3 Mar 2012

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.

  1 Comment

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.

Sign in to comment.


Answer by Derek O'Connor on 3 Mar 2012

@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
I still think there may be an easier solution.

  0 Comments

Sign in to comment.


Answer by Luuc
on 30 Mar 2012

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

  0 Comments

Sign in to comment.