4
$\begingroup$

I have an assignment problem as follows

$\begin{equation} \begin{array}{*{35}{l}} \underset{d_{u,c}}{\max}\hspace{1mm}\hspace{1mm}\sum_{u=1}^{U}\sum_{c=1}^{C}d_{u,c}\omega_{u,c}\\ \text{}\text{subject to }\text{ C1:} \hspace{2mm}1\le \sum_{c=1}^Cd_{u,c}\le 10,\forall u, u=1,\cdots, U, \\ \text{}\hspace{16.5mm}\text{ C2:} \hspace{2mm}\sum_{u=1}^U d_{u,c}\le 50,\forall c, c=1,\cdots, C, \\ \end{array} \end{equation}$

The objective is to maximise the quality/quality.

Is there a way I can solve this problem heuristically but optimally? For example, some iterative approach?

What I tried:

For each $u$, I find the $C_{\max}$ largest values for $\omega_{u,c}$ and assign them to corresponding $c$'s.

Then Find the number of assignment we get for each $c$

If for some $c$, we have higher than $U_{\max}$ assignments, find the $X_c$ number of lowest ($X_c$ is the number of extra assignments for $c$) values of assigned $\omega_{u,c}$ and unassociated them.

However, I find that this is not giving me optimal assignments.

Any Help?

$\endgroup$
2
  • $\begingroup$ Would you say please, what do $C_\max$ and $U_\max$ mean? If they are the pre-defined parameters, as the problem is maximization, almost all of the $d_{u,c}$ might be greater than zero. Is it reasonable? $\endgroup$
    – A.Omidi
    Feb 13 at 12:52
  • $\begingroup$ @A.Omidi, Please see the edit. $\endgroup$ Feb 13 at 18:59
5
$\begingroup$

This is the transportation problem, a network flow problem (in a directed bipartite network) and hence solvable exactly as an LP. If you prefer a combinatorial algorithm, this might be a good exercise to learn the primal-dual method, and your heuristic approach can provide the initial solution.

$\endgroup$
3
  • $\begingroup$ you mean LP or MILP? Would you please give me the LP formulation as my formulation is in the form of MILP. $\endgroup$ Feb 13 at 19:18
  • 2
    $\begingroup$ You can replace the integrality constraint C3 with bounds $0 \le d_{u,c} \le 1$. Because the constraint matrix is total unimodular, any basic feasible solution will automatically take integer values. $\endgroup$
    – RobPratt
    Feb 13 at 19:20
  • $\begingroup$ Thanks a lot. Yes, the solution gives integer values. Are all binary metrics total uni modular matrix? $\endgroup$ Feb 15 at 20:54
4
$\begingroup$

It seems to me that this problem can be reduced to a variant of the generalized assignment problem (GAP). If you set $U_{\max} = 1, \forall u$, then your problem is indeed GAP with equal weights for items. I know GAP is NP-hard, but not sure about this variant of GAP. I guess you can find some good stuff if you look for variants of GAP.

$\endgroup$
3
$\begingroup$

I did a few computational trials on a small example, and it appears that you can solve the Lagrangean relaxation via a gradient based method. If we reverse the constraint requiring all users to be assigned at least one provider, to $$-\sum_{c=1}^C d_{u,c}\ge -1\,\forall u$$(so that all multipliers are nonnegative), the Lagrangean problem is$$\min_{\lambda,\mu,\nu\ge0}LR(\lambda,\mu,\nu)=\\\max_{d\in\left\{ 0,1\right\} ^{U\times C}}\left(\sum_{u}\sum_{c}\omega_{u,c}d_{u,c}-\sum_{u}\lambda_{u}\left[\sum_{c}d_{u,c}-C_{\max}\right]\\+\sum_{u}\mu_{u}\left[\sum_{c}d_{u,c}-1\right]-\sum_{c}\nu_{c}\left[\sum_{u}d_{u,c}-U_{\max}\right]\right)$$where $\lambda$ is the multiplier vector for the upper limit on providers assigned to a user, $\mu$ is the multiplier vector for the lower limit, and $\nu$ is the multiplier vector for the upper limit on users assigned to a provider. We can reduce that to$$LR(\lambda,\mu,\nu)=\sum_{u}\sum_{c}\left(\omega_{u,c}-\lambda_{u}+\mu_{u}-\nu_{c}\right)^{+}\\+C_{\max}\sum\lambda_{u}-\sum_{u}\mu_{u}+U_{\max}\sum_{c}\nu_{c}$$, using the fact that in the inner maximization $d_{u,c}$ will be 1 if it has a positive coefficient and 0 if it has a negative coefficient. $LR$ is piecewise linear, with a gradient defined piecewise, so with a little care a gradient based descent procedure should work (and does in my limited tests).

That said, I personally would use an LP solver, per Rob's answer.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.