Min Cost Flow with lower bound reduction to MCF algorithm

Question

We define the Min Cost Flow Problem with Lower Bounds (MCFPLB) as a generalization of the usual Min Cost Flow. The input consists of:

• a directed graph $G=(V,E)$

• capacities $u_{ij} \geq 0$ for each edge $(i,j) \in E$

• costs $c_{ij}$ for each edge $(i,j) \in E$

• a supply value $b_i$ for each node $i\in V$

• It is balanced $\sum_{i\in V} b_i = 0$.

The output are values $x_{ij}$ for each $(i,j)\in E$, so that

• $x_{ij} \geq 0$ for all $(i,j)\in E$

• $x_{ij} \leq u_{ij}$ for all $(i,j)\in E$ (capacity constraints)

• $\sum_{ij} x_{ij} - \sum_{ji} x_{ji} = b_i$ $\forall i\in V$ (flow conservation constraints)

• $x_{ij} \geq \ell_{ij}$ for all $(i,j)\in E$ (lower bound constraints)

Our objective is the same: $\min \sum_{(i,j)\in E} c_{ij} x_{ij}$

Using the MCF algorithm, solve the MCFPLB.

So the issue here is handling the lower bound constraints. The MCF problem does not inherently capture this when solving, so we must be a little creative. My current idea to motivate the MCF algorithm is to take the lower bound and add it to a node $b_i$ as demand so that the MCF will satisfy the lower bound constraints, i.e. we define $b_i' = b_i \pm \ell_{ij}$ (add for supply, subtract for demand, we add to supply nodes and subtract from demand nodes). However I am having a hard time justifying and formalizing this idea. Furthermore, I am not sure if this is the best way to do this, so I am open to any advice or help.

Answer 1

Your intuition that you need to adjust $b_i$ is correct, but you also need to adjust $u_{i,j}$. To derive the desired MCF, perform a change of variables $y_{i,j}=x_{i,j}-\ell_{i,j}$ (so that the lower bound constraints become $y_{i,j} \ge 0$). That is, replace $x_{i,j}$ with $y_{i,j}+\ell_{i,j}$ throughout your constraints, and rewrite into the form of MCF.