Optimal way to pour cups of water into buckets

63 Views Asked by At

Say that I have $n$ cups and that the $i$-th cup contains $c_i$ ml of water, where $c_i$ is some non-negative but not necessarily integer number. Also denote the total volume of water as: $V=\sum_i^n c_i$.

I want to pour the cups to fill $m$ buckets with water so that the $j$-th bucket contains a target volume of $b_j$ ml of water. Again, $b_j$ is some non-negative but not necessarily integer number and $m$ can be smaller, equal or larger than $n$. It is also $V=\sum_i^m b_i$. I can't split the water from a cup into multiple buckets, I can though use multiple cups to fill a single bucket. After I pour the cups, I denote the volume of water in the $j$-th bucket as $b_j'$.

I want to pour the cups into the buckets in such a way so that I minimize the mean square error $MSE = \sum_j^m (b_j-b_j')^2$. Is there any way of solving this minimization problem, other than combinatorially?

To give an example, say that the cups each contain the following volumes of water:

$c_1 = 3, ~c_2 = 2, ~c_3 = 4, ~c_4 = 1, ~c_5 = 8$

And I want the buckets to fill with the following volumes of water:

$b_1 = 3.6, ~b_2 = 1.8, ~b_3 = 12.6$

One way to do that is to pour the 3rd cup into the 1st bucket, the 2nd cup into the 2nd bucket and cups 1, 4 & 5 into the 3rd bucket. Then the buckets fill with the following volumes of water:

$b_1'=4, ~b_2' = 2, ~b_3' = 3+1+8=12$

The MSE then is: $MSE = (4-3.6)^2 + (2-1.8)^2 + (12-12.6)^2 = 0.56$

1

There are 1 best solutions below

0
On BEST ANSWER

You can solve the problem via integer programming as follows. Let binary decision variable $x_{i,j}$ indicate whether cup $i$ is assigned to bucket $j$. The problem is to minimize $$\sum_{j=1}^m \left(\sum_{i=1}^n c_i x_{i,j} - b_j\right)^2$$ subject to linear constraints $$\sum_{j=1}^m x_{i,j} = 1 \quad \text{for $i\in\{1,\dots,n\}$} \tag1$$ that enforce the assignment of each cup to exactly one bucket.

You can call an integer quadratic programming solver directly or linearize the objective and call an integer linear programming solver. One way to linearize is to expand the square, replace each $x_{i,j}^2$ with $x_{i,j}$, and introduce a new variable $y_{i,i',j} \ge 0$ for $i<i'$ and all $j$ to represent the product $x_{i,j} x_{i',j}$, together with linear constraints \begin{align} y_{i,i',j} &\le x_{i,j} \tag2\\ y_{i,i',j} &\le x_{i',j} \tag3\\ y_{i,i',j} &\ge x_{i,j} + x_{i',j} - 1 \tag4 \end{align} The resulting linear objective is to minimize $$\sum_{j=1}^m \left(\sum_{i=1}^n c_i^2 x_{i,j} + 2\sum_{1 \le i < i' \le n} c_i c_{i'} y_{i,i',j} - 2 b_j \sum_{i=1}^n c_i x_{i,j} + b_j^2\right)$$

Your example solution is optimal.


When $c_i \ge 0$ for all $i$, you can omit constraints $(2)$ and $(3)$, which will naturally be satisfied at optimality.