How to find the optimal sum

Question

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!

Answer 1

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.