Variation on the travelling salesman problem

4 views (last 30 days)
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

Accepted Answer

Walter Roberson
Walter Roberson on 2 Mar 2012
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 ;-)

More Answers (3)

Derek O'Connor
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
Walter Roberson
Walter Roberson on 3 Mar 2012
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.

Derek O'Connor
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 */
/* 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;
x11 x12 x13 x21 x22 x23 x31 x32 x33
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.

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!

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!