9
This is a minimum cost flow problem in the bipartite graph $G=(V,A)$ with $V=N_U \cup N_B$.
Add a source node and link it to each vertex $v\in N_U$. On each of these arcs, constrain the flow to be in the range $[a_{min},a_{max}]$. Note that if $a_{min} > |N_B|$ the problem is infeasible.
Likewise with a sink node, that you link to each vertex $v \in N_B$, ...
3
In order to query the GRB_DoubleAttr_UnbdRay attribute, you need to optimize the problem with the InfUnbdInfo parameter set to 1.
3
For simplicity, I will drop the $i$ subscripts everywhere and instead write $x_d$ for $x_{i,d}$ and $y$ for $y_i$.
The linear constraint $$\sum_{d=1}^6 x_d \le 5 + y$$ enforces $$\sum_{d=1}^6 x_d > 5 \implies y=1.$$
You can derive this constraint via conjunctive normal form as follows:
$$
\left(\land_{d=1}^6 x_d\right) \implies y \\
\lnot\left(\land_{d=1}^...
2
I don't know whether this is the reason, but the documentation says that InfUnbdInfo is for LP only. So we might have to work with the LP. Two thoughts:
x = 0, u = 0 is a feasible solution for the MIP.
As x is bounded, x will not be part of the ray.
Thus, any ray for the LP should also be a ray for the MIP.
So if Gurobi decides your problem is unbounded, ...
2
Now that you have removed the range constraints, the problem decomposes by $j$ and can be solved optimally for each $j$ by a greedy algorithm: set $X_{i,j}=1$ for the $b_\max$ largest (positive) values of $R_{i,j}$.
1
I thought about the following:
then all you need is:
$$
Y \ge (\sum X_d) - 5 \ \ \& \ \ Y \le (\sum X_d)/5.
$$
This can be written in a solver:
$\forall$ worker $i$, you can just add $Cy_i$ to the cost function and add the constraint $$ \sum_{d=1}^6 x_{id} \leq 5 + y_i$$.
(Note that $y_i$ can be declared as either continuous or binary.)
Only top voted, non community-wiki answers of a minimum length are eligible
