2016 Optimization Days

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

Schedule Authors My Schedule

TB4 Clustering

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

Location: Gérard-Parizeau

Chaired by Claudio Contardo

4 Presentations

  • 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.

  • 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.

  • 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.

  • 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.