# matrix linear optimization problem

I have a problem at work which is the redistribution of man days over a project period. We have it in an EXCEL-sheet and man days are always shifted etc. For each month you have a monthly sum of man days from different activities from a worker. What the redistribution should do is readjusting the man days for each month for all activities to reach a treshold value which is set. I started to program the thing in EXCEL VBA but now I am stuck because I don't know how to distribute it to get the treshold value for each month. I think it can be solved via matrix calculation because it seems to me it is a linear optimization problem. Could anyone point me in the right direction - especially what kind of calculation is needed to solve this?

Treshold value: 7

The following (manual) algorithm checks if the monthly sum is above or below the treshold value. Then it picks the activity with most man days in column and shifts a day to the next column or takes a days from the next column until treshold value is reached. Then it continues to the next column until all are aligned to treshold value but I am looking for a better or faster way to do it if possible.

Iterations:

           M M M M M M M M M M M
Start   A1 3 1 3 1 3 3 3 3 3 3 1
A2 3 3 2 3 1 3 1 2 1 3 1
A3 3 3 1 3 2 2 1 3 3 2 3
SU 9 7 6 7 6 8 5 8 7 8 5

M M M M M M M M M M M
1. Ite  A1 2 2 3 1 3 3 3 3 3 3 1
A2 3 3 2 3 1 3 1 2 1 3 1
A3 3 3 1 3 2 2 1 3 3 2 3
SU 8 8 6 7 6 8 5 8 7 8 5

M M M M M M M M M M M
2. Ite  A1 2 2 3 1 3 3 3 3 3 3 1
A2 2 4 2 3 1 3 1 2 1 3 1
A3 3 3 1 3 2 2 1 3 3 2 3
SU 7 9 6 7 6 8 5 8 7 8 5

M M M M M M M M M M M
3. Ite A1 2 2 3 1 3 3 3 3 3 3 1
A2 2 3 3 3 1 3 1 2 1 3 1
A3 3 3 1 3 2 2 1 3 3 2 3
SU 7 8 7 7 6 8 5 8 7 8 5

M M M M M M M M M M M
4. Ite  A1 2 2 3 1 3 3 3 3 3 3 1
A2 2 3 3 3 1 3 1 2 1 3 1
A3 3 2 2 3 2 2 1 3 3 2 3
SU 7 7 8 7 6 8 5 8 7 8 5

M M M M M M M M M M M
5. Ite  A1 2 2 2 2 3 3 3 3 3 3 1
A2 2 3 3 3 1 3 1 2 1 3 1
A3 3 2 2 3 2 2 1 3 3 2 3
SU 7 7 7 8 6 8 5 8 7 8 5

M M M M M M M M M M M
6. Ite  A1 2 2 2 2 3 3 3 3 3 3 1
A2 2 3 3 2 2 3 1 2 1 3 1
A3 3 2 2 3 2 2 1 3 3 2 3
SU 7 7 7 7 7 8 5 8 7 8 5

M M M M M M M M M M M
7. Ite  A1 2 2 2 2 3 2 4 3 3 3 1
A2 2 3 3 2 2 3 1 2 1 3 1
A3 3 2 2 3 2 2 1 3 3 2 3
SU 7 7 7 7 7 7 6 8 7 8 5

M M M M M M M M M M M
8. Ite  A1 2 2 2 2 3 2 4 3 3 3 1
A2 2 3 3 2 2 3 2 1 1 3 1
A3 3 2 2 3 2 2 1 3 3 2 3
SU 7 7 7 7 7 7 7 7 7 8 5

M M M M M M M M M M M
Result  A1 2 2 2 2 3 2 4 3 3 2 2
A2 2 3 3 2 2 3 2 1 1 3 1
A3 3 2 2 3 2 2 1 3 3 2 3
SU 7 7 7 7 7 7 7 7 7 7 6

-
So, you want to redistribute man-hours so that the total hours of each worker to be at most a given threshold, but I expect you also want the total man-hours for each activity to not change, is that correct? In other words, if you added a sum column to the right of the tables, it should be the same in both the input and the output? – Rahul Jan 12 '12 at 13:03
The total man-hours (days actually) for activities can change but not too much but the monthly man days aligned to treshold value are what I am aiming for. I compared the sums of the examples and the sum of man days for each activity is the same for start example and result example but this is a coincidence I think. – user366121 Jan 12 '12 at 13:11

Edit (13 Jan 2012):

Your example can be solved in smaller number of iterations. I will try to code you an algorithm. But, for the time being consider the following where I reach the same solution as your example in 4 iterations:

• We ignore the column where SU = T. For example, we don't touch M2, M4, M9 in this example.
• We proceed from left to right (M1 to M11). Everything on the left will have SU = T

The basic functions are:

• Find_Odd_Any() will find the first column where SU != T
• Find_Odd_Greater_Than_T(Mx, T) will return the first column where SU > T
• Find_Odd_Smaller_Than_T(Mx, T) will return the first column where SU < T
• Exchange_One_ManDay(Mx, My) will take one man-day from the highest row in Mx and put it in the lowest row in My
Threshold (T) = 7

M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11
Start   A1 3  1  3  1  3  3  3  3  3  3   1
A2 3  3  2  3  1  3  1  2  1  3   1
A3 3  3  1  3  2  2  1  3  3  2   3
SU 9  7  6  7  6  8  5  8  7  8   5


Iteration 1:

 1. Find the first odd column where SU != T.

 Find_Odd_Any(): - Will return M1=9 2. M1 = 9. So we have to reduce and donate 2 man-days into some other column(s) where SU < T. So, now we find the next odd column where SU < T. for (i = 0; i < absolute(M1[SU] - T); i++): // this loop runs twice { Find_Odd_Smaller_Than_T(M2, 7): * This function will start checking from column M2 and return the column for which SU < T=7 * Starting from M2 because it is next to M1 and we are operating on M1 * Will return M3=6 (at loop i=0), M5=6 (at loop i=1) Exchange_One_ManDay(M1, M3): // at loop i = 0 * This function will take 1 from M1 (from max row A1) and put it inside M3 (to min row A2) at loop i=0 Exchange_One_ManDay(M1, M5): // at loop i = 1 * This function will take 1 from M1 (from max row A2) and put it inside M5 (to min row A2) at loop i=1 } * By the end of the loop, the distribution will look like the following: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 Start A1 2 1 3 1 3 3 3 3 3 3 1 A2 2 3 2 3 2 3 1 2 1 3 1 A3 3 3 2 3 2 2 1 3 3 2 3 SU 7 7 7 7 7 8 5 8 7 8 5 

Iteration 2:

 1. Find the first odd column where SU != T.

 Find_Odd_Any(): * Will return M6=8 2. M6 = 8. So, we have to reduce and donate 1 man-day from M6 into some other column(s) where SU < T. So, now we find the next odd column where SU < T. for (i = 0; i < absolute(M6[SU] - T); i++): // this loop runs once { Find_Odd_Smaller_Than_T(M7, 7): * This function will start checking from column M7 and return the column for which SU < T=7 * Starting from M7 because it is next to M6 and we are operating on M6 * Will return M7=5 (loop i=0) Exchange_One_ManDay(M6, M7): * This function will take 1 from M6 (from max row A1) and put it inside M7 (to min row A2) at loop i=0 } * By the end of the loop, the distribution will look like the following: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 Start A1 2 1 3 1 3 2 3 3 3 3 1 A2 2 3 2 3 2 3 2 2 1 3 1 A3 3 3 2 3 2 2 1 3 3 2 3 SU 7 7 7 7 7 7 6 8 7 8 5 

Iteration 3:

 1. Find the first odd column where SU != T.

 Find_Odd_Any(): * Will return M7=6 2. M7 = 6. So, we have to increase and borrow 1 man-day from some other column(s) where SU > T. So, now we find the next odd column where SU > T. for (i = 0; i < absolute(M6[SU] - T); i++): // this loop runs once { Find_Odd_Greater_Than_T(M8, 7): * This function will start checking from column M8 and return the column for which SU > T=7 * Starting from M8 because it is next to M7 and we are operating on M7 * Will return M8=8 (loop i=0) Exchange_One_ManDay(M8, M7): * This function will take 1 from M8 (from max row A1) and put it inside M7 (to min row A3) at loop i=0 } * By the end of the loop, the distribution will look like the following: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 Start A1 2 1 3 1 3 2 3 2 3 3 1 A2 2 3 2 3 2 3 2 2 1 3 1 A3 3 3 2 3 2 2 2 3 3 2 3 SU 7 7 7 7 7 7 7 7 7 8 5 

Iteration 4:

 1. Find the first odd column where SU != T.

 Find_Odd_Any(): - Will return M10=8 2. M10 = 8. So, we have to reduce and donate 1 man-day into some other column(s) where SU < T. So, now we find the next odd column where SU < T. for (i = 0; i < absolute(M10[SU] - T); i++): // this loop runs once { Find_Odd_Smaller_Than_T(M11, 7): * This function will start checking from column M11 and return the column for which SU > T=7 * Starting from M11 because it is next to M10 and we are operating on M10 * Will return M11=5 (loop i=0) Exchange_One_ManDay(M10, M11): * This function will take 1 from M10 (from max row A1) and put it inside M11 (to min row A1) at loop i=0 } - By the end of the loop, the distribution will look like the following: M1 M2 M3 M4 M5 M6 M7 M8 M9 M10 M11 Start A1 2 1 3 1 3 2 3 2 3 2 2 A2 2 3 2 3 2 3 2 2 1 3 1 A3 3 3 2 3 2 2 2 3 3 2 3 SU 7 7 7 7 7 7 7 7 7 7 6 

Python code that Implements above:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

def find_odd_any():
su = 0
i = 0

for m in x:
for a in m:
su = su + a

if su != t:
return i
else:
su = 0
i = i + 1

return None

def find_odd_greater(k):
su = 0
i = k

for m in x[k:]:
for a in m:
su = su + a

if su > t:
return i
else:
su = 0
i = i + 1

return None

def find_odd_smaller(k):
su = 0
i = k

for m in x[k:]:
for a in m:
su = su + a

if su < t:
return i
else:
su = 0
i = i + 1

return None

def exchange_one_manday(src_i, dst_i):
src_m = x[src_i]
dst_m = x[dst_i]

# Reduce 1 man-day from source
src_m[src_m.index(max(src_m))] = src_m[src_m.index(max(src_m))] - 1

# Increase 1 man-day in destination
dst_m[dst_m.index(min(dst_m))] = dst_m[dst_m.index(min(dst_m))] + 1

def print_x():
print "[",
for m in x:
su = 0
for a in m:
su = su + a
print su, m, "|",
print "] \n"

t = 7 # threshold
x = [
[3,3,3], # 9
[1,3,3], # 7
[3,2,1], # 6
[1,3,3], # 7
[3,1,2], # 6
[3,3,2], # 8
[3,1,1], # 5
[3,2,3], # 8
[3,1,3], # 7
[3,3,2], # 8
[1,1,3]  # 5
]

print "start =>",
print_x()

su = 0
i = 0
c = 0

while find_odd_any() is not None and (i+2) < len(x):

i = find_odd_any()
m = x[i]

for a in m: # find SU for the current M
su = su + a

if su != t:
d = abs(su - t) # absolute displacement from T

for j in range(0, d):
if su > t: # current M's SU is greater than T
odd = find_odd_smaller(i+1)
if odd is not None:
print "gotta exchange=", i,x[i], "with", odd,x[odd]
exchange_one_manday(i, odd)

if su < t: # current M's SU is smaller than T
odd = find_odd_greater(i+1)
if odd is not None:
print "gotta exchange=", i,x[i], "with", odd,x[odd]
exchange_one_manday(odd, i)

su = 0
c  = c + 1

print "round", c,"=>",
print_x()
#raw_input()


If you run the code above with python file.py, the output should be:

start => [ 9 [3, 3, 3] | 7 [1, 3, 3] | 6 [3, 2, 1] | 7 [1, 3, 3] | 6 [3, 1, 2] | 8 [3, 3, 2] | 5 [3, 1, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]

gotta exchange= 0 [3, 3, 3] with 2 [3, 2, 1]
gotta exchange= 0 [2, 3, 3] with 4 [3, 1, 2]
round 1 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 8 [3, 3, 2] | 5 [3, 1, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]

gotta exchange= 5 [3, 3, 2] with 6 [3, 1, 1]
round 2 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 6 [3, 2, 1] | 8 [3, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]

gotta exchange= 6 [3, 2, 1] with 7 [3, 2, 3]
round 3 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 7 [3, 2, 2] | 7 [2, 2, 3] | 7 [3, 1, 3] | 8 [3, 3, 2] | 5 [1, 1, 3] | ]

gotta exchange= 9 [3, 3, 2] with 10 [1, 1, 3]
round 4 => [ 7 [2, 2, 3] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [1, 3, 3] | 7 [3, 2, 2] | 7 [2, 3, 2] | 7 [3, 2, 2] | 7 [2, 2, 3] | 7 [3, 1, 3] | 7 [2, 3, 2] | 6 [2, 1, 3] | ]

-
Thanks for the answer. I am not sure if this solves the problem because for example if I have more days in a month than treshold value they have to be shifted to the next respectively taken from the next and it seems to build the partitions for larger numbers would take some significant calculation time which is bad for the performance of the algorithm. – user366121 Jan 12 '12 at 12:53
@user366121: If you provide an example where the unused man-days shift from one month to the next, that would clear up some confusions. Also, do you have a criteria based on which you want to do the distribution. For example, if your threshold is $S=6$ and number of activity $A=3$, is it okay to have $A_3 = 0$? – GSBabil Jan 12 '12 at 13:32
@user366121: Also, elaborate a little more on what sort of values do you want to see in $A_1, A_2, A_3$. Can they have the exact same value for each $M_1, M_2, ...$ ? – GSBabil Jan 12 '12 at 13:39
I extended the question. – user366121 Jan 12 '12 at 14:11
I will try this. – user366121 Jan 13 '12 at 9:18

That's a cute problem. I surmise there are more restrictions to it like every activity should not fall far behind the schedule, etc.

I would try the primitive greedy algorithm first. Below I assume that all you care about is that each activity is done more or less on schedule but you don't mind any distribution within one particular day (that is true if all your men can do all jobs and your initial schedule is just the schedule of customer requests you accepted, say).

Start with computing the current schedule for each activity so that $B_j(n)$ is the total number of man hours spent by the month $n$ inclusive on the activity $j$ in the non-spread schedule. The spread schedule will be constructed from left to right. Put $A_j(0)=0$. Let $n$ be the current month to process. Look at $S(n)=\sum_j a_j(n)$ where $a_j(n)$ is the number of hours initially planned for the activity $j$ in the month $n$. If $S(n)=S$, do nothing. If $S(n)>S$, move some hours forward (say, one by one). The order of moving is that you look at $A_j(n-1)+a_j(n)-B_j(n)$ and take the index $j$ corresponding to the largest of those numbers (least backlog). Then, if $a_j(n)>0$ decrease $a_j(n)$ by $1$ and increase $a_j(n+1)$ by $1$. Else, use the second least backlog index, etc. Then recalculate the backlogs and choose the least backlog index again and so on until you get $S(n)=S$. If $S(n)<S$, you should start bringing hours from the next columns in a similar manner except now, the largest backlog has prority and when you exhaust the position in the next column, you can use the next after the next, etc. Do it until you reach $S$. After you finish with scheduling column $n$, put $A_j(n)=A_j(n-1)+a_j(n)$ and repeat for the next month.

I have no idea how to encode that in Excel but if you want, I can write a code for you in some decent programming language. Just a bit later :).

OK, I wrote in Asymptote. It is pretty close to C but I had trouble with the C compiler on the computer I used. That hasn't been optimized in any way and the hours are moved one by one, which may be a bit slow if they are many. However, it seems to work. Play with it and tell me what you think :)

int [][]a; // work hours for each month and activity
int []A,B; //backlog data.
int M=15,N=7; //15 months, 7 activities
int K=7; //parameter for random initialization
int S=30; // the monthly total

//initializing the schedule randomly
//(you'll have to fill it with some real data to see if it works for you)

for(int j=0;j<N;++j)
{
a[j]=new int[];
for(int n=0;n<M;++n)
a[j][n]=rand()%(rand()%K+K);
}

int[][] aa;
for(int j=0;j<N;++j) aa[j]=copy(a[j]);//saving the intial schedule

write("Start");
write();
for(int j=0;j<N;++j)
{
string s="";
write(s);
}

for(int j=0;j<N;++j) A[j]=0; // nothing backlogged before the work starts

//the main loop

for(int n=0;n<M-1;++n) //M-1 because you don't have any freedom for the last month
{

int SS=0; //current month initial sum
for(int j=0;j<N;++j)
{
A[j]+=aa[j][n]; B[j]=A[j]-a[j][n];    //looking at the backlogs
}

int jj,u;

while (SS>S) //overworking scenario
{
jj=-1; //impossible index
u=10*M*S; //some huge stupid number exceeding all the accepted workload for the year
//if the accepted work is greater, you cannot make even 10% of it

for(int k=0;k<N;++k)
{
if((B[k]<u)&&(a[k][n]>0)) {u=B[k];jj=k;} //finding the minimal backlog you can shift
}
--a[jj][n];++a[jj][n+1]; //moving one unit forward
++B[jj]; --SS; //increasing the backlog and decreasing the load
}

jj=1;

while ((SS<S)&(jj>-1)) //underworking scenario that is fixable
{
jj=-1; //impossible index
u=-M*S; //some huge stupid number exceeding all you can do in a year

int v,vv;

for(int k=0;k<N;++k)
{
bool flag=false;
for(vv=n+1;(vv<M)&&(!flag);++vv) if(a[k][vv]>0) flag=true;
--vv;
//finding the first non-zero place to take a unit from
if((B[k]>u)&&flag) {u=B[k];jj=k;v=vv;} //finding the maximal backlog you can diminish
}
if(jj>-1)
{
++a[jj][n];--a[jj][v]; //moving one unit forward
--B[jj]; ++SS; //decreasing the backlog and increasing the load
}
}

for(int j=0;j<N;++j) A[j]-=a[j][n]; //updating backlog;

}

//just to see what we end up with; the last column shows
//what should be done to finish the annual plan

write("Finish");
write();
for(int j=0;j<N;++j)
{
string s="";
for(int n=0;n<M;++n) s+=format("%#4d",a[j][n]);
write(s);
}

pause(); //not to close window

-
Hi. Thanks for the answer. Yes a code snippet would be helpful. As a matter of fact I already tried something like this but maybe my algorithm was wrong and the performance was not acceptable. – user366121 Jan 12 '12 at 12:51
I tried to post a code sample but this stupid interface eats up every "less" sign and quite a few following characters and the preformat and code tags do not help in the slightest :(. Post on AoPS (www.artofproblemsolving.com): there you can really communicate something other than plain text. It took a couple of hours to debug the program and now this problem arose! :( The good news is that it seems to work. What are the real numbers (just tell the orders of magnitude)? I'll try with them to see if it is fast enough. – fedja Jan 13 '12 at 0:53
@fedja: you should try wrapping around your code with <pre> or <code> tags. – GSBabil Jan 13 '12 at 1:08
OK, figured out how to do it here. It turned out that one needs to put four spaces in front of each code line. A brilliant rule, indeed.... Well, let's stay nice, calm. Hope it'll work. Just don't make your hand slip. Four isn't five. Take your time, each code line must have them. Keep them neat: that must feel good! When will some guys have wits? – fedja Jan 13 '12 at 1:35
@GSBabil I tried those and failed miserably :( I'll try again next time :) Perhaps, this is just my stupidity... – fedja Jan 13 '12 at 1:37

Your problem is underconstrained. From what you have said, a solution could just be something like

           M M M M M M M M M M M
Result  A1 7 0 0 7 0 0 7 0 0 7 0
A2 0 7 0 0 7 0 0 7 0 0 7
A3 0 0 7 0 0 7 0 0 7 0 0
SU 7 7 7 7 7 7 7 7 7 7 7


or

           M M M M M M M M M M M
Result  A1 2 2 2 2 2 2 2 2 2 2 2
A2 2 2 2 2 2 2 2 2 2 2 2
A3 3 3 3 3 3 3 3 3 3 3 3
SU 7 7 7 7 7 7 7 7 7 7 7


Once you explain whether these are not acceptable solutions, and why, we can begin formalizing the problem so it is less underconstrained.

-
Hi, Both suggested solutions are acceptable although it is unlikely that solution one is going to happen. The man days represent the planning for activities and to execute only one activity in a month is very unlikely because some are happening in parallel. Let me explain further: First you have the initial planning which is based on an estimate. You estimate this activity will take so and so many days to complete. Sometimes it turns out you don't need that many days for this activity and you shift them and suddenly you have more man days in a month than allowed and have to shift again. – user366121 Jan 13 '12 at 9:10
The priority lies on the man days not the activities. You want to use all man days. – user366121 Jan 13 '12 at 9:14