Constrained clustering for data assignment problems with examples of module placement

We present a new approach to the class of optimization problems known'as data assignment problems, viewing them in the context of constrained clustering. The clustering algorithm we apply, an extension of the deterministic annealing method which incorporates clustering constraints, initially generates "soft" data assignments, then reduces the fuzziness of these assignments by lowering an effective temperature. In the low temperature limit, we obtain a legal data assignment solution which seeks to minimize the desired objective function. The gradual reduction of temperature allows the method to avoid some local minima which plague conventional descent methods. We implement our method on the two-dimensional module placement problem. For the minimum squared wire length objective, our algorithm is demonstrated to outperform several other methods on module placement examples from the literature.