Optimize distribution of amount in 2d array

Question

I have a problem where sum of each row and column for a 2-d array is given and we have to distribute the amount in each cell of the array. There will be some cells which will be locked and you can't use them for distribution. Also, total amounts of row/column can be decimal values.

So For example, We have a 4*3 2-d array

 A   B   C
 D   E   F
 G   H   I
 J   K   L 

where sum of each row is 10,20,30,35 and sum of each column is 35,30,30.

E, I and K are locked so the equations become

 E = I = K = 0

 A + B + C = 10 
 D + F = 20 
 G + H = 30
 J + L = 35

 A + D + G + H = 30
 B + H = 30 and 
 C + F + L = 30 

I have tried linear f(x) = Min(x) and quadratic solvers f(x) = Min(x^2) using Python scipy and IBM CPLEX(C#).

Linear solver doesn't optimize the distribution.

Quadratic solver helps with that approach but it is not working for array with size greater than 10*10. Solver failed with infeasible status.

What approaches/library should i use to solve this problem given that totals can have decimal values and size of matrix can go up to 100*10000 ?

Answer 1

If you organize the equations as

 A + B + C                        = 10
 A         + D     + G + H        = 30
     B                 + H        = 30
         C     + F            + L = 30
             D + F                = 20
                     G + H        = 30
                            J + L = 35

you can see this is a system of linear equations Ax=b with

    1,1,1,0,0,0,0,0,0           10
    1,0,0,1,1,1,0,0,0           30
    0,1,0,0,0,1,0,0,0           30
A = 0,0,1,0,0,0,1,1,0   and b = 30
    0,0,0,1,0,0,1,0,0           20
    0,0,0,0,1,1,0,0,0           30
    0,0,0,0,0,0,0,1,1           35

Solving such systems has been discussed on Stack Overflow previously:

• Solving a linear equation