balancing assignment according to the fraction of the pie
kel
anyone have any experience in modelling assignment problem that
balances the assignment between several demands?
a typical scenario:
you have three departments recieving yearly intake of people and
assignment of the supply is inaccordance with preplanned fraction (or
demand) of the pie before the actual supply is known. The excess or
shortfall of the assignment between the departments should be as close
to the fraction as possible. The crux of the problem is that we have
an non-homogenous pool of supply,
i.e. person 1 can go to department A or B
person 2 can go to department C only
person 3 can go to none of the departments
person 4 can go to department A etc......
My current solution would be to minimise:
( demand [i] / total demand ) - ( assign [i] / total assignment )
forall [i] departments
however this is a NLP, i need to solve this as a LP.
I have also tried to use the minimax method to solve the assignment
but it doesn't give a "good" solution? Any suggestions? Thanks.
Lutz Tautenhahn
your problem looks similar to a transprtation problem.
From your example you could generate a tableau as shown below.
The model is valid for the case, that excess does not have to be assigned.
There is a dummy department 4, where all excess is send to.
d1, d2 and d3 are the demands of the departments 1, 2 and 3
(=number of persons * fraction), which should be rounded to integer values.
In your example there must be d1+d2+d3=4 (4 persons).
M is any big number.
0 0 M 1 | 1
M M 0 1 | 1
M M M 1 | 1
0 M M 1 | 1
1 M M 0 | d1*alpha
M 1 M 0 | d2*alpha
M M 1 0 | d3*alpha
-------------
d1 d2 d3 4*alpha
You could start solving the transportation problem for alpha=1 and calculate
the corresponding total cost. After that solve the problem for alpha=0.
If you get the same total cost, then you have found the optimum.
Otherwise you could use the bisection method, to find the smallest alpha
which has the same total cost as the solution with alpha=1
and take this as your optimum solution.
I hope this suggestion works (I didn't try it out).
Regards,
Lutz Tautenhahn.
Paul A. Rubin
@posting.google.com:
Not sure this will help much, but let's say x_{ij} is 1 if person i is
assigned to department j and 0 if not, and let f_j be the predetermined
target fraction for department j. Also, let J(i) be the set of
departments j to which person i can legally be assigned. In what
follows, w, s, s_j, y_j and z_j are nonnegative real auxiliary variables.
minimize w
s.t. sum_{j\in J(i)} x_{ij} = 1 for all i (change to <= if you want to
allow some people to be unassigned)
s_j = sum_i x_{ij} for all j
s = sum_j s_j
s_j = f_j*s + y_j - z_j for all j
w >= y_j for all j
w >= z_j for all j
It's an LP, but there are two issues. One is that it doesn't do exactly
what I think you want it to do in the objective. It tries to minimize
the worst discrepancy between any department and its target, but the
discrepancy is measured in absolute terms and not relative to the
departmental target. Thus one extra person assigned to a department
targeted for 99% of demand is no worse than one extra person assigned to
a department targeted for 1% of demand. The other problem is that I'm
not sure the LP solution will automatically be integer, given the extra
constraints. If not, you'll have to constrain the x variables to be 0-1
and use a MILP solver.
If you're going to go to a MILP solution, we can improve the objective
function a bit. Define a sequence of constants K_1 < K_2 < ... < K_N
which represent possible sizes for the total number of customers,
introduce new 0-1 variables t_1, ..., t_N, add the constraints
s >= K_n - M*t_n n=1,...,N (where M is some adequately large parameter),
and replace w >= y_j and w >= z_j with
w >= y_j/K_n - M*(1-t_n) for all j, n
and the same with y changed to z. This will scale each individual
discrepancy by the smallest predefined constant K_n which is greater than
the actual demand (s) experienced. In other words, it's the objective I
think you wanted, but with the denominator rounded up to the next preset
K_n.
-- Paul
*************************************************************************
Paul A. Rubin Phone: (517) 432-3509
Department of Management Fax: (517) 432-1111
The Eli Broad Graduate School of Management E-mail: ru...@msu.edu
Michigan State University http://www.msu.edu/~rubin/
East Lansing, MI 48824-1122 (USA)
*************************************************************************
Mathematicians are like Frenchmen: whenever you say something to them,
they translate it into their own language, and at once it is something
entirely different. J. W. v. GOETHE