2016 Optimization Days

HEC Montréal, Québec, Canada, May 2 — 4, 2016

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

TB4 Clustering

May 3, 2016 03:30 PM – 05:10 PM

Location: Gérard-Parizeau

Chaired by Claudio Contardo

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:30 PM - 03:55 PM

    A hierarchical graph clustering algorithm based on the co-occurrences of nodes following consensus clustering

    • Ghislain Benoit, presenter, HEC Montréal
    • Gilles Caporossi, GERAD, HEC Montréal
    • Sylvain Perron, GERAD, HEC Montréal

    This article works with computational methods used to analyse complex systems in order to identify communities in networks. The proposed algorithm can identify partitions on different scales and down to the core communities of a graph. This is achieved by a hierarchical graph clustering method based on the co-occurrence of nodes in the same community after repeated clustering using the Louvain method. The results are analyzed using both LFR random graphs and classical graph theory examples.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    03:55 PM - 04:20 PM

    An iterative algorithm for the solution of some highly degenerate combinatorial optimization problems: Applications in clustering

    • Daniel Aloise, Universidade Federal do Rio Grande do Norte
    • Claudio Contardo, presenter, GERAD - ESG UQÀM

    We present an iterative algorithm for the solution of some combinatorial optimization problems presenting extremely high degrees of degeneracy. We illustrate the use of our algorithm to solve a classical clustering problem arising in data mining. The newly proposed approach can scale and solve problems two orders of magnitude larger than with the state-of-the-art solver.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:20 PM - 04:45 PM

    Less is more approach: Capacitated clustering problem

    • Jack Brimberg, presenter, GERAD, The Royal Military College of Canada
    • Nenad Mladenovic, Mathematical Institute SANU
    • Raca Todosijevic, LAMIH, Université de Valenciennes et du Hainaut- Cambrésis
    • Dragan Urosevic, Mathematical Institute SANU

    Heuristic search named 'Less is more' has been recently proposed: find the minimum number of ingredients that make some heuristic more efficient than the currently best. It is represented by Variable neighborhood search, where simple neighborhood types are used for both, shaking and local search. This approach is successfully applied in solving Capacitated Clustering Problem.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    04:45 PM - 05:10 PM

    Bi-objective variable neighborhood search for franchise location

    • Antoine Baudouin, presenter, HEC Montréal
    • Gilles Caporossi, GERAD, HEC Montréal
    • Pierre Hansen, HEC Montréal
    • Sylvain Perron, GERAD, HEC Montréal
    • Behnaz Saboonchi, HEC Montréal

    We present a bi-objective model for franchise location which is aimed at maximizing the proximity between the franchises and the client locations and maximizing the franchise dispersion in order to avoid cannibalization. We have developed several variants of the Variable Neighborhood Search metaheuristic in order to approximate the Pareto front. Extensive computational experiments are presented.