A reduction technique for weighted grouping problems

Weighted grouping problems are shown to have an equivalent reduced form, which is often considerably smaller than the original problem. Although the reduction may be small for randomly generated problems, real-life probelms often contain non-random properties that greatly increase the effect of reduction. We give an efficient algorithm to build the reduced problem instance, and analyse the expected amount of reduction for certain statistical distributions and real-life data. In addition, we briefly discuss the effect of reduction on traditional solving methods of the grouping problem. The results show clearly the usefulness of problem reduction: it is computationally cheap to apply and may make the reduced problem solvable in a practical time whilst the original one is not. The method is readily applicable to the job grouping problem of printed circuit board printing industry.