CODEWITHSUNDEEP
mathematical-optimization
rcorreia
rcorreia

Reputation: 559

How to find the optimal sum

Imagine this set of values:

      A B C
LINE1 2 1 1
LINE2 1 4 1
LINE3 3 1 3
LINE4 6 5 4

I can choose one value per line from 1 to 3. If I choose a value from a specific column, I need to sum the value from line 4.

Example:

2 (LINE1, COLUMN A)
1 (LINE2, COLUMN A)
3 (LINE3, COLUMN C)

So, as I chose values from COLUMN A, I need to sum both of them with the value of LINE 4. Final result:

      A B C
LINE1 2 - -
LINE2 1 - -
LINE3 - - 3
LINE4 6 - 4 

2 + 1 + 6 = 9
3 + 4 = 7
TOTAL: 16

The fact is: I need to retrieve the smaller possible total from the combination. I chose the numbers in the example randomly, but my algorithm need to choose numbers that give me the smaller total.

I think the optimal solution is to pick all numbers from COLUMN C (TOTAL: 9), but will be situations that I need to pick numbers from different columns.

I think it is a optimization problem and I thought to use simplex but I don't know how to start the development.

Thank you!

Upvotes: 1

Views: 399

Answers (3)

CliffordVienna
CliffordVienna

Reputation: 8235

This is the solution I came up with using GLPK in GNU MathProg modeling language. Note: This is literally the first thing I ever wrote in MathProg, so feedback is very welcome.

Specifically I'm not sure if the way I linked x[] and s[] is efficient (I'm more used to SAT CNF encodings than to ILP).

Save the code as test.mod and execute with glpsol --math test.mod.

set A, dimen 3;
set B, dimen 2;

set I := setof{(i,j,v) in A} i;
set J := setof{(i,j,v) in A} j;

var x{I, J}, binary;
var s{J}, binary;

s.t. lines {i in I}:
  sum{j in J} x[i, j] = 1;

s.t. rows {j in J, i in I}:
  x[i, j] <= s[j];

minimize obj:
  (sum{(i,j,v) in A} x[i, j]*v) + (sum{(j,v) in B} s[j]*v);

solve;

printf "Result:\n";
printf {(i,j,v) in A : x[i, j] == 1} " %3d %3d %5d\n", i, j, v;
printf {(j,v) in B : s[j] == 1} " --- %3d %5d\n", j, v;
printf " --- --- %5d\n", (sum{(i,j,v) in A} x[i, j]*v) + (sum{(j,v) in B} s[j]*v);
printf "\n";

data;

set A :=
# Line 1
  1 1 2
  1 2 1
  1 3 1
# Line 2
  2 1 1
  2 2 4
  2 3 1
# Line 3
  3 1 3
  3 2 1
  3 3 3;

set B :=
# Line 4
  1 6
  2 5
  3 4;

end;

Thanks to Robert for suggesting GLPK and providing an outline for the solution in his answer.

Upvotes: 2

Robert Dodier
Robert Dodier

Reputation: 17576

This seems to be an example of a so-called 0-1 assignment problem; a web search for that term should turn up a lot of hits. It is a special case of a linear programming problem. There are several software packages that could be useful. I have used GLPK for various problems and found it to be very useful. Don't bother trying to write your software for this problem; it is extremely difficult, and you needn't bother.

To describe this as a 0-1 assignment problem, let Ajk be the values in the table you showed, and introduce binary variables x11, x12, x13; x21, x22, x23; x31, x32, x33; etc (i.e. xjk for the k'th element of the j'th row) and minimize the sum of xjk times Ajk, subject to the constraint that the row sum xj1 + xj2 + xj3 = 1 for each row j. That is, xjk selects (if xjk = 1) or omits (if xjk = 0) the corresponding value Ajk, and exactly one value is selected from each row.

GLPK for instance allows you to describe such problems in terms very similar to that.

If I've misunderstood the problem, you'll have to adjust what I said about the constraints and so on. Good luck & have fun. Constrained optimization problems are always interesting.

Upvotes: 2

gnasher729
gnasher729

Reputation: 52538

In this examples, there are seven sets of columns that you could choose from: A, B, C, A and B, A and C, B and C, A, B and C. If that set of columns is fixed you pick the smallest value in each line that belongs to one of those columns. The smallest total is the winner. 

A: 2 + 1 + 3 + 6 = 12.
B: 1 + 4 + 1 + 5 = 11
C: 1 + 1 + 3 + 4 = 9

AB: 1 + 1 + 1 + 6 + 5 = 14
AC: 1 + 1 + 3 + 6 + 4 = 15
BC: 1 + 1 + 1 + 5 + 4 = 12

ABC: 1 + 1 + 1 + 6 + 5 + 4 = 18.

Of course for k columns there are almost 2^k possibilities to choose the column; with every choice of columns the rest of the calculation is trivial.

Upvotes: 1

Related Questions