HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Help wrapping my head around a combinatorial optimization problem

Submitted by: @import:stackexchange-cs··
0
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!

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.

Context

StackExchange Computer Science Q#48510, answer score: 3

Revisions (0)

No revisions yet.