# Allocate items to an unknown number of resources

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

-
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. –  Libra Apr 26 '12 at 10:10
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! –  Dan Brumleve Apr 26 '12 at 10:16