HEC Montréal, Canada, 2 - 4 mai 2011

Journées de l'optimisation 2011

HEC Montréal, Canada, 2 — 4 mai 2011

Horaire Auteurs Mon horaire
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TC10 Classification / Clustering

3 mai 2011 15h30 – 17h10

Salle: Van Houtte

Présidée par Sylvain Perron

4 présentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h30 - 15h55

    A Column Generation Approach to the Capacitated Centered Clustering Problem

    • Marcos Antonio Pereira, prés., 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    15h55 - 16h20

    A Clustering Problem with Capacity and Side Constraints

    • Marcello Sammarra, prés., 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h20 - 16h45

    Clustering Using Several Diameter Criteria

    • Nicolas Grebille, prés., 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    16h45 - 17h10

    Exact Normalized Cut Clustering by Column Generation

    • Sylvain Perron, prés., 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.