带下界最大流模型求解罐桶分配问题的正确性验证及整数流约束实现问询

问题背景 #

我现在碰到这么一个实际问题：有n个装着不同体积水的罐子（每个罐子的水量是$v_i$），要把这些水分配到m个空桶里（每个桶的容量是$V_j$），而且$n \ge m$。规则是：

• 每个罐子的水只能全部倒进某一个桶里，不能拆分到多个桶
• 多个罐子可以倒进同一个桶
• 最后所有罐子必须完全倒空
• 每个桶都不能是空的
• 我们的目标是找到一种分配方式，让所有桶的剩余空间（也就是deficit，桶容量减实际装的水量）和溢出的总水量（excess，实际装的水量超过桶容量的部分）的总和最小。

我的尝试思路 #

我想着把这个问题映射到带下界的最大流算法上，构建了一个二分图$G$，外加源点$s$和汇点$t$，每条边都设置了下界$l(e)$和上界$u(e)$：

• 从源点$s$到每个罐子$i$的边：上下界都设为$v_i$，也就是l(s,i) = u(s,i) = v_i，这样保证每个罐子的水都必须全部流出去
• 罐子$i$到桶$j$的边：下界设为0，上界设为$v_i$，也就是l(i,j)=0，u(i,j)=v_i，意思是可以选择把这个罐子的水倒进这个桶，也可以不选，但最多只能倒整个罐子的量
• 从桶$j$到汇点$t$的边：下界设为(1-ε)V_j，上界设为(1+ε)V_j，这里的ε是个小参数，用来允许桶里的水量可以稍微低于或者超过容量，这样就能把deficit和excess都纳入模型里。我看到有论文讲过怎么修改图结构来找到这种带下界的可行流，就打算用这个方法试试。

我的疑问 #

现在我有两个地方拿不准，想请教大家：

1. 我这个模型的参数化是不是正确的？能不能准确对应到原问题的目标和约束？
2. 怎么保证罐子到桶的边的流是整数？因为原问题要求每个罐子的水只能全倒进一个桶，不能拆分，但我不确定这个模型能不能约束这一点。我之前看到Ford–Fulkerson算法好像能处理整数流的情况，但这块我了解得不多，有点摸不着头脑。

抱歉可能我在形式化表述上有点不严谨，还望大家多多包涵！

备注：内容来源于stack exchange，提问作者WaterFox