4 Presentations

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

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

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

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