4
$\begingroup$

I have this problem that I want to understand how to model as a mathematical program: there is a set $N$ of $n$ items; each item has a known weight $w_i$. I have bags of equal capacity $W$. I want to determine the minimum number of bags that can contain all the items in $N$.

I don't know how to deal with this situation where I have to allocate items to an unknown number (that I have to find out) of resources (bags), therefore my overly simplistic approach would be as follow:

  • assume a set $B$ of $n$ bags (i.e. assume the availability of one bag per item)

  • define the binary variable $x_{ij}$ = 1 if item $i \in N$ is allocated to bag $j \in B$, and 0 otherwise

  • set the objective function: $\min\sum_{i \in N, j \in B} x_{ij} $

subject to:

$\sum_{j \in B} x_{ij} = 1 \;\; \forall i \in N $ //each item is assigned to exactly one bag

$\sum_{i \in N} w_i \cdot x_{ij} \leq W \;\; \forall j \in B$ //bags' capacity constraint

$x_{ij} \in \{0,1\}$

Is it a correct formulation? At this stage I am not interested in the solution procedure. My question is: is it possible to mathematically model this situation in a more efficient way where I don't have to define the set $B$ a priori? Is it a variant of any known problem (i.e. multiple knapsack?).

Thanks for your hints

Libra

$\endgroup$
2
  • 1
    $\begingroup$ Addendum: If I have well understood, it should be a case of bin packing problem, isn't it?. Nevetheless, I would like to know if there are formulations where the number of bags should not be defined a priori. $\endgroup$
    – Libra
    Commented Apr 26, 2012 at 10:10
  • 1
    $\begingroup$ A priori you can set the number of bags equal to the number of items, since you won't need any more than that. Looks like we both discovered "bin packing" at about the same second, cool! $\endgroup$
    – Dan Brumleve
    Commented Apr 26, 2012 at 10:16

1 Answer 1

Reset to default
2
$\begingroup$

If the capacity is exactly half of the total weight, then the question of whether or not all items can be packed into two bags is equivalent to the partition problem, which is NP-complete. So the general problem is at least as hard.

EDIT: I discovered that this is called the bin packing problem.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .