Combinatorial optimization problem

Question

I'm having trouble writing a general algorithm for what at first glance appears to be a simple problem.

If I have a volume $V_{required}$ that can be made from two smaller, different volumes how can I decide which volumes to use to get the minimum wastage? Some examples:

If $V_{required} =300$ and my smaller volumes are $V_1=60$ and $V_2=150$, one would use $2V_2$.

If $V_{required}=240$, then one would use $4V_1$.

If $V_{required}=330$ one would use $3V_1+V_2$.

Finally if $V_{required}=250$ one would use $2V_1+V_2$ with $20$ units wastage.

Is there a way to decide on the best combination for a given volume and two smaller, given volumes for the general case, minimizing wastage? Thanks.

Answer 1

I suppose that this problem corresponds to integer programming (http://en.wikipedia.org/wiki/Integer_programming).

As Gerry Myerson commented, for two volumes, the number of solutions is quite limited, so let us consider it with $p$ volumes.

Call $n_i$ the number of times volume $V_i$ should be used and $V_{required}$ the required volume. So, the waste $W$ is $$W=\sum_{i=1}^p n_i V_i-V_{required}$$ I then suppose that we could define an objective function $$\Phi(n_1,n_2,\cdots,n_p)=\Big(\sum_{i=1}^p n_i V_i-V_{required}\Big)^2$$ we need to minimize subject to bound constraints $0\leq n_i\leq \frac {V_{required}}{V_i}$, and a linear constraint $W\geq0$.