Tuesday, December 1, 2015

Bin Packing but different

From http://cs.stackexchange.com/questions/48510/help-wrapping-my-head-around-a-combinatorial-optimization-problem/50179#50179:

Here's the problem I'm trying to solve:

I have a bunch of widgets, whose weights vary over a small range. I would like to find the optimal grouping of them such that each group meets a minimum weight requirement, while maximizing the total number of groups I can form.

My solution:

image

The order equation is interesting: it is a symmetry breaking constraint but also improves how the solution looks: start with assigning to lower numbered bins.

An even more interesting question is: do we need equation UnusedBin? If we are just interested in the maximum number of bins we can fill-up then no. But if we want to prevent some lingering widget j to be assigned to an unused bin then we should include it. I decided to include it in my answer on StackExchange as the solution is easier to interpret.

With 1000 widgets things become large and difficult.  Is is noted further that:

Let's say we have 1000 widgets, weights ranging from 2-4 oz in .05 oz increments, and the minimum weight requirement for all groups is 8 oz

Indeed one poster added that this means there are just 40 possible weights. How to exploit that is an interesting question. I probably would look at some column generation approach similar to some cutting stock examples.