Including an Industrial Optimization Day

HEC Montréal, May 7 - 9, 2012


HEC Montréal, May 7 — 9, 2012

Schedule Authors My Schedule
Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402

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

May 8, 2012 10:30 AM – 12:10 PM

Location: Sony

Chaired by Gilles Caporossi

4 Presentations

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:30 AM - 10:55 AM

    The k-Separator Problem

    • Mohamed Ahmed Mohamed Sidi, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    10:55 AM - 11:20 AM

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

    • Fahimah Al-Awadhi, presenter, 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.

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:20 AM - 11:45 AM

    Clustering of a Geographical Region into Spatially Contiguous and Homogeneous Territories

    • Pierre de Freminville, presenter, É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).

  • Cal add eabad1550a3cf3ed9646c36511a21a854fcb401e3247c61aefa77286b00fe402
    11:45 AM - 12:10 PM

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

    • Réal Carbonneau, presenter, 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.