How can I find the optimal assignments for this MILP problem heuristically?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.