HEC Montréal, Canada, 2  4 mai 2011
Journées de l'optimisation 2011
HEC Montréal, Canada, 2 — 4 mai 2011
TC10 Classification / Clustering
3 mai 2011 15h30 – 17h10
Salle: Van Houtte
Présidée par Sylvain Perron
4 présentations

15h30  15h55
A Column Generation Approach to the Capacitated Centered Clustering Problem
We propose a column generation based heuristic to calculate approximate solutions to the capacitated centered clustering problem. The proposed approach uses a stabilization technique derived from the lagrangean/surrogate relaxation of the corresponding capacitated pmedian problem. Computational results will be presented to show the effectiveness of the method.

15h55  16h20
A Clustering Problem with Capacity and Side Constraints
A set of weighted items must be grouped into stacks, of given height and weight, such that the weight of the items decreases from the bottom to the top. The assignment costs depend on the position items will have within the stacks. An assignment model with side constraints is investigated.

16h20  16h45
Clustering Using Several Diameter Criteria
We present a short study on two criteria that may be used to partition a subset of points: the diameter criterion, and the sum of diameter criterion. The diameter of a subset is the maximal distance between two of its points; the former criterion minimize the smallest diameter among resulting subsets, and the later the sum of the subset's diameters. We present a graphical comparison of the results obtained with the two criteria and some of their extensions.

16h45  17h10
Exact Normalized Cut Clustering by Column Generation
Clustering addresses the following problem: given a set of entities, find subsets, or clusters, which are homogeneous and/or well separated. Many criteria have been proposed to express homogeneity and/or separation of the clusters. We focus on the normalized cut criterion and present an exact solution method based on the column generation techniques of linear programming applied to a set partitioning formulation of the problem.