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:
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.
No comments:
Post a Comment