In a Python matrix, how to select each row once and get the lowest sum, considering there is a cost for selecting a column?

user_9127470 0
Viewed 60

In my real situation, I have a 68*160 large matrix.

In this example let's use a smaller one. each number represents a cost.

matrix = [[8, 5,      4,    7,   10,    6],
          [8,  None,  4,    12,  None,  2],
          [4,  5,     4,    2,   None,  10],
          [6,  None,  4,    1,   None,  1],
          [2,  5,     None, 3,   2,     10]]

I need to select exactly 1 value from every row. "None" can't be selected.

I need to find the combination that will get the lowest cost.

The difficult part is, for each column that is selected there is an additional cost of 2, regardless of how many items were selected from it.

If I just iterate over each row and get the lowest value, that won't work. In this example, I would get 4, 2, 2, 1, 2, but from 4 different columns. The total sum would be 11+(4*2)=19

If instead I got 4,4 from column 2 and 2,1,3 from column 3, the sum would be 14+(2*2)=18, already proving that straight up selecting the lowest from each row won't work.

I tried doing a cartesian product (every possible combination from the matrix) and adding the column costs then comparing, but that generates 68^160 results, which wouldn't finish running by the time the sun blows up.

I also tried some more complex things like iterating over each column and checking values, considering then "active" or "inactive" as needed, but the interactions of many columns with one another are very hard to take into account.

Is there any way to solve this elegantly that I'm not seeing?

math matrix python
1 Answers

you can iterate over every possible solutions by only considering row values that are either the lowest or inferior to that lowest plus two for example in your first row [8, 5, 4, 7, 10, 6] you can consider 4, 5 as candidate for this row, but selecting 6 7 or 8 would always be more costly to select.

Depending on your data structure, you can heavily reduce your calculating times.

Furthermore, instead of iterating row by row, begin with the ones with only one best solution, they may highlight colums to be selected and simplify your problem.

user_51184200
Related