HEC Montréal, Canada, May 6 - 8, 2013
2013 Optimization Days
HEC Montréal, Canada, 6 — 8 May 2013
TB10 Algorithmes II / Algorithms II
May 7, 2013 03:30 PM – 05:10 PM
Location: Nancy et Michel-Gaucher
Chaired by Matthias Takouda
5 Presentations
-
03:30 PM - 03:55 PM
Validation de la Méthode de Vogel Modifiée pour la Résolution du Problème d'Affectation linéaire
Le problème d'affectation linéaire consiste à déterminer un couplage optimal entre deux ensembles de même dimension. Un exemple patent est celui d'affection optimale de n tâches à n travailleurs. Dans cette présentation, nous introduisons ce problème qui possède une pléthore d'applications en recherche opérationnelle. Nous en fournissons certaines pour mieux illustrer son importance dans ce domaine. Ce problème d'affectation est usuellement résolu par la méthode hongroise. Une nouvelle approche de résolution du problème d'affectation est proposée dans cette recherche. Elle est une modification de la méthode d'approximation de Vogel appliquée à la matrice réduite. Pour cette raison, elle s'apparente beaucoup à la méthode hongroise et semble procurer un outil efficace de détermination de zéros indépendants. L'utilisation de la matrice réduite permet d'introduire de nouvelles règles pour lever les embarras de choix. Contrairement à la méthode d'approximation de Vogel, cette approche est convergente pour les problèmes d'affectation. Dans cette présentation, nous proposons une programmation de la méthode de Vogel modifiée en utilisant Java ce qui nous permet de la valider par des tests numériques.
-
03:55 PM - 04:20 PM
Méthode de Vogel modifiée pour la résolution des problèmes de transport simple
L'algorithme de Dantzig (1963) du problème de transport simple, comme toute application de la méthode du simplexe à la résolution de problèmes linéaires, nécessite une solution initiale de base. Sa détermination à partir de la forme standard n'est pas appropriée compte tenu de la structure de ses problèmes de transport. D'autres techniques plus simples et adaptées leurs sont appliquées. La méthode de Vogel (MV), un exemple très utilisé de détermination de solution initiale, est également une méthode d'approximation qui réduit assez considérablement le nombre d’itérations de l’algorithme de transport. Dans cette présentation, une nouvelle méthode d'approximation est introduite. Elle est une modification de la méthode de Vogel permettant d'obtenir une meilleure solution initiale. Nous observons que la méthode modifiée (MVM) fournit directement la solution optimale dans un nombre assez impressionnant de problèmes. De plus, elle permet également dans certains cas de détecter directement l’optimalité sans devoir faire appel à l’évaluation des coûts réduits. Cette démarche ouvre la voie à une nouvelle méthode de résolution des problèmes de transport qui éviterait la sollicitation de l’algorithme de transport.
-
04:20 PM - 04:45 PM
Regression Trees and Forests for Non-homogeneous Poisson Process
Non-homogeneous Poisson processes (NHPP), for which the rate function varies over time, constitute a class of a very versatile model for modeling recurrent events. The existing tree-based methods for count and Poisson data were developed under the assumption of a constant rate function. We propose tree and random forest methods for NHPP. The proposed tree splitting criterion is based on the observed log-likelihood of a model with piecewise constant rate function over pre-specified intervals. The first approach builds a random forest using an aggregation of many trees built with the same intervals. The second approach builds the forest by varying the number, length, and position of the intervals from one tree to another. This produces a smooth estimate of the rate compared to the piecewise constant estimation of the first approach. The results from a simulation study, showing that the proposed models work very well, and an application with real data will be presented.
-
04:45 PM - 05:10 PM
Optimal Stopping Rule for the Full-Information Duration Problem with a Random Number of Objects
A full information duration problem with random horizon is considered. A random number of iid random variables are observed with the objective of maximizing the expected duration of holding a relatively largest observation. A necessary and sufficient condition for the optimal stopping rule to be monotone is given.
-
05:10 PM - 05:35 PM
Planification de chemin : l'état de l'art 2013
Les dernières décennies ont connu un développement conséquent de la robotique et des systèmes de haute autonomie. L'objectif de ma présentation est de revenir sur l'état de l'art concernant la recherche du chemin le plus court. En effet, il s'agit de l'un des outils clé pour la conception de systèmes autonomes.