Journées de l'optimisation 2016

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

Horaire Auteurs Mon horaire

TB4 Clustering

3 mai 2016 15h30 – 17h10

Salle: Gérard-Parizeau

Présidée par Claudio Contardo

4 présentations

  • 15h30 - 15h55

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

    • Ghislain Benoit, prés., 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.

  • 15h55 - 16h20

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

  • 16h20 - 16h45

    Less is more approach: Capacitated clustering problem

    • Jack Brimberg, prés., 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.

  • 16h45 - 17h10

    Bi-objective variable neighborhood search for franchise location

    • Antoine Baudouin, prés., 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.