A reduction technique for weighted grouping problems

A reduction technique for weighted grouping problems

0.00 Avg rating0 Votes
Article ID: iaor20031375
Country: Netherlands
Volume: 140
Issue: 3
Start Page Number: 590
End Page Number: 605
Publication Date: Aug 2002
Journal: European Journal of Operational Research
Authors: ,
Keywords: combinatorial analysis
Abstract:

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.

Reviews

Required fields are marked *. Your email address will not be published.