A new Bin-packing?

Question

I'm looking in to a kind-of bin-packing problem, but not quite the same. The problem asks to put n items into minimum number of bins without total weight exceeding capacity of bins. (classical definition)

The difference is: Each item has a weight and bound, and the capacity of the bin is dynamically determined by the minimum bound of items in that bin.

E.g., I have four items A[11,12], B[1,10], C[3,4], D[20,22] ([weight,bound]). Now, if I put item A into a bin, call it b1, then the capacity of b1 become 12. Now I try to put item B into b1, but failed because the total weight is 11+1 =12, and the capacity of b1 become 10, which is smaller than total weight. So, B is put into bin b2, whose capacity become 10. Now, put item C into b2, because the total weight is 1+3 =4, and the capacity of b2 become 4.

I don't know whether this question has been solved in some areas with some name. Or it is a variant of bin-packing that has been discussed somewhere. I don't know whether this is the right place to post the question, any helps are appreciated!

Answer 1

Usually with algorithm design for NP-hard problems, it's necessary to reuse techniques rather than whole algorithms. Here, the algorithms for standard bin packing that use branch-and-bound with column generation carry over well.

The idea is that we formulate an enormous set cover instance where the sets are the sets of items that fit into a single bin. Integer programming is a good technique for normal set cover, but there are so many sets that we need to do something else, i.e., column generation. There is a one-to-one correspondence between sets and columns, so we rip out the part of the linear programming solver that uses brute force to find a good column to enter and replace it with a solver for what turns out to be the knapsack analog of this problem.

This modified knapsack problem is, given items with weights, profits, and bounds, find the most profitable set of items whose total weight is less than the minimum bound. The dynamic program for solving knapsack with small integer weights happily transfers over with no loss of efficiency. Just sort the items by descending bounds; then, when forming sets involving the most recent item, the weight limit is just that item's bound.

Answer 2

First of all i might be totally wrong and there might exist an algorithm that is even better than mine.

Bin packing is NP-hard and is efficiently solved using classic algorithms like First Fit etc.There are some improvements to this too.Korf's algorithm

I aim to reduce this to normal bin packing by sorting the items by thier bound.The steps are

1. Sort items by bound :Sorting items by bound will help us in arranging the bins as limiting condition is minimum of bound.

2. Insert smallest item(by bound) into a bin

3. Check whether the next item(sorted by bound) can coexist in this bin.If it can then keep the item in the bin too.If not then try putting it in another bin or create another bin for it.
4. Repeat the procedure till all elements are arranged. The procedure is repeated in ascending order of bounds.

I think this pretty much solves the problem.Please inform me if it doesn't.I am trying to implement the same.And if there are any suggestions or improvements inform me that too. :) Thank you

Answer 3

The following is based on Anony-mouse's answer. I am not an algorithm expert, so consider the following as "just my two cents", for what they are worth.

I think Anony-mouse is correct in starting with the smallest items (by bound). This is because a bin tends to get smaller in capacity the more items you add to it; a bin's maximum capacity is determined with the first item placed in it, it can never get larger after that point.

So instead of starting with a large bin and have its capacity slowly reduced, and having to worry about taking out too-large items that previously fit, let's jut try to keep bins' capacities as constant as possible. If we can keep the bins' capacities stable, we can use "standard" algorithms that know nothing about "bound".

So I'd suggest this:

1. Group all items by bound.

   This will allow you to use a standard bin packing algorithm per group because if all items have the same bound (i.e. bound is constant), it can essentially be disregarded. All that the bound means now is that you know the resulting bins' capacity in advance.

2. Start with the group with the smallest bound and perform a standard bin packing for its items.

   This will result in 1 or more bins that have a capacity equal to the bound of all items in them.

3. Proceed with the item group having the next-larger bound. See if there are any items that could still be put in an already existing bin (i.e. a bin produced by the previous steps).

   Note that bound can again be ignored; since all pre-existing bins already have a smaller capacity than these additional items' bound, the bins' capacity cannot be affected; only weight is relevant, so you can use "standard" algorithms.

   I suspect this step is an instance of the (multiple) knapsack problem, so look towards knapsack algorithms to determine how to distribute these items over and into the pre-existing, partially filled bins.

4. It's possible that the item group from the previous group has only been partially processed, there might be items left. These will go into one or more new bins: Basically, repeat step 3.

5. Repeat the above steps (from 3 onwards) until no more items are left.

Answer 4

It can still be written as an ILP instance, like so:

Make a binary variable x_{i,j} signifying whether item j goes into bin i, helper variables y_i that signify whether bin i is used, helper variables c_i that determine the capacity of bin i, and there are constants s_j (size of item j) b_j (bound of item j) and M (a large enough constant), now

minimize sum[j] y_j

subject to:
1:   for all j:
         (sum[i] x_{i,j}) = 1
2:   for all i,j:
         y_i ≥ x_{i,j}
3:   for all i:
         (sum[j] s_j * x_{i,j}) ≤ c_i
4:   for all i,j:
         c_i ≤ b_j + (M - M * x_{i,j})
5:   x_{i,j} ϵ {0,1}
6:   y_i ϵ {0,1}

The constraints mean

1. any item is in exactly one bin
2. if an item is in a bin, then that bin is used
3. the items in a bin do not exceed the capacity of that bin
4. the capacity of a bin is no more than the lowest bound of the items that are in it (the thing with the big M prevents items that are not in the bin from changing the capacity, provided you choose M no less than the highest bound)
5. and 6., variables are binary.

But the integrality gap can be atrocious.