3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – sgk
    Nov 8, 2022 at 2:13
  • $\begingroup$ The cost $c_{ij}$ is associated with the arc from $(i,\ell')$ to $j$. $\endgroup$
    – RobPratt
    Nov 8, 2022 at 2:25
  • $\begingroup$ I understand!! Thank you for your reply :) $\endgroup$
    – sgk
    Nov 8, 2022 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.