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