[Solved]: Help wrapping my head around a combinatorial optimization problem

Problem Detail: 

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!

Asked By : JCL

Answered By : D.W.

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/48510

3.2K people like this

 Download Related Notes/Documents