<p>Perhaps the corresponding decision problem is NP-complete; given an instance of SUBSET-SUM:</p>

<p>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$?</p>

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

<p>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.</p>

CC BY-SA 3.0
2012-11-29T15:19:03.340Z
Yes, perhaps. "Perfect"-BinPack is already NP-complete, and if I remember correctly, "Optimal"-BinPack (with no perfect Solution) is NP-hard; both can be reduced to this problem, so this is at least NP-hard. But I do not know how to reduce this problem to any known problem in a useful/practical way.
comonad
CC BY-SA 3.0
2012-11-29T18:33:13.290Z
Have you looked at adapting any of the standard heuristics for bin packing ?
Suresh Venkat
CC BY-SA 3.0
2012-11-28T18:45:16.583Z
2012-11-28T18:45:16.583Z
Marzio De Biasi
<p>I have a special variant of BinPack problem.
Does anyone know <strong>how to reduce this problem</strong> to something known?</p>

<hr>

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

<p>$|I| ∈ ℕ, |B| ∈ ℕ$</p>

<p>$s : (I ∪ B) → ℕ$</p>

<p>The sum of all item-sizes is <strong>not less than</strong> the sum of all bin-sizes.</p>

<p>$∑ _{i∈I} s(i) ≥ ∑ _{b∈B} s(b)$</p>

<p>Each bin has to be filled with items or <strong>parts of items</strong> 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.</p>

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

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

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

<p>The goal is to minimize the <strong>number of item-parts</strong> used to fill all bins.</p>

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

<p>$minimize\ numparts$</p>

<hr>

<p>Example 1:</p>

<p>$I=[100,5]$</p>

<p>$B=[10,10,7]$</p>

<p>$allparts=[10,10,7,73,5]$ after partitioning the first item</p>

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

<p>$numparts=3$</p>

<hr>

<p>Example 2:</p>

<p>$I=[8,14,5]$</p>

<p>$B=[10,10,7]$</p>

<p>$allparts=[8,10,2,2,5]$ after partitioning the second item</p>

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

<p>$numparts=5$</p>

CC BY-SA 3.0
2012-11-16T17:40:24.910Z
Please use $\mathsf{\LaTeX}$ syntax for math.
Jeffε
CC BY-SA 3.0
2012-11-16T18:08:13.560Z
@je: Oh, thx. I was wondering why $\LaTeX$ didn't work… (was using code blocks)
comonad
CC BY-SA 3.0
2012-11-28T17:48:34.427Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-11-28T17:57:32.047Z
@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.
Marzio De Biasi
CC BY-SA 3.0
2012-11-28T19:04:32.800Z
that may be, but the constraint as written still allows for my "trivial" solution that is clearly not what's intended. I actually think the total size of all items should be at most the total size of all bins, and for each bin, the parts of items allocated to it should NOT exceed the bin size.
Suresh Venkat
CC BY-SA 3.0
2012-11-29T13:11:10.047Z
@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).
Marzio De Biasi
CC BY-SA 3.0
2012-11-29T15:06:57.197Z
@SureshVenkat: "The sum of all item-sizes *is* not less than the sum of all bin-sizes." that is already given. "*Each* bin *has to be* filled with items or parts of items so that it is filled completely." that is a condition which the solution must have. If you stack all items, the number of used item-parts equals the number of items, which is not always optimal, because you stacked more items than needed.
comonad
CC BY-SA 3.0
2012-11-29T18:32:26.610Z
Ah so you're allowed to throw out item parts, but you must fill the bins. I think I get it now.
Suresh Venkat
<ds.algorithms><approximation-algorithms><packing>
How can I reduce this kind of BinPack algorithm? ("MinBreak-BinFill")
comonad
# How can I reduce this kind of BinPack algorithm? ("MinBreak-BinFill")

(Asked by: username_0 on 2012-11-16)

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$

**Tags:** ds.algorithms, approximation-algorithms, packing
> **Comments:**
> **username_1**: Please use $\mathsf{\LaTeX}$ syntax for math.  
> **username_0**: @je: Oh, thx. I was wondering why $\LaTeX$ didn't work… (was using code blocks)  
> **username_2**: 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.  
> **username_3**: @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.  
> **username_2**: that may be, but the constraint as written still allows for my "trivial" solution that is clearly not what's intended. I actually think the total size of all items should be at most the total size of all bins, and for each bin, the parts of items allocated to it should NOT exceed the bin size.  
> **username_3**: @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).  
> **username_0**: @SureshVenkat: "The sum of all item-sizes *is* not less than the sum of all bin-sizes." that is already given. "*Each* bin *has to be* filled with items or parts of items so that it is filled completely." that is a condition which the solution must have. If you stack all items, the number of used item-parts equals the number of items, which is not always optimal, because you stacked more items than needed.  
> **username_2**: Ah so you're allowed to throw out item parts, but you must fill the bins. I think I get it now.  

---

## 1 answers

### Answer by username_3 on 2012-11-28. Score: 1

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 > 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.

> **Comments:**
> **username_0**: Yes, perhaps. "Perfect"-BinPack is already NP-complete, and if I remember correctly, "Optimal"-BinPack (with no perfect Solution) is NP-hard; both can be reduced to this problem, so this is at least NP-hard. But I do not know how to reduce this problem to any known problem in a useful/practical way.  
> **username_2**: Have you looked at adapting any of the standard heuristics for bin packing ?  

---

