Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

up vote 1 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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