Problem
- $n$ jars of water with different volumes $v_i$ have to be assigned to $m$ empty buckets with different volumes $V_j$
- $n \ge m$.
- A jar can only be poured into 1 bucket.
- Multiple jars can be poured into the same bucket.
- All jars have to be completely empty at the end.
- No bucket can be left completely empty.
- We want to find the assignment that minimizes the sum of the volume left empty across buckets (deficit), and the total amount of water that overflowed (excess).
What I tried
So I tried to map this problem to the Maximum Flow Algorithm with Lower bounds: for an input bipartite graph $G$, a source $s$, a sink $t$, two function $l,u : E \rightarrow R^+$ we seek a flow $l(e) \leq f(e) \leq u(e)$ at every edge $e$
- arcs $(s,i)_{i\in[n]}$ have capacity $u(s,i) = l(s,i) = v_i$
- inner edges $(i,j){i\in[n],j\in[m]}$ have lower bound $l(i,j)=0$ and capacity $u(i,j)=v_i$
- arcs $(j,t)_{j\in[m]}$ have lower bound $l(j,t) = (1-\epsilon)V_j$ and upper bound $u(j,t) = (1+\epsilon)V_j$.
That is, we are allowing for a fraction of the flow to go overload or underload. The attached paper explains how to modify the graph structure to find a feasible flow.
Question
If this parametrization is correct (is it?), I don't know how to guarantee that the inner edges must have an integral value: I don't want the flow from one jars to be split across different buckets. I have read that the Ford–Fulkerson algorithm should proceed with integer values, but I am reaching the end of my knowledge here. Also sorry for butchering the formalism :'/
You can solve the problem via integer linear programming as follows. Let binary decision variable $x_{ij}$ indicate whether jar $i$ is poured into bucket $j$. Let nonnegative decision variables $d_j$ and $e_j$ denote the amount of deficit or excess, respectively, for bucket $j$. The problem is to minimize $$\sum_j \left(d_j + e_j\right)$$ subject to linear constraints \begin{align} \sum_j x_{ij} &= 1 &&\text{for all $i$} \tag1\label1 \\ \sum_i x_{ij} &\ge 1 &&\text{for all $j$} \tag2\label2 \\ \sum_i v_i x_{ij} + d_j - e_j &= V_j &&\text{for all $j$} \tag3\label3 \\ \end{align} Constraint \eqref{1} assigns each jar to exactly one bucket. Constraint \eqref{2} assigns at least one jar to each bucket. Constraint \eqref{3} defines the deficit and excess for each bucket.
You cannot relax integrality of $x_{ij}$ and expect to get integer values. The objective function would encourage splitting of $v_i$ to multiple buckets, yielding fractional values for $x_{ij}$.