Groupe d’études et de recherche en analyse des décisions

G-2010-44

Binary Clustering Problems: Symmetric, Asymmetric and Decomposition Formulations

et

In this paper, we generalize the Asymmetric Representatives Formulation, which was first introduced by Campêlo et al. (2008) for the Node Coloring Problem. The main idea from this formulation can be used to model a variety of Binary Clustering Problems. The new asymmetric decision variables indicate if an object belongs to a specific cluster, but the cluster is identified by the lowest indexed object. The advantage of this formulation is that it eliminates the symmetry between the clusters which exists in the classical formulation. We prove that the LP relaxation bound of the Asymmetric Representatives Formulation is at least as good as the one from the classical Symmetric Formulation. We further show that applying Dantzig-Wolfe decomposition to the classical Symmetric Formulation or to the Asymmetric Representatives Formulation leads to the same symmetry-breaking model, and hence the same LP bound that can be much stronger. Finally, we show that in specific cases, the LP relaxation bound of the Asymmetric Representatives Formulation depends on the order of the input data.

, 21 pages