2
$\begingroup$

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$

$\endgroup$
  • 2
    $\begingroup$ Please use $\mathsf{\LaTeX}$ syntax for math. $\endgroup$ – Jeffε Nov 16 '12 at 17:40
  • $\begingroup$ @je: Oh, thx. I was wondering why $\LaTeX$ didn't work… (was using code blocks) $\endgroup$ – comonad Nov 16 '12 at 18:08
  • $\begingroup$ 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. $\endgroup$ – Suresh Venkat Nov 28 '12 at 17:48
  • 1
    $\begingroup$ @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. $\endgroup$ – Marzio De Biasi Nov 28 '12 at 17:57
  • 1
    $\begingroup$ @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). $\endgroup$ – Marzio De Biasi Nov 29 '12 at 13:11
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – comonad Nov 29 '12 at 15:19
  • $\begingroup$ Have you looked at adapting any of the standard heuristics for bin packing ? $\endgroup$ – Suresh Venkat Nov 29 '12 at 18:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.