Algorithme de branch-and-price-and-cut pour le problème de conception de réseaux avec coûts fixes, capacités et un seul produit

De nombreux problèmes liés aux domaines du transport, des télécommunications et de la logistique peuvent être modélisés comme des problèmes de conception de réseaux. Le problème classique consiste à transporter un flot (données, personnes, produits, etc.) sur un réseau sous un certain nombre de contraintes dans le but de satisfaire la demande, tout en minimisant les coûts. Dans ce mémoire, on se propose d'étudier le problème de conception de réseaux avec coûts fixes, capacités et un seul produit, qu'on transforme en un problème équivalent à plusieurs produits de façon à améliorer la valeur de la borne inférieure provenant de la relaxation continue du modèle. La méthode que nous présentons pour la résolution de ce problème est une méthode exacte de branch-and-price-and-cut avec une condition d'arrêt, dans laquelle nous exploitons à la fois la méthode de génération de colonnes, la méthode de génération de coupes et l'algorithme de branch-and-bound. Ces méthodes figurent parmi les techniques les plus utilisées en programmation linéaire en nombres entiers. Nous testons notre méthode sur deux groupes d'instances de tailles différentes (gran-des et très grandes), et nous la comparons avec les résultats donnés par CPLEX, un des meilleurs logiciels permettant de résoudre des problèmes d'optimisation mathématique, ainsi qu’avec une méthode de branch-and-cut. Il s'est avéré que notre méthode est prometteuse et peut donner de bons résultats, en particulier pour les instances de très grandes tailles.

Modernizing Mount Royal Park : Montréal’s Jungle in the 1950s

Durant les années 1950, les autorités municipales, sous la pression du département de la police, ont demandé le déboisement d’une section du parc du Mont-Royal. Cette section, communément appelée la « Jungle » et principalement composée de broussailles, de buissons et d’arbres, était fréquentée par une clientèle considérée comme indésirable. Cette dernière comprenait, essentiellement, des alcooliques, des voyous, des pervers, et, surtout, des homosexuels. Leur éradication s’est alors déployée selon un plan en trois étapes qui avait pour objectif de simplifier les techniques de surveillance utilisées par le département de la police. D’abord, une augmentation de l’éclairage, puis, le déboisement de la « Jungle », et, finalement, la construction d’une route, aujourd’hui connue sous le nom de Camillien-Houde. Le parc devenait ainsi plus accessible et plus sécuritaire. Les coupes, que l’on a appelées les « coupes de la moralité », ont eu un effet considérable sur l’environnement et la composition écologique du parc, donnant, entre autres, aux Montréalais, l’impression que le parc était devenu chauve (ce qui lui conféra d’ailleurs le surnom de Mont Chauve). Les transformations du parc du Mont-Royal n’étaient cependant pas limitées à sa Jungle. En fait, des modifications furent aussi mises en application dans d’autres sections considérées comme sous-développées. La métamorphose du parc et de sa « Jungle » était un acte de développement caractéristique de l’ère moderniste de la planification du Montréal d’après-guerre. La re-planification du parc du Mont-Royal témoigne ainsi d’une volonté sans bornes des autorités d’instaurer la moralité et la modernité dans la ville, volonté qui aura pour conséquence d’altérer la composition écologique du parc. C’est ce qui sera à l’origine d’une campagne nommée « Save-the-Mountain Movement », qui a cherché à empêcher la modernisation de l’espace et milité pour la réhabilitation du parc en tant que boisé paisible.