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

I have an assignment problem as follows

$$$$\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}$$$$

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?

• 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? Feb 13, 2021 at 12:52
• @A.Omidi, Please see the edit.
– KGM
Feb 13, 2021 at 18:59

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.

• you mean LP or MILP? Would you please give me the LP formulation as my formulation is in the form of MILP.
– KGM
Feb 13, 2021 at 19:18
• 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. Feb 13, 2021 at 19:20
• Thanks a lot. Yes, the solution gives integer values. Are all binary metrics total uni modular matrix?
– KGM
Feb 15, 2021 at 20:54

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.

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.