Incluant une Journée industrielle de l'optimisation
HEC Montréal, 7  9 mai 2012
JOPT2012
HEC Montréal, 7 — 9 mai 2012
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 kSeparator Problem
Let G be a vertexweighted undirected graph and k be a positive number. We want to compute a minimumweight 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 MultiScale Template Method for Shape Detection
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 semiautomatic 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
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 subproblem generates new territories and is solved by a greedy multistart 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
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.