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.

Une littérature du décloisonnement : la construction de la figure de l'écrivain et du littéraire dans Comment faire l'amour avec un Nègre sans se fatiguer et Cette grenade dans la main du jeune Nègre est-elle une arme ou un fruit? de Dany Laferrière

Dany Laferrière, récemment admis à la prestigieuse Académie française, a produit une œuvre considérable au cours des trente dernières années. Deux de ces premiers romans, Comment faire l’amour avec un Nègre sans se fatiguer et Cette grenade dans la main du jeune Nègre est-elle une arme ou un fruit?, sont caractérisés par une intertextualité riche et variée. La trame narrative de ces deux romans est construite par fragments. Dans le premier texte, on retrouve un écrivain fictif qui procède à l’écriture d’un roman qu’il nomme Paradis du dragueur nègre. Dans le deuxième roman, nous retrouvons le même écrivain, mais ce dernier est plutôt employé par un magazine de la côte est afin de rédiger un reportage sur l’Amérique. Dans les deux cas, il y a une mise en scène de l’écriture par un écrivain fictif qui présente beaucoup de ressemblances avec Laferrière lui-même. Le lecteur assiste à la construction du récit qu’il est en train de lire à travers une autofiction originale. Il y a donc une multitude de ressemblances, et mêmes correspondances, entre les deux récits. Les deux romans de Laferrière s’inscrivent par leur thème, leur style et leur genre dans une « généalogie » de textes qui peuvent être regroupés en « familles » littéraires. Nous tenterons, dans le mémoire qui suit, de définir et de comprendre le rôle de ces « familles » et d’illustrer comment l’appropriation de ces textes permet à l’auteur à la fois de s’en inspirer et de s’en distancer. Il s’agira donc, dans les deux premiers chapitres, d’étudier les références intertextuelles appartenant à ces deux « familles » d’écrivains pour ensuite étudier plus particulièrement la construction de la figure de l’écrivain et de son espace littéraire à travers ces deux œuvres. MOT-CLÉS : Dany Laferrière ; intertextualité ; autofiction ; roman contemporain ; littérature québécoise.