patternMinor
Help wrapping my head around a combinatorial optimization problem
Viewed 0 times
aroundproblemheadhelpcombinatorialoptimizationwrapping
Problem
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.
Knowing a specific name for this class of problem would be a good start. Help formalizing it would be even better. I did this stuff so long ago in school, I need my memory jogged good and hard. Thanks!
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.
Knowing a specific name for this class of problem would be a good start. Help formalizing it would be even better. I did this stuff so long ago in school, I need my memory jogged good and hard. Thanks!
Solution
Here is a complete MIP (Mixed Integer Programming) model that should do the trick. I just use some random data (weights) with 100 widgets and 50 possible bins. When solved the variable NumUsedBins gives the maximum number of bins and the variable x gives the assignment. The equation 'order' is to make sure we use lower numbered bins first. The strange statement about optcr is to tell the solver to solve to optimality (for very difficult problems you may want to stop at 5% or so).
With 1000 widgets this becomes somewhat difficult to solve to optimality.
With 1000 widgets this becomes somewhat difficult to solve to optimality.
Context
StackExchange Computer Science Q#48510, answer score: 3
Revisions (0)
No revisions yet.