L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité
Thèse ou mémoire
2015-04 (octroi du grade: 2015-09-23)
Auteur·e·s
Directeur·trice·s de recherche
Cycle d'études
MaîtriseProgramme
InformatiqueRésumé·s
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. The network design problem has been studied extensively in the field of operational
research given its characteristics and applications in many areas such as transportation, communications, and logistics.
We are particularly interested in solving the multicommodity uncapacitated fixed-charge
network design problem, with the aim of meeting the demands of all the products
while minimizing the total cost of transporting commodities and designing the network.
This problem is typically modeled as a linear integer program including continuous variables. To solve it, we applied the exact method of Branch-and-bound based on linear
relaxation with a stopping criterion, while exploiting the column generation and cutting-plane methods.
We tested our Branch-and-Price-and-Cut algorithm on 156 instances divided into five
groups of different sizes, and we compared it with Cplex, one of the best mathematical
optimization solvers. We compare it also with the Branch-and-Cut method.
Numerical results show that our method is competitive and perform better especially
on large-scale instances with many commodities.
Ce document diffusé sur Papyrus est la propriété exclusive des titulaires des droits d'auteur et est protégé par la Loi sur le droit d'auteur (L.R.C. (1985), ch. C-42). Il peut être utilisé dans le cadre d'une utilisation équitable et non commerciale, à des fins d'étude privée ou de recherche, de critique ou de compte-rendu comme le prévoit la Loi. Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.