L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité

Le problème de conception de réseaux est un problème qui a été beaucoup étudié dans le domaine de la recherche opérationnelle pour ses caractéristiques, et ses applications dans des nombreux domaines tels que le transport, les communications, et la logistique. Nous nous intéressons en particulier dans ce mémoire à résoudre le problème de conception de réseaux avec coûts fixes et sans capacité, en satisfaisant les demandes de tous les produits tout en minimisant la somme des coûts de transport de ces produits et des coûts fixes de conception du réseau. Ce problème se modélise généralement sous la forme d’un programme linéaire en nombres entiers incluant des variables continues. Pour le résoudre, nous avons appliqué la méthode exacte de Branch-and-Bound basée sur une relaxation linéaire du problème avec un critère d’arrêt, tout en exploitant les méthodes de génération de colonnes et de génération de coupes. Nous avons testé la méthode de Branch-and-Price-and-Cut sur 156 instances divisées en cinq groupes de différentes tailles, et nous l’avons comparée à Cplex, l’un des meilleurs solveurs d’optimisation mathématique, ainsi qu’à la méthode de Branch-and- Cut. Notre méthode est compétitive et plus performante sur les instances de grande taille ayant un grand nombre de produits.

Optimization of p-cycle protection schemes in optical networks

La survie des réseaux est un domaine d'étude technique très intéressant ainsi qu'une préoccupation critique dans la conception des réseaux. Compte tenu du fait que de plus en plus de données sont transportées à travers des réseaux de communication, une simple panne peut interrompre des millions d'utilisateurs et engendrer des millions de dollars de pertes de revenu. Les techniques de protection des réseaux consistent à fournir une capacité supplémentaire dans un réseau et à réacheminer les flux automatiquement autour de la panne en utilisant cette disponibilité de capacité. Cette thèse porte sur la conception de réseaux optiques intégrant des techniques de survie qui utilisent des schémas de protection basés sur les p-cycles. Plus précisément, les p-cycles de protection par chemin sont exploités dans le contexte de pannes sur les liens. Notre étude se concentre sur la mise en place de structures de protection par p-cycles, et ce, en supposant que les chemins d'opération pour l'ensemble des requêtes sont définis a priori. La majorité des travaux existants utilisent des heuristiques ou des méthodes de résolution ayant de la difficulté à résoudre des instances de grande taille. L'objectif de cette thèse est double. D'une part, nous proposons des modèles et des méthodes de résolution capables d'aborder des problèmes de plus grande taille que ceux déjà présentés dans la littérature. D'autre part, grâce aux nouveaux algorithmes, nous sommes en mesure de produire des solutions optimales ou quasi-optimales. Pour ce faire, nous nous appuyons sur la technique de génération de colonnes, celle-ci étant adéquate pour résoudre des problèmes de programmation linéaire de grande taille. Dans ce projet, la génération de colonnes est utilisée comme une façon intelligente d'énumérer implicitement des cycles prometteurs. Nous proposons d'abord des formulations pour le problème maître et le problème auxiliaire ainsi qu'un premier algorithme de génération de colonnes pour la conception de réseaux protegées par des p-cycles de la protection par chemin. L'algorithme obtient de meilleures solutions, dans un temps raisonnable, que celles obtenues par les méthodes existantes. Par la suite, une formulation plus compacte est proposée pour le problème auxiliaire. De plus, nous présentons une nouvelle méthode de décomposition hiérarchique qui apporte une grande amélioration de l'efficacité globale de l'algorithme. En ce qui concerne les solutions en nombres entiers, nous proposons deux méthodes heurisiques qui arrivent à trouver des bonnes solutions. Nous nous attardons aussi à une comparaison systématique entre les p-cycles et les schémas classiques de protection partagée. Nous effectuons donc une comparaison précise en utilisant des formulations unifiées et basées sur la génération de colonnes pour obtenir des résultats de bonne qualité. Par la suite, nous évaluons empiriquement les versions orientée et non-orientée des p-cycles pour la protection par lien ainsi que pour la protection par chemin, dans des scénarios de trafic asymétrique. Nous montrons quel est le coût de protection additionnel engendré lorsque des systèmes bidirectionnels sont employés dans de tels scénarios. Finalement, nous étudions une formulation de génération de colonnes pour la conception de réseaux avec des p-cycles en présence d'exigences de disponibilité et nous obtenons des premières bornes inférieures pour ce problème.

Optimization models and methods for real-time transportation planning in forestry

Lors du transport du bois de la forêt vers les usines, de nombreux événements imprévus peuvent se produire, événements qui perturbent les trajets prévus (par exemple, en raison des conditions météo, des feux de forêt, de la présence de nouveaux chargements, etc.). Lorsque de tels événements ne sont connus que durant un trajet, le camion qui accomplit ce trajet doit être détourné vers un chemin alternatif. En l’absence d’informations sur un tel chemin, le chauffeur du camion est susceptible de choisir un chemin alternatif inutilement long ou pire, qui est lui-même "fermé" suite à un événement imprévu. Il est donc essentiel de fournir aux chauffeurs des informations en temps réel, en particulier des suggestions de chemins alternatifs lorsqu’une route prévue s’avère impraticable. Les possibilités de recours en cas d’imprévus dépendent des caractéristiques de la chaîne logistique étudiée comme la présence de camions auto-chargeurs et la politique de gestion du transport. Nous présentons trois articles traitant de contextes d’application différents ainsi que des modèles et des méthodes de résolution adaptés à chacun des contextes. Dans le premier article, les chauffeurs de camion disposent de l’ensemble du plan hebdomadaire de la semaine en cours. Dans ce contexte, tous les efforts doivent être faits pour minimiser les changements apportés au plan initial. Bien que la flotte de camions soit homogène, il y a un ordre de priorité des chauffeurs. Les plus prioritaires obtiennent les volumes de travail les plus importants. Minimiser les changements dans leurs plans est également une priorité. Étant donné que les conséquences des événements imprévus sur le plan de transport sont essentiellement des annulations et/ou des retards de certains voyages, l’approche proposée traite d’abord l’annulation et le retard d’un seul voyage, puis elle est généralisée pour traiter des événements plus complexes. Dans cette ap- proche, nous essayons de re-planifier les voyages impactés durant la même semaine de telle sorte qu’une chargeuse soit libre au moment de l’arrivée du camion à la fois au site forestier et à l’usine. De cette façon, les voyages des autres camions ne seront pas mo- difiés. Cette approche fournit aux répartiteurs des plans alternatifs en quelques secondes. De meilleures solutions pourraient être obtenues si le répartiteur était autorisé à apporter plus de modifications au plan initial. Dans le second article, nous considérons un contexte où un seul voyage à la fois est communiqué aux chauffeurs. Le répartiteur attend jusqu’à ce que le chauffeur termine son voyage avant de lui révéler le prochain voyage. Ce contexte est plus souple et offre plus de possibilités de recours en cas d’imprévus. En plus, le problème hebdomadaire peut être divisé en des problèmes quotidiens, puisque la demande est quotidienne et les usines sont ouvertes pendant des périodes limitées durant la journée. Nous utilisons un modèle de programmation mathématique basé sur un réseau espace-temps pour réagir aux perturbations. Bien que ces dernières puissent avoir des effets différents sur le plan de transport initial, une caractéristique clé du modèle proposé est qu’il reste valable pour traiter tous les imprévus, quelle que soit leur nature. En effet, l’impact de ces événements est capturé dans le réseau espace-temps et dans les paramètres d’entrée plutôt que dans le modèle lui-même. Le modèle est résolu pour la journée en cours chaque fois qu’un événement imprévu est révélé. Dans le dernier article, la flotte de camions est hétérogène, comprenant des camions avec des chargeuses à bord. La configuration des routes de ces camions est différente de celle des camions réguliers, car ils ne doivent pas être synchronisés avec les chargeuses. Nous utilisons un modèle mathématique où les colonnes peuvent être facilement et naturellement interprétées comme des itinéraires de camions. Nous résolvons ce modèle en utilisant la génération de colonnes. Dans un premier temps, nous relaxons l’intégralité des variables de décision et nous considérons seulement un sous-ensemble des itinéraires réalisables. Les itinéraires avec un potentiel d’amélioration de la solution courante sont ajoutés au modèle de manière itérative. Un réseau espace-temps est utilisé à la fois pour représenter les impacts des événements imprévus et pour générer ces itinéraires. La solution obtenue est généralement fractionnaire et un algorithme de branch-and-price est utilisé pour trouver des solutions entières. Plusieurs scénarios de perturbation ont été développés pour tester l’approche proposée sur des études de cas provenant de l’industrie forestière canadienne et les résultats numériques sont présentés pour les trois contextes.

Planification et dimensionnement des réseaux optiques de longues distances

Le projet de recherche porte sur l'étude des problèmes de conception et de planification d'un réseau optique de longue distance, aussi appelé réseau de coeur (OWAN-Optical Wide Area Network en anglais). Il s'agit d'un réseau qui transporte des flots agrégés en mode commutation de circuits. Un réseau OWAN relie différents sites à l'aide de fibres optiques connectées par des commutateurs/routeurs optiques et/ou électriques. Un réseau OWAN est maillé à l'échelle d'un pays ou d’un continent et permet le transit des données à très haut débit. Dans une première partie du projet de thèse, nous nous intéressons au problème de conception de réseaux optiques agiles. Le problème d'agilité est motivé par la croissance de la demande en bande passante et par la nature dynamique du trafic. Les équipements déployés par les opérateurs de réseaux doivent disposer d'outils de configuration plus performants et plus flexibles pour gérer au mieux la complexité des connexions entre les clients et tenir compte de la nature évolutive du trafic. Souvent, le problème de conception d'un réseau consiste à prévoir la bande passante nécessaire pour écouler un trafic donné. Ici, nous cherchons en plus à choisir la meilleure configuration nodale ayant un niveau d'agilité capable de garantir une affectation optimale des ressources du réseau. Nous étudierons également deux autres types de problèmes auxquels un opérateur de réseau est confronté. Le premier problème est l'affectation de ressources du réseau. Une fois que l'architecture du réseau en termes d'équipements est choisie, la question qui reste est de savoir : comment dimensionner et optimiser cette architecture pour qu'elle rencontre le meilleur niveau possible d'agilité pour satisfaire toute la demande. La définition de la topologie de routage est un problème d'optimisation complexe. Elle consiste à définir un ensemble de chemins optiques logiques, choisir les routes physiques suivies par ces derniers, ainsi que les longueurs d'onde qu'ils utilisent, de manière à optimiser la qualité de la solution obtenue par rapport à un ensemble de métriques pour mesurer la performance du réseau. De plus, nous devons définir la meilleure stratégie de dimensionnement du réseau de façon à ce qu'elle soit adaptée à la nature dynamique du trafic. Le second problème est celui d'optimiser les coûts d'investissement en capital(CAPEX) et d'opération (OPEX) de l'architecture de transport proposée. Dans le cas du type d'architecture de dimensionnement considérée dans cette thèse, le CAPEX inclut les coûts de routage, d'installation et de mise en service de tous les équipements de type réseau installés aux extrémités des connexions et dans les noeuds intermédiaires. Les coûts d'opération OPEX correspondent à tous les frais liés à l'exploitation du réseau de transport. Étant donné la nature symétrique et le nombre exponentiel de variables dans la plupart des formulations mathématiques développées pour ces types de problèmes, nous avons particulièrement exploré des approches de résolution de type génération de colonnes et algorithme glouton qui s'adaptent bien à la résolution des grands problèmes d'optimisation. Une étude comparative de plusieurs stratégies d'allocation de ressources et d'algorithmes de résolution, sur différents jeux de données et de réseaux de transport de type OWAN démontre que le meilleur coût réseau est obtenu dans deux cas : une stratégie de dimensionnement anticipative combinée avec une méthode de résolution de type génération de colonnes dans les cas où nous autorisons/interdisons le dérangement des connexions déjà établies. Aussi, une bonne répartition de l'utilisation des ressources du réseau est observée avec les scénarios utilisant une stratégie de dimensionnement myope combinée à une approche d'allocation de ressources avec une résolution utilisant les techniques de génération de colonnes. Les résultats obtenus à l'issue de ces travaux ont également démontré que des gains considérables sont possibles pour les coûts d'investissement en capital et d'opération. En effet, une répartition intelligente et hétérogène de ressources d’un réseau sur l'ensemble des noeuds permet de réaliser une réduction substantielle des coûts du réseau par rapport à une solution d'allocation de ressources classique qui adopte une architecture homogène utilisant la même configuration nodale dans tous les noeuds. En effet, nous avons démontré qu'il est possible de réduire le nombre de commutateurs photoniques tout en satisfaisant la demande de trafic et en gardant le coût global d'allocation de ressources de réseau inchangé par rapport à l'architecture classique. Cela implique une réduction substantielle des coûts CAPEX et OPEX. Dans nos expériences de calcul, les résultats démontrent que la réduction de coûts peut atteindre jusqu'à 65% dans certaines jeux de données et de réseau.

Timing verification in transaction modeling

Les systèmes Matériels/Logiciels deviennent indispensables dans tous les aspects de la vie quotidienne. La présence croissante de ces systèmes dans les différents produits et services incite à trouver des méthodes pour les développer efficacement. Mais une conception efficace de ces systèmes est limitée par plusieurs facteurs, certains d'entre eux sont: la complexité croissante des applications, une augmentation de la densité d'intégration, la nature hétérogène des produits et services, la diminution de temps d’accès au marché. Une modélisation transactionnelle (TLM) est considérée comme un paradigme prometteur permettant de gérer la complexité de conception et fournissant des moyens d’exploration et de validation d'alternatives de conception à des niveaux d’abstraction élevés. Cette recherche propose une méthodologie d’expression de temps dans TLM basée sur une analyse de contraintes temporelles. Nous proposons d'utiliser une combinaison de deux paradigmes de développement pour accélérer la conception: le TLM d'une part et une méthodologie d’expression de temps entre différentes transactions d’autre part. Cette synergie nous permet de combiner dans un seul environnement des méthodes de simulation performantes et des méthodes analytiques formelles. Nous avons proposé un nouvel algorithme de vérification temporelle basé sur la procédure de linéarisation des contraintes de type min/max et une technique d'optimisation afin d'améliorer l'efficacité de l'algorithme. Nous avons complété la description mathématique de tous les types de contraintes présentées dans la littérature. Nous avons développé des méthodes d'exploration et raffinement de système de communication qui nous a permis d'utiliser les algorithmes de vérification temporelle à différents niveaux TLM. Comme il existe plusieurs définitions du TLM, dans le cadre de notre recherche, nous avons défini une méthodologie de spécification et simulation pour des systèmes Matériel/Logiciel basée sur le paradigme de TLM. Dans cette méthodologie plusieurs concepts de modélisation peuvent être considérés séparément. Basée sur l'utilisation des technologies modernes de génie logiciel telles que XML, XSLT, XSD, la programmation orientée objet et plusieurs autres fournies par l’environnement .Net, la méthodologie proposée présente une approche qui rend possible une réutilisation des modèles intermédiaires afin de faire face à la contrainte de temps d’accès au marché. Elle fournit une approche générale dans la modélisation du système qui sépare les différents aspects de conception tels que des modèles de calculs utilisés pour décrire le système à des niveaux d’abstraction multiples. En conséquence, dans le modèle du système nous pouvons clairement identifier la fonctionnalité du système sans les détails reliés aux plateformes de développement et ceci mènera à améliorer la "portabilité" du modèle d'application.

Optimization and validation of a new 3D-US imaging robot to detect, localize and quantify lower limb arterial stenoses

L’athérosclérose est une maladie qui cause, par l’accumulation de plaques lipidiques, le durcissement de la paroi des artères et le rétrécissement de la lumière. Ces lésions sont généralement localisées sur les segments artériels coronariens, carotidiens, aortiques, rénaux, digestifs et périphériques. En ce qui concerne l’atteinte périphérique, celle des membres inférieurs est particulièrement fréquente. En effet, la sévérité de ces lésions artérielles est souvent évaluée par le degré d’une sténose (réduction >50 % du diamètre de la lumière) en angiographie, imagerie par résonnance magnétique (IRM), tomodensitométrie ou échographie. Cependant, pour planifier une intervention chirurgicale, une représentation géométrique artérielle 3D est notamment préférable. Les méthodes d’imagerie par coupe (IRM et tomodensitométrie) sont très performantes pour générer une imagerie tridimensionnelle de bonne qualité mais leurs utilisations sont dispendieuses et invasives pour les patients. L’échographie 3D peut constituer une avenue très prometteuse en imagerie pour la localisation et la quantification des sténoses. Cette modalité d’imagerie offre des avantages distincts tels la commodité, des coûts peu élevés pour un diagnostic non invasif (sans irradiation ni agent de contraste néphrotoxique) et aussi l’option d’analyse en Doppler pour quantifier le flux sanguin. Étant donné que les robots médicaux ont déjà été utilisés avec succès en chirurgie et en orthopédie, notre équipe a conçu un nouveau système robotique d’échographie 3D pour détecter et quantifier les sténoses des membres inférieurs. Avec cette nouvelle technologie, un radiologue fait l’apprentissage manuel au robot d’un balayage échographique du vaisseau concerné. Par la suite, le robot répète à très haute précision la trajectoire apprise, contrôle simultanément le processus d’acquisition d’images échographiques à un pas d’échantillonnage constant et conserve de façon sécuritaire la force appliquée par la sonde sur la peau du patient. Par conséquent, la reconstruction d’une géométrie artérielle 3D des membres inférieurs à partir de ce système pourrait permettre une localisation et une quantification des sténoses à très grande fiabilité. L’objectif de ce projet de recherche consistait donc à valider et optimiser ce système robotisé d’imagerie échographique 3D. La fiabilité d’une géométrie reconstruite en 3D à partir d’un système référentiel robotique dépend beaucoup de la précision du positionnement et de la procédure de calibration. De ce fait, la précision pour le positionnement du bras robotique fut évaluée à travers son espace de travail avec un fantôme spécialement conçu pour simuler la configuration des artères des membres inférieurs (article 1 - chapitre 3). De plus, un fantôme de fils croisés en forme de Z a été conçu pour assurer une calibration précise du système robotique (article 2 - chapitre 4). Ces méthodes optimales ont été utilisées pour valider le système pour l’application clinique et trouver la transformation qui convertit les coordonnées de l’image échographique 2D dans le référentiel cartésien du bras robotisé. À partir de ces résultats, tout objet balayé par le système robotique peut être caractérisé pour une reconstruction 3D adéquate. Des fantômes vasculaires compatibles avec plusieurs modalités d’imagerie ont été utilisés pour simuler différentes représentations artérielles des membres inférieurs (article 2 - chapitre 4, article 3 - chapitre 5). La validation des géométries reconstruites a été effectuée à l`aide d`analyses comparatives. La précision pour localiser et quantifier les sténoses avec ce système robotisé d’imagerie échographique 3D a aussi été déterminée. Ces évaluations ont été réalisées in vivo pour percevoir le potentiel de l’utilisation d’un tel système en clinique (article 3- chapitre 5).

Groupage et protection du trafic dynamique dans les réseaux WDM

Avec les nouvelles technologies des réseaux optiques, une quantité de données de plus en plus grande peut être transportée par une seule longueur d'onde. Cette quantité peut atteindre jusqu’à 40 gigabits par seconde (Gbps). Les flots de données individuels quant à eux demandent beaucoup moins de bande passante. Le groupage de trafic est une technique qui permet l'utilisation efficace de la bande passante offerte par une longueur d'onde. Elle consiste à assembler plusieurs flots de données de bas débit en une seule entité de données qui peut être transporté sur une longueur d'onde. La technique demultiplexage en longueurs d'onde (Wavelength Division Multiplexing WDM) permet de transporter plusieurs longueurs d'onde sur une même fibre. L'utilisation des deux techniques : WDM et groupage de trafic, permet de transporter une quantité de données de l'ordre de terabits par seconde (Tbps) sur une même fibre optique. La protection du trafic dans les réseaux optiques devient alors une opération très vitale pour ces réseaux, puisqu'une seule panne peut perturber des milliers d'utilisateurs et engendre des pertes importantes jusqu'à plusieurs millions de dollars à l'opérateur et aux utilisateurs du réseau. La technique de protection consiste à réserver une capacité supplémentaire pour acheminer le trafic en cas de panne dans le réseau. Cette thèse porte sur l'étude des techniques de groupage et de protection du trafic en utilisant les p-cycles dans les réseaux optiques dans un contexte de trafic dynamique. La majorité des travaux existants considère un trafic statique où l'état du réseau ainsi que le trafic sont donnés au début et ne changent pas. En plus, la majorité de ces travaux utilise des heuristiques ou des méthodes ayant de la difficulté à résoudre des instances de grande taille. Dans le contexte de trafic dynamique, deux difficultés majeures s'ajoutent aux problèmes étudiés, à cause du changement continuel du trafic dans le réseau. La première est due au fait que la solution proposée à la période précédente, même si elle est optimisée, n'est plus nécessairement optimisée ou optimale pour la période courante, une nouvelle optimisation de la solution au problème est alors nécessaire. La deuxième difficulté est due au fait que la résolution du problème pour une période donnée est différente de sa résolution pour la période initiale à cause des connexions en cours dans le réseau qui ne doivent pas être trop dérangées à chaque période de temps. L'étude faite sur la technique de groupage de trafic dans un contexte de trafic dynamique consiste à proposer différents scénarios pour composer avec ce type de trafic, avec comme objectif la maximisation de la bande passante des connexions acceptées à chaque période de temps. Des formulations mathématiques des différents scénarios considérés pour le problème de groupage sont proposées. Les travaux que nous avons réalisés sur le problème de la protection considèrent deux types de p-cycles, ceux protégeant les liens (p-cycles de base) et les FIPP p-cycles (p-cycles protégeant les chemins). Ces travaux ont consisté d’abord en la proposition de différents scénarios pour gérer les p-cycles de protection dans un contexte de trafic dynamique. Ensuite, une étude sur la stabilité des p-cycles dans un contexte de trafic dynamique a été faite. Des formulations de différents scénarios ont été proposées et les méthodes de résolution utilisées permettent d’aborder des problèmes de plus grande taille que ceux présentés dans la littérature. Nous nous appuyons sur la méthode de génération de colonnes pour énumérer implicitement les cycles les plus prometteurs. Dans l'étude des p-cycles protégeant les chemins ou FIPP p-cycles, nous avons proposé des formulations pour le problème maître et le problème auxiliaire. Nous avons utilisé une méthode de décomposition hiérarchique du problème qui nous permet d'obtenir de meilleurs résultats dans un temps raisonnable. Comme pour les p-cycles de base, nous avons étudié la stabilité des FIPP p-cycles dans un contexte de trafic dynamique. Les travaux montrent que dépendamment du critère d'optimisation, les p-cycles de base (protégeant les liens) et les FIPP p-cycles (protégeant les chemins) peuvent être très stables.

Représentation et détection des images et des surfaces déformables

La représentation d'une surface, son lissage et son utilisation pour l'identification, la comparaison, la classification, et l'étude des variations de volume, de courbure ou de topologie sont omniprésentes dans l'aire de la numérisation. Parmi les méthodes mathématiques, nous avons retenu les transformations difféomorphiques d'un pattern de référence. Il y a un grand intérêt théorique et numérique à approcher un difféomorphisme arbitraire par des difféomorphismes engendrés par des champs de vitesses. Sur le plan théorique la question est : "est-ce que le sous-groupe de difféomorphismes engendrés par des champs de vitesses est dense dans le groupe plus large de Micheletti pour la métrique de Courant ?" Malgré quelques progrès réalisés ici, cette question demeure ouverte. Les pistes empruntées ont alors convergé vers le sous-groupe de Azencott et de Trouvé et sa métrique dans le cadre de l'imagerie. Elle correspond à une notion de géodésique entre deux difféomorphismes dans leur sous-groupe. L'optimisation est utilisée pour obtenir un système d'équations état adjoint caractérisant la solution optimale du problème d'identification à partir des observations. Cette approche est adaptée à l'identification de surfaces obtenues par un numériseur tel que, par exemple, le scan d'un visage. Ce problème est beaucoup plus difficile que celui d'imagerie. On doit alors introduire un système de référence courbe et une surface à facettes pour les calculs. On donne la formulation du problème d'identification et du calcul du changement de volume par rapport à un scan de référence.

C.A.M.E.L.E.O. : a cultural adaptation methodology for E-learning environment optimization

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Représentation et identification des hypersurfaces

L’objectif à moyen terme de ce travail est d’explorer quelques formulations des problèmes d’identification de forme et de reconnaissance de surface à partir de mesures ponctuelles. Ces problèmes ont plusieurs applications importantes dans les domaines de l’imagerie médicale, de la biométrie, de la sécurité des accès automatiques et dans l’identification de structures cohérentes lagrangiennes en mécanique des fluides. Par exemple, le problème d’identification des différentes caractéristiques de la main droite ou du visage d’une population à l’autre ou le suivi d’une chirurgie à partir des données générées par un numériseur. L’objectif de ce mémoire est de préparer le terrain en passant en revue les différents outils mathématiques disponibles pour appréhender la géométrie comme variable d’optimisation ou d’identification. Pour l’identification des surfaces, on explore l’utilisation de fonctions distance ou distance orientée, et d’ensembles de niveau comme chez S. Osher et R. Fedkiw ; pour la comparaison de surfaces, on présente les constructions des métriques de Courant par A. M. Micheletti en 1972 et le point de vue de R. Azencott et A. Trouvé en 1995 qui consistent à générer des déformations d’une surface de référence via une famille de difféomorphismes. L’accent est mis sur les fondations mathématiques sous-jacentes que l’on a essayé de clarifier lorsque nécessaire, et, le cas échéant, sur l’exploration d’autres avenues.

Optimization Studies to Improve MSC-based Cardiac Cell Therapy : Cytokine Preconditioning and Nanoparticle Coupling

Contexte: La cardiopathie ischémique (IHD) reste une cause majeure de mortalité en Amérique du Nord. La thérapie cellulaire cardiaque (CCT) a émergé comme une thérapie prometteuse pour aider à guérir certaines malades cardiaques. Parmi les cellulaires avec propriétés pluripotentes, les cellules stromales mésenchymateuses (MSC) sont prometteuses. Cependant, plusieurs questions demeurent non résolues et certaines défis empêchent l'application clinique de la CCT se dans l'IHD, tels que le faible taux de rétention cellulaire in situ, le suivi des cellules in vivo post-implantation et post-acheminements et l`apoptose. Ici, le traitement préliminaire des MSC avec des facteurs de croissance et leur couplage avec des nanoparticules (NP) seront étudiés comme des méthodes pour optimiser MSC. Méthodes: Des MSCs provenant du rat (rMSC) et du cochon (pMSC) ont été isolés à partir de moelle osseuse. Les rMSC ont été préconditionnées avec SDF-1a, TSG-6 et PDGF-BB, et ensuite soumises à une hypoxie, une privation de sérum et a un stress oxydatif. Des études de cicatrisation ont également été effectués avec rMSCs préconditionnées. En parallèle, de nouvelles NP ferromagnétiques liées aux silicones ont été synthétisées. Les NPs ont été couplées aux pMSCs suivant leur fonctionnalisation avec l`anticorps, CD44, un antigène de surface du MSC bien connu. Par la suite, les études de biocompatibilité ont été réalisées sur pMSC-NP et en incluant des tests des processus cellulaires tels que la migration, l'adhésion, la prolifération et les propriétés de la différenciation. Résultats: Parmi toutes les cytokines testées, PDGF-BB a démontré la plus grande capacité à améliorer la survie de MSC dans des conditions d'hypoxie, de privation de sérum et en reponse au stress oxydatif. La conjugaison de NP a atténué la migration et la prolifération des pMSCs, mais n`a pas changé leur capacité de différenciation. Enfin, la complexe du MSC-NP est détectable par IRM. Conclusion: Nos données suggèrent que de nouvelles stratégies, telles que traitement préliminaire de PDGF-BB et le couplage des nanoparticules ferromagnétiques, peuvent être considérés comme des avenues prometteuse pour optimiser les MSCs pour la CCT.

Revisiting optimization algorithms for maximum likelihood estimation

Parmi les méthodes d’estimation de paramètres de loi de probabilité en statistique, le maximum de vraisemblance est une des techniques les plus populaires, comme, sous des conditions l´egères, les estimateurs ainsi produits sont consistants et asymptotiquement efficaces. Les problèmes de maximum de vraisemblance peuvent être traités comme des problèmes de programmation non linéaires, éventuellement non convexe, pour lesquels deux grandes classes de méthodes de résolution sont les techniques de région de confiance et les méthodes de recherche linéaire. En outre, il est possible d’exploiter la structure de ces problèmes pour tenter d’accélerer la convergence de ces méthodes, sous certaines hypothèses. Dans ce travail, nous revisitons certaines approches classiques ou récemment d´eveloppées en optimisation non linéaire, dans le contexte particulier de l’estimation de maximum de vraisemblance. Nous développons également de nouveaux algorithmes pour résoudre ce problème, reconsidérant différentes techniques d’approximation de hessiens, et proposons de nouvelles méthodes de calcul de pas, en particulier dans le cadre des algorithmes de recherche linéaire. Il s’agit notamment d’algorithmes nous permettant de changer d’approximation de hessien et d’adapter la longueur du pas dans une direction de recherche fixée. Finalement, nous évaluons l’efficacité numérique des méthodes proposées dans le cadre de l’estimation de modèles de choix discrets, en particulier les modèles logit mélangés.

Improving the microbial production of biofuels through metabolic engineering

Les défis conjoints du changement climatique d'origine anthropique et la diminution des réserves de combustibles fossiles sont le moteur de recherche intense pour des sources d'énergie alternatives. Une avenue attrayante est d'utiliser un processus biologique pour produire un biocarburant. Parmi les différentes options en matière de biocarburants, le bio-hydrogène gazeux est un futur vecteur énergétique attrayant en raison de son efficacité potentiellement plus élevé de conversion de puissance utilisable, il est faible en génération inexistante de polluants et de haute densité d'énergie. Cependant, les faibles rendements et taux de production ont été les principaux obstacles à l'application pratique des technologies de bio-hydrogène. Des recherches intensives sur bio-hydrogène sont en cours, et dans les dernières années, plusieurs nouvelles approches ont été proposées et étudiées pour dépasser ces inconvénients. À cette fin, l'objectif principal de cette thèse était d'améliorer le rendement en hydrogène moléculaire avec un accent particulier sur l'ingénierie métabolique et l’utilisation de bioprocédés à variables indépendantes. Une de nos hypothèses était que la production d’hydrogène pourrait être améliorée et rendue plus économiquement viable par ingénierie métabolique de souches d’Escherichia coli producteurs d’hydrogène en utilisant le glucose ainsi que diverses autres sources de carbone, y compris les pentoses. Les effets du pH, de la température et de sources de carbone ont été étudiés. La production maximale d'hydrogène a été obtenue à partir de glucose, à un pH initial de 6.5 et une température de 35°C. Les études de cinétiques de croissance ont montré que la μmax était 0.0495 h-1 avec un Ks de 0.0274 g L-1 lorsque le glucose est la seule source de carbone en milieu minimal M9. .Parmi les nombreux sucres et les dérivés de sucres testés, les rendements les plus élevés d'hydrogène sont avec du fructose, sorbitol et D-glucose; 1.27, 1.46 et 1.51 mol H2 mol-1 de substrat, respectivement. En outre, pour obtenir les interactions entre les variables importantes et pour atteindre une production maximale d'hydrogène, un design 3K factoriel complet Box-Behnken et la méthodologie de réponse de surface (RSM) ont été employées pour la conception expérimentale et l'analyse de la souche d'Escherichia coli DJT135. Le rendement en hydrogène molaire maximale de 1.69 mol H2 mol-1 de glucose a été obtenu dans les conditions optimales de 75 mM de glucose, à 35°C et un pH de 6.5. Ainsi, la RSM avec un design Box-Behken était un outil statistique utile pour atteindre des rendements plus élevés d'hydrogène molaires par des organismes modifiés génétiquement. Ensuite, l'expression hétérologue de l’hydrogénases soluble [Ni-Fe] de Ralstonia eutropha H16 (l'hydrogénase SH) a tenté de démontrer que la mise en place d'une voie capable de dériver l'hydrogène à partir de NADH pourrait surpasser le rendement stoechiométrique en hydrogène.. L’expression a été démontrée par des tests in vitro de l'activité enzymatique. Par ailleurs, l'expression de SH a restaurée la croissance en anaérobie de souches mutantes pour adhE, normalement inhibées en raison de l'incapacité de réoxyder le NADH. La mesure de la production d'hydrogène in vivo a montré que plusieurs souches modifiées métaboliquement sont capables d'utiliser l'hydrogénase SH pour dériver deux moles d’hydrogène par mole de glucose consommé, proche du maximum théorique. Une autre stratégie a montré que le glycérol brut pourrait être converti en hydrogène par photofermentation utilisant Rhodopseudomonas palustris par photofermentation. Les effets de la source d'azote et de différentes concentrations de glycérol brut sur ce processus ont été évalués. À 20 mM de glycérol, 4 mM glutamate, 6.1 mol hydrogène / mole de glycérol brut ont été obtenus dans des conditions optimales, un rendement de 87% de la théorie, et significativement plus élevés que ce qui a été réalisé auparavant. En prolongement de cette étude, l'optimisation des paramètres a également été utilisée. Dans des conditions optimales, une intensité lumineuse de 175 W/m2, 30 mM glycérol et 4.5 mM de glutamate, 6.69 mol hydrogène / mole de glycérol brut ont été obtenus, soit un rendement de 96% de la valeur théorique. La détermination de l'activité de la nitrogénase et ses niveaux d'expression ont montré qu'il y avait relativement peu de variation de la quantité de nitrogénase avec le changement des variables alors que l'activité de la nitrogénase variait considérablement, avec une activité maximale (228 nmol de C2H4/ml/min) au point central optimal. Dans la dernière section, la production d'hydrogène à partir du glucose via la photofermentation en une seule étape a été examinée avec la bactérie photosynthétique Rhodobacter capsulatus JP91 (hup-). La méthodologie de surface de réponse avec Box-Behnken a été utilisée pour optimiser les variables expérimentales de façon indépendante, soit la concentration de glucose, la concentration du glutamate et l'intensité lumineuse, ainsi que d'examiner leurs effets interactifs pour la maximisation du rendement en hydrogène moléculaire. Dans des conditions optimales, avec une intensité lumineuse de 175 W/m2, 35 mM de glucose, et 4.5 mM de glutamate,, un rendement maximal d'hydrogène de 5.5 (± 0.15) mol hydrogène /mol glucose, et un maximum d'activité de la nitrogénase de 246 (± 3.5) nmol C2H4/ml/min ont été obtenus. L'analyse densitométrique de l'expression de la protéine-Fe nitrogenase dans les différentes conditions a montré une variation significative de l'expression protéique avec un maximum au point central optimisé. Même dans des conditions optimales pour la production d'hydrogène, une fraction significative de la protéine Fe a été trouvée dans l'état ADP-ribosylée, suggérant que d'autres améliorations des rendements pourraient être possibles. À cette fin, un mutant amtB dérivé de Rhodobacter capsulatus JP91 (hup-) a été créé en utilisant le vecteur de suicide pSUP202. Les résultats expérimentaux préliminaires montrent que la souche nouvellement conçue métaboliquement, R. capsulatus DG9, produit 8.2 (± 0.06) mol hydrogène / mole de glucose dans des conditions optimales de cultures discontinues (intensité lumineuse, 175 W/m2, 35 mM de glucose et 4.5 mM glutamate). Le statut d'ADP-ribosylation de la nitrogénase-protéine Fe a été obtenu par Western Blot pour la souche R. capsulatus DG9. En bref, la production d'hydrogène est limitée par une barrière métabolique. La principale barrière métabolique est due au manque d'outils moléculaires possibles pour atteindre ou dépasser le rendement stochiométrique en bio-hydrogène depuis les dernières décennies en utilisant les microbes. À cette fin, une nouvelle approche d’ingénierie métabolique semble très prometteuse pour surmonter cette contrainte vers l'industrialisation et s'assurer de la faisabilité de la technologie de la production d'hydrogène. Dans la présente étude, il a été démontré que l’ingénierie métabolique de bactéries anaérobiques facultatives (Escherichia coli) et de bactéries anaérobiques photosynthétiques (Rhodobacter capsulatus et Rhodopseudomonas palustris) peuvent produire de l'hydrogène en tant que produit majeur à travers le mode de fermentation par redirection métabolique vers la production d'énergie potentielle. D'autre part, la méthodologie de surface de réponse utilisée dans cette étude représente un outil potentiel pour optimiser la production d'hydrogène en générant des informations appropriées concernant la corrélation entre les variables et des producteurs de bio-de hydrogène modifiés par ingénierie métabolique. Ainsi, un outil d'optimisation des paramètres représente une nouvelle avenue pour faire un pont entre le laboratoire et la production d'hydrogène à l'échelle industrielle en fournissant un modèle mathématique potentiel pour intensifier la production de bio-hydrogène. Par conséquent, il a été clairement mis en évidence dans ce projet que l'effort combiné de l'ingénierie métabolique et la méthodologie de surface de réponse peut rendre la technologie de production de bio-hydrogène potentiellement possible vers sa commercialisation dans un avenir rapproché.

Staffing Optimization with Chance Constraints in Call Centers

Les centres d’appels sont des éléments clés de presque n’importe quelle grande organisation. Le problème de gestion du travail a reçu beaucoup d’attention dans la littérature. Une formulation typique se base sur des mesures de performance sur un horizon infini, et le problème d’affectation d’agents est habituellement résolu en combinant des méthodes d’optimisation et de simulation. Dans cette thèse, nous considérons un problème d’affection d’agents pour des centres d’appels soumis a des contraintes en probabilité. Nous introduisons une formulation qui exige que les contraintes de qualité de service (QoS) soient satisfaites avec une forte probabilité, et définissons une approximation de ce problème par moyenne échantillonnale dans un cadre de compétences multiples. Nous établissons la convergence de la solution du problème approximatif vers celle du problème initial quand la taille de l’échantillon croit. Pour le cas particulier où tous les agents ont toutes les compétences (un seul groupe d’agents), nous concevons trois méthodes d’optimisation basées sur la simulation pour le problème de moyenne échantillonnale. Étant donné un niveau initial de personnel, nous augmentons le nombre d’agents pour les périodes où les contraintes sont violées, et nous diminuons le nombre d’agents pour les périodes telles que les contraintes soient toujours satisfaites après cette réduction. Des expériences numériques sont menées sur plusieurs modèles de centre d’appels à faible occupation, au cours desquelles les algorithmes donnent de bonnes solutions, i.e. la plupart des contraintes en probabilité sont satisfaites, et nous ne pouvons pas réduire le personnel dans une période donnée sont introduire de violation de contraintes. Un avantage de ces algorithmes, par rapport à d’autres méthodes, est la facilité d’implémentation.