# Tag Info

9

You can add an extra binary that equals $1$ if and only if the first constraint is satisfied: \begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align} If $\delta=1$, the first two constraints become: $$1 \le x_1+x_2+x_3 \le 3$$ And ...

5

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.

4

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.

4

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with duration $w_o$, each bin is a machine that is available for only $c_b$ time units, and $z$ is the makespan. It is also a special case of the bottleneck ...

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,\...

2

I assume one way to gain good level of interpretation of solver's result in optimization (especially in a high dimensional setting) is by doing something called Scenario Discovery. You can read more about this from linked papers here.

Only top voted, non community-wiki answers of a minimum length are eligible