The problem can be stated as:
I have $m$ liquids ($A_i$ is the amount of the $i$-th liquid) and $n$ tanks ($x_j$ is the volume of the $j$-th tank), and the task is to find the best way to fill the tanks.
Additional information:
- $A_i, x_j \in \mathbb{N}$
- If we fit the tank $x_j$ with liquid $A_i$, then we are not allowed to fit it with anything else (e.g. we can not pour $2$l from $A_1$ and $3$l from $A_2$ into tank $x_1 = 10$).
- The liquid $A_i$ can be distributed over several tanks (but watch 2.)
My first model was:
We have the following problem: solve for $(k_i)$
$$ \left\{ \begin{aligned} \min & (k_1 x_1 + k_2 x_2 + \cdots + k_n x_n - A_1) \\ \min & (k_1 x_1 + k_2 x_2 + \cdots + k_n x_n - A_2) \\ \vdots & \\ \min& (k_1 x_1 + k_2 x_2 + \cdots + k_n x_n - A_n) \end{aligned} \right. $$
$$ k_i > 0 \\ A_i > 0 \\ \min(...) > 0 $$
$k_i$ may be either $0$ or $1$. If $k_i$ is $1$ in some equation, it can only be $0$ in all other. The $A_i$ and $x_i$ are known.
Note: This might not be your problem, but I think it is quite close to it.
Update: Calculating a small example exposed a modeling error. I am trying to fix this.
Update: The solution has morphed into a round based procedure, where each round tries to pour as much liquid as possible until one runs out of free tanks or rest liquid. Sounds greedy. Will this yield an optimum? More examples needed.
Update: The greedy approach fails. It allocates a tank with the $1$l (total allocation $16$) while it should not and wait for the next round of allocation to reach an optimimum of $17$.
First try:
The equations for the $m$ liquid rests $r_i$ of the liquid $A_i$ could be modeled as: $$ \left\{ \begin{align} r_1 =& A_1 - (k_{11} x_1 + k_{12} x_2 + \cdots + k_{1n} x_n) \\ r_2 =& A_2 - (k_{21} x_1 + k_{22} x_2 + \cdots + k_{2n} x_n) \\ \vdots & \\ r_m =& A_m - (k_{m1} x_1 + k_{m2} x_2 + \cdots + k_{mn} x_n) \end{align} \right. $$ where each column vector of the matrix $k$ has at most one component with value $1$ and its other components have value $0$.
A non-zero matrix element $k_{ij}$ means fill tank $x_j$, and fill it with liquid from $A_i$. So this allows only tank fills from one source. It also means that tanks are either filled not at all or fully.
This means we have $n$ times $m+1$ choices to not place the $1$ at all or place it into the particular columns vector of $k$.
Constraints seem to be: \begin{align} r_i & \ge 0 \quad (?) \\ A_i &> 0 \\ k_{ij} &\in \{0, 1\} \\ x_i &> 0 \quad (?) \\ \end{align}
Optimization goal and objective function might be: $$ \min_{k} r(k) $$ where \begin{align} r(k) &= \sum_{i=1}^m r_i \\ &= \sum_{i=1}^m \left( A_i - \sum_{j=1}^n k_{ij} x_j \right) \\ &= \sum_{i=1}^m A_i - \sum_{i=1}^m \sum_{j=1}^n k_{ij} x_j \\ \end{align}
which is equivalent to $$ \max_k x(k) $$ for $$ x(k) = \sum_{i=1}^m \sum_{j=1}^n k_{ij} x_j $$
Result
The above problem can be formulated as integer linear program (ILP) $$ \begin{array}{ll} \max & c^\top k \\ \mbox{w.r.t.} & c^\top k \le a \\ & \alpha_1^\top k \le 1 \\ & \quad \vdots \\ & \alpha_n^\top k \le 1 \\ & k_{ij} \in \{ 0, 1 \} \end{array} $$ in $mn$ unknowns $k_{ij}$ rearranged as vector $$ k = (k_{11}, \ldots k_{m1}, \ldots, k_{1n} \ldots k_{mn})^\top $$ with cost vector $c \in \mathbb{R}^{mn}$: $$ c = (\underbrace{x_1, \ldots, x_1}_{m \times}, \ldots, \underbrace{x_n, \ldots, x_n}_{m \times})^\top $$ constraint parameter $a \in \mathbb{R}$ with $$ a = \sum_{i=1}^m A_i $$ and the $n$ constraints $\alpha_j$ on the columns of the $k$-matrix: $$ \alpha_j = (0,\cdots 0, \underbrace{1 \cdots 1}_{m \times}, 0 \cdots 0)^\top $$ where for the $j$-th constraint vector $\alpha_j$ the $1$ values are from component $1 + (j-1) m$ to $m + (j-1) m$.
Instances of the above problem can be solved with many available lp solvers, e.g. see lpsolve docs.
Example:
The problem
$$ x = (5, 5, 10)^\top \\ A = (1, 7, 10)^\top $$
led to this solution with lpsolve: $$ k = \left( \begin{matrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 1 & 0 & 0 \end{matrix} \right) $$ This means
What is wrong is that $x_3$ accounted for its full volume of $10$l while it got only $1$l. This is an error in the model.
It could have been prevented by enforcing that $k_{ij} = 0$ if $x_j > A_i$. This can be determined before optimization and should lead to drop that $k_{ij}$ from the variables or (maybe simpler) to add a constraint $\delta_{ij}^\top k = 0$ to enforce $k_{ij} = 0$.
In case of the example this leads to four additional constraints:
and a new solution
$$ k = \left( \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 0 \end{matrix} \right) $$
which means
Ouch, again wrong. Only $7+5=12l$ were poured.
The objective function must be modified into $$ x(k) = \sum_{i=1}^m \sum_{j=1}^n k_{ij} \min(A_i, x_j) $$
And we have to think about additional rounds to deal with the left-overs $A' = (1,0,5)$.
And we get rid of the last four constraints.
This gives
$$ k = \left( \begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 1 & 0 & 1 \end{matrix} \right) $$
which means
Again a modeling error, we can not pour $15$l from the $10$l in $A_3$.
Tricky. Adding constraints on the rows of $k$ so only one $1$ is allowed would mean that we allow at most one pour from a liquid into atmost one tank.
And we do not need the constraint $c^\top k \le a$ anymore, as we can not exceed $a$.
$$ k = \left( \begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix} \right) $$
which means
That looks better. But this problem might be farther from the original problem.
Result 2:
$$ \begin{array}{ll} \max & c^\top k \\ \mbox{w.r.t.} & \alpha_1^\top k \le 1 \\ & \quad \vdots \\ & \alpha_n^\top k \le 1 \\ & \beta_1^\top k \le 1 \\ & \quad \vdots \\ & \beta_m^\top k \le 1 \\ & k_{ij} \in \{ 0, 1 \} \end{array} $$ in $mn$ unknowns $k_{ij}$ rearranged as vector $$ k = (k_{11}, \ldots k_{m1}, \ldots, k_{1n} \ldots k_{mn})^\top $$ with cost vector $c \in \mathbb{R}^{mn}$: $$ c = (\underbrace{\min(A_1,x_1), \ldots, \min(A_m,x_1)}_{m}, \ldots, \underbrace{\min(A_1,x_n), \ldots, \min(A_m,x_n)}_{m})^\top $$ the $n$ constraints $\alpha_j$ on the columns of the $k$-matrix: $$ \alpha_j = (0,\cdots 0, \underbrace{1 \cdots 1}_{m \times}, 0 \cdots 0)^\top $$ where for the $j$-th constraint vector $\alpha_j$ the $1$ values are from component $1 + (j-1) m$ to $m + (j-1) m$.
And the $m$ constraints $\beta_i$ on the rows of the $k$-matrix: $$ \beta_1 = (\underbrace{1, 0, \cdots, 0}_{m}, \underbrace{1, 0, \cdots, 0}_{m}, \underbrace{1, 0, \cdots, 0}_{m})^\top \\ \beta_2 = (\underbrace{0, 1, 0, \cdots, 0}_{m}, \underbrace{0, 1, 0, \cdots, 0}_{m}, \underbrace{0, 1, 0, \cdots, 0}_{m})^\top \\ \vdots $$
where for the $i$-th constraint vector $\beta_i$ the $1$ values are at component $q m + i$ for $q \in \{ 0, \ldots, n-1 \}$.
Interpretation of the above model:
$t=\min(m,n)$ of the $m$ liquids are selected for $t$ of the $n$ tanks. A pour is attempted each.
$k_{ij} = 1$ means: Of the liquid $A_i$ there will be $\min(A_i, x_j)$ litres poured into tank $x_j$.
Several Rounds:
One might interpret the above procedure as one round of several.
For the example we started with $$ x = (5,5,10)^\top \quad A = (1, 7, 10) $$ and ended up with rest capacities and liquids $$ x' = (4, 0, 0)^\top \quad A' = (0, 2, 0) $$ Also all tanks are used, there are no free tanks anymore, so we have to stop. Another stop condition would be that no liquid is available anymore.