How can I reduce this kind of BinPack algorithm? ("MinBreak-BinFill") I have a special variant of BinPack problem.
Does anyone know how to reduce this problem to something known?



The problem:
There are items $I$ and bins $B$ in specific quantity and size.

$|I| ∈ ℕ, |B| ∈ ℕ$

$s : (I ∪ B) → ℕ$

The sum of all item-sizes is not less than the sum of all bin-sizes.

$∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)$

Each bin has to be filled with items or parts of items so that it is filled completely. $s(b,i)$ is the size of that part of $i$ that is in $b$, or $0$ iff not.

$∀ b ∈ B, i ∈ I: s(b,i) ∈ ℕ ∪ \{0\}$

$∀ i ∈ I: ∑ _{b∈B} s(b,i) ≤ s(i)$

$∀ b ∈ B: ∑ _{i∈I} s(b,i) ≥ s(b)$

The goal is to minimize the number of item-parts used to fill all bins.

$numparts = |\{ (b,i) ∈ B×I\ |\ s(b,i)&gt;0 \}|$

$minimize\ numparts$



Example 1:

$I=[100,5]$

$B=[10,10,7]$

$allparts=[10,10,7,73,5]$ after partitioning the first item

$usedparts=[10,10,7]$ because we do not need the other parts anymore

$numparts=3$



Example 2:

$I=[8,14,5]$

$B=[10,10,7]$

$allparts=[8,10,2,2,5]$ after partitioning the second item

$usedparts=[8,2,10,5,2]$ because we need all to fill the bins

$numparts=5$
Perhaps the corresponding decision problem is NP-complete; given an instance of SUBSET-SUM:

Given $K, x_1,...,x_n$ does exist $A \subseteq \{x_1, x_2, ..., x_n\}$ s.t. $\sum_{x_i \in A}x_i = K$?

Suppose that $k &gt; 0, x_i &gt; 0$ and let $k' = \sum_{i=1..n} x_i - K$

Now, if you pick two bins $B_1, B_2$ with sizes $k$ and $k'$, then $n$ items of sizes $x_i$ can be packed with cost $numparts = n$ if and only if the corrsponding SUBSET-SUM problem has a solution.