Incluant une Journée industrielle de l'optimisation

HEC Montréal, 7 - 9 mai 2012


HEC Montréal, 7 — 9 mai 2012

Horaire Auteurs Mon horaire

TB7 Classification et forage de données / Clustering and Data Mining

8 mai 2012 10h30 – 12h10

Salle: Sony

Présidée par Gilles Caporossi

4 présentations

  • 10h30 - 10h55

    The k-Separator Problem

    • Mohamed Ahmed Mohamed Sidi, prés., Telecom SudParis
    • Walid Ben-Ameur, Telecom SudParis
    • José Neto, Telecom SudParis

    Let G be a vertex-weighted undirected graph and k be a positive number. We want to compute a minimum-weight subset of vertices whose removal leads to a graph where the size of each connected component is less than or equal to k. If k =1 we get vertex cover problem.

  • 10h55 - 11h20

    Bayesian Reconstruction using a Multi-Scale Template Method for Shape Detection

    • Fahimah Al-Awadhi, prés., Kuwait University

    In this study, we describe the fitting of Bayesian template models to 3D data in the presence of signal noise and convolution by an initially unknown point spread function. Our motivation is a set of confocal fluorescence microscopy data of cartilage cells which are approximately ellipsoidal. This problem falls within object recognition task that require models and algorithms which deal with the components of the image on a global scale. The high dimensionality of the model requires using Markov chain Monte Carlo (MCMC) simulation to draw samples from the posterior distribution. Substantial computing effort can be consumed simply in reaching the main area of support of the posterior distribution. For more effective use of computation time, we produce an initial typical image as starting point in our simulation. We then use automatic or semi-automatic segmentations showing the shape, size, orientation and spatial arrangement of objects in a sample.

  • 11h20 - 11h45

    Clustering of a Geographical Region into Spatially Contiguous and Homogeneous Territories

    • Pierre de Freminville, prés., École Polytechnique de Montréal

    Clustering of a geographical region into spatially contiguous and homogeneous territories. The problem studied consists of dividing a geographical region into a predefined number of spatially contiguous territories that enforce a minimum weight constraint, while optimizing the homogeneity of the territories. This research proposes a column generation algorithm coupled with a heuristic branching method for solving this problem.The sub-problem generates new territories and is solved by a greedy multi-start heuristic. The method was developed in an industrial context and tested on real data, with a 500 elementary units map. Good feasible solutions were found in short computing times (30min to 2h).

  • 11h45 - 12h10

    Efficient Branch and Bound Optimization using Heuristics, Sequencing and Ending Subset for Clusterwise Regression

    • Réal Carbonneau, prés., HEC Montréal
    • Gilles Caporossi, GERAD, HEC Montréal
    • Pierre Hansen, HEC Montréal

    Branch and bound optimization is enhanced by heuristics which can improve the upper bound, observation sequencing which can improve the search path and can increase fathoming, and ending subsets which can recursively strengthen the lower bounds of the search. Symmetry breaking and incremental regression calculations further speed up the optimization.