4 Presentations

• 
  03:30 PM - 03:55 PM

  A Column Generation Approach to the Capacitated Centered Clustering Problem

  • Marcos Antonio Pereira, presenter, Universidade Estadual Paulista
  • Edson Luiz França Senne, Universidade Estadual Paulista
  • Jacques Desrosiers, GERAD, HEC Montréal
  • Luiz Antonio Nogueira Lorena, Instituto Nacional de Pesquisas Espaciais

  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 p-median 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

  • Marcello Sammarra, presenter, High Performance Computing and Networking Institute of the Italian National Research Council
  • M. Flavia Monaco, Department of Electronics, Computer Science and Systems of the University of Calabria

  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

  • Nicolas Grebille, presenter, GERAD
  • Sylvain Perron, GERAD, HEC Montréal
  • Pierre Hansen, HEC Montréal
  • Gilles Caporossi, GERAD, HEC Montréal

  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

  • Sylvain Perron, presenter, GERAD, HEC Montréal
  • Pierre Hansen, HEC Montréal
  • Gilles Caporossi, GERAD, HEC Montréal

  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.