Variation on the travelling salesman problem

5 次查看（过去 30 天）
Luuc
Luuc 2012-3-2
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

请先登录，再回答此问题。

采纳的回答

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

更多回答（3 个）

Derek O'Connor
Derek O'Connor 2012-3-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.
  1 个评论
Walter Roberson
Walter Roberson 2012-3-3
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.

请先登录，再进行评论。

Derek O'Connor
Derek O'Connor 2012-3-3
@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.
Luuc
Luuc 2012-3-30
Thank you Derek O'Connor and Walter Roberson, my solution was in the dynamic programming section. I appreciate your answers!

类别

在 Help Center 和 File Exchange 中查找有关 Nearest Neighbors 的更多信息

标签

Community Treasure Hunt

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

Start Hunting!

Translated by