# Assignment problem with mutually exclusive constraints has an integral polyhedron?

I have the following problem

$$\min \sum_{i\in I} \sum_{j \in J} c_{ij} x_{ij}$$

$$s.t. \sum_{j \in J} x_{ij} \leq b_i, \forall i \in I$$

$$\sum_{j \in S_l} x_{ij} \leq 1, \forall l \in L, i \in I$$

$$\sum_{i \in I} x_{ij} = 1, \forall j \in J$$

$$x_{ij}$$ is 0 or 1 for all $$i,j$$

Here, $$b_i$$ is a non-negative integer, and $$\cup_{l \in L} S_l = J$$ and $$S_{l1} \cap S_{l2} = \emptyset$$ for all $$l1, l2 \in L$$.

I wonder if it has an integer polyhedron. I'd really appreciate your help.

Hint: Reformulate as a minimum-cost network flow problem in a directed network with supply nodes $$I$$, demand nodes $$J$$, and transshipment nodes $$I \times L$$. You can model the upper bound of $$1$$ on flow into each $$(i,\ell)\in I \times L$$ by a node-splitting transformation that moves these upper bounds to the arcs.
• I tried to reformulate it as a min-cost network flow problem before. But, I have no idea how to consider the cost $c_{ij}$. How can I consider it?
• The cost $c_{ij}$ is associated with the arc from $(i,\ell')$ to $j$. Nov 8, 2022 at 2:25