# 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)>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$

• Please use $\mathsf{\LaTeX}$ syntax for math. Nov 16, 2012 at 17:40
• @je: Oh, thx. I was wondering why $\LaTeX$ didn't work… (was using code blocks) Nov 16, 2012 at 18:08
• I'm confused about your constraints. If I'm allowed to exceed the bin size (the last inequality) my solution is to stack all items in one "bin" which gives numparts = |I| which is clearly optimal. Nov 28, 2012 at 17:48
• @SureshVenkat: I think that the OP means that the total size of the items is greater than the total size of the bins, so we can always fill them completely; and the goal is to minimize the number of items that must be broken to fill them completely. Nov 28, 2012 at 17:57
• @SureshVenkat: but suppose that there are 4 items of sizes $\{2,3,5,7\}$, and two bins of sizes $\{8,8\}$ then if you stack all the items on the first bin, the second one remains empty (and the last condition is not satisfied). Nov 29, 2012 at 13:11

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 > 0, x_i > 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.