5 views (last 30 days)

Show older comments

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

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.

Walter Roberson
on 3 Mar 2012

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.

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

Start Hunting!