Développement d’un algorithme de branch-and-price-and-cut pour le problème de conception de réseau avec coûts fixes et capacités

De nombreux problèmes en transport et en logistique peuvent être formulés comme des modèles de conception de réseau. Ils requièrent généralement de transporter des produits, des passagers ou encore des données dans un réseau afin de satisfaire une certaine demande tout en minimisant les coûts. Dans ce mémoire, nous nous intéressons au problème de conception de réseau avec coûts fixes et capacités. Ce problème consiste à ouvrir un sous-ensemble des liens dans un réseau afin de satisfaire la demande, tout en respectant les contraintes de capacités sur les liens. L'objectif est de minimiser les coûts fixes associés à l'ouverture des liens et les coûts de transport des produits. Nous présentons une méthode exacte pour résoudre ce problème basée sur des techniques utilisées en programmation linéaire en nombres entiers. Notre méthode est une variante de l'algorithme de branch-and-bound, appelée branch-and-price-and-cut, dans laquelle nous exploitons à la fois la génération de colonnes et de coupes pour la résolution d'instances de grande taille, en particulier, celles ayant un grand nombre de produits. En nous comparant à CPLEX, actuellement l'un des meilleurs logiciels d'optimisation mathématique, notre méthode est compétitive sur les instances de taille moyenne et supérieure sur les instances de grande taille ayant un grand nombre de produits, et ce, même si elle n'utilise qu'un seul type d'inégalités valides.

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.

Détection et caractérisation génétique de Listeria monocytogenes dans une usine d’abattage/découpe de porcs au Québec

Listeria monocytogenes (L. monocytogenes) est un pathogène majeur en santé publique comme les épisodes de 2008 dans les fromages et les charcuteries l’ont démontré. Au Canada, il n’y a pas de surveillance règlementaire de ce microorganisme dans les étapes précédant la transformation de produits prêts-à-manger. Ainsi, la présence et la circulation de ce microorganisme dans ces environnements est peu documentée. Pour décrire ces phénomènes, nous avons effectué un échantillonnage dans une usine d’abattage et de découpe de porcs au Québec, principalement dans les parcs d’attente, et dans l’environnement de l’abattage et de découpe : les échantillonages ont été effectués après lavage et désinfection sur une période de 2 ans. Un nombre de 874 échantillons a été récoltés. Le protocole de détection utilisé était inspiré de la méthode MFHPB-30 de Santé Canada. Les sérotypes ont été obtenus par PCR et les isolats caractérisés par un génotypage RFLP-PFGE en utilisant les enzymes de restriction Apa1 et Asc1. Nous avons détecté la présence de Listeria monocytogemes dans toutes ces étapes de la production. De ces échantillons positifs, 4 sérotypes (principalement 1/2b) ont émergé. Les patrons PFGE ont démontré la présence d’une variété de génotypes dans les zones d’attente et d’abattage de l’usine et la présence d’un type majeur dans l’environnement de la zone de découpe (le type 1 représentant 96.1% des souches à cette étape). De plus, nous avons démontré des liens entre les souches retrouvés au début de la production, en attente, et les souches retrouvées dans la zone de découpe. Ces résultats suggèrent que Listeria monocytogenes entre dans l’usine avec les animaux, contamine les étapes suivantes de la production et que certaines souches peuvent être sélectionnées et leur croissance favorisé dans l’environnement, devenant majoritaires, persistantes et préoccupantes en regars de la santé publique.

Méthode de génération de colonnes pour les problèmes de conception de réseaux avec coûts d’ajout de capacité

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles.

Defining the crime of aggression : cutting the Gordian knot ?

"Mémoire présenté à la Faculté des Études supérieures en vue de l'obtention du grade de LL.M. en Maîtrise en droit Option recherche"