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 ?

What approaches have you tried? What isn't working? Presumably you would have a 2d array of decimals and get the sums in a loop. What distribution do you need to do? — Rufus L, Sep 18 '17 at 04:44
I have updated my question. @RufusL I have tried solving it using CPLEX quadratic solver but it fails after 10*10 matrix. — Himanshu Jaswal, Sep 18 '17 at 14:18

score 0 · Answer 1 · answered Sep 18 '17 at 05:27

0

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

answered Sep 18 '17 at 05:27

jq170727

13,159
3
46
56

Note that there are R+C equations for R*C unknowns – MBo Sep 18 '17 at 06:45
Yes in this case there will be an infinite number of solutions `{ A = (-r2)-r1+10, B = r2, C = r1, D = r2+r1-10, F = (-r2)-r1+30, G = r2, H = 30-r2, J = 35-r2, L = r2 }` for parameters `r1, r2`. – jq170727 Sep 18 '17 at 07:11
Thanks @jq170727, Linear equation don't optimize the distribution. – Himanshu Jaswal Sep 18 '17 at 14:21
@MBo This is exactly the problem. My solution is working for small arrays but with bigger problem size, it gives me infeasible solution error – Himanshu Jaswal Sep 18 '17 at 14:21
To optimize this you also need to specify a function whose value is to be optimized. – jq170727 Sep 18 '17 at 14:32
@jq170727 My quadratic function was like Minimize (A^2+B^2+C^2+D^2+F^2+...) Do i have to make another minimize function. I want to optimize output of each variable (A,B,C,.) – Himanshu Jaswal Sep 18 '17 at 15:11

Optimize distribution of amount in 2d array

1 Answers1