HEC Montréal, Canada, May 2  4, 2011
2011 Optimization Days
HEC Montréal, Canada, 2 — 4 May 2011
TC10 Classification / Clustering
May 3, 2011 03:30 PM – 05:10 PM
Location: Van Houtte
Chaired by Sylvain Perron
4 Presentations

03:30 PM  03:55 PM
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.

03:55 PM  04:20 PM
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.

04:20 PM  04:45 PM
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.

04:45 PM  05:10 PM
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.