# Tag Info

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