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.
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.
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)
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, 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.