Help wrapping my head around a combinatorial optimization problem

Question

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!

Answer 1

I recommend you use an integer linear programming (ILP) solver to approach this. It will be relatively easy to code this up, and the resulting solution will probably out-perform any other simple scheme I can think of.

Let $w_1,\dots,w_n$ be the (known) weights of your $n$ widgets. Let $t$ be the required minimum weight of each group. We're going to test whether it's possible to partition those $n$ widgets into $m$ groups, so that each group weighs at least $t$.

Here's how. Introduce zero-or-one variables $x_{i,j}$. The intended meaning is that $x_{i,j}=1$ means that widget $i$ is placed into group $j$. Add the following constraints:

• $\sum_j x_{i,j}=1$ for each $i$ (each widget can be placed in exactly one group).

• $\sum_i w_i x_{i,j} \ge t$ for each $j$ (each group weighs at least $t$).

Now ask the solver whether the combination of these inequalities is feasible. If the ILP solver finds a feasible solution, then you know it is possible to partition the widgets into $m$ groups. If it says the problem is infeasible, you know it's not possible to partition the widgets into $m$ groups.

Now use binary search to find the largest value of $m$ for which a feasible solution exists.

Of course, your problem is a NP-hard problem, so you shouldn't expect an efficient solution that works for all parameters -- but you might find that the ILP-based solution works well enough for your problem.

---

Incidentally, you mention that a typical problem instance would have "1000 widgets, [with] weights ranging from 2-4 oz in .05 oz increments". This means that there are only 40 possible weights, so while you have 1000 widgets, there are effectively only 40 different types of widgets.

This kind of situation allows a more efficient solution. It is possible to adjust the above algorithm to handle this situation. Let $w_1,\dots,w_n$ be the weights of the $n$ types of widgets, and let $q_1,\dots,q_n$ be the quantities of each type of widgets (i.e., you have $q_i$ widgets of weight $w_i$).

Now you can use integer variables $x_{i,j}$ that are not zero-or-one, but are constrained to be integers in the range $0 \le x_{i,j} \le q_i$. The intended meaning of $x_{i,j}$ is that it counts the number of widgets of type $i$ that are placed into group $j$. You introduce the constraints

• $\sum_j x_{i,j} = q_i$, and

• $\sum_i w_i x_{i,j} \ge t$.

Everything proceeds as before. In this way, the number of variables fed to the ILP solver is greatly reduced, which will likely make the solving process a lot more efficient. I definitely recommend applying this optimization, if you want to solve the problem in practice.

Answer 2

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.

Answer 3

The first thing I would do in order to solve this question is simplify it into a smaller problem: You have the weights and the min-weight requirement. Now try to match 2 weights in order to reach exactly the min-weight. My approach:

1. Store every number inside a set.
2. For each number a calculate - ( a - mid_weight ) = b. Then check if the set already has the number b in it.

Now in the second scenario the pairs don't have to exactly match the min-weight. My approach would be:

1. Store every number inside a set.
2. For each number a calculate its optimal partner - ( a - mid_weight ) = b. Then check the closest element matching b inside the set. In C++ you can find both partners (the partner lower to b and higher to b) using std::set::lower_bounds and std::set::higher_bounds.
3. Sort all the matching pairs according to their waisted weight from lower to higher: a + b - min-weight = wasted-weight. Then always choose the best pair and reevaluate any new pairs that had a or b as partner.

This is only a quick attempt at your problem, i'm not sure if it's optimal. You have to do the general case. For a similar problem look up 3sum (or 4sum). I hoped this helped a little bit at least.