L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité
dc.contributor.advisor | Gendron, Bernard | |
dc.contributor.author | Grainia, Sameh | |
dc.date.accessioned | 2015-10-26T18:59:05Z | |
dc.date.available | NO_RESTRICTION | fr |
dc.date.available | 2015-10-26T18:59:05Z | |
dc.date.issued | 2015-09-23 | |
dc.date.submitted | 2015-04 | |
dc.identifier.uri | http://hdl.handle.net/1866/12485 | |
dc.subject | Problème de conception de réseaux | fr |
dc.subject | Génération de colonnes | fr |
dc.subject | Génération de coupes | fr |
dc.subject | Branch-and-Bound | fr |
dc.subject | Multicommodity network design problem | fr |
dc.subject | Column generation | fr |
dc.subject | Cutting-plane method | fr |
dc.subject.other | Applied Sciences - Operations Research / Sciences appliqués et technologie - Recherche opérationnelle (UMI : 0796) | fr |
dc.title | L'algorithme de Branch and Price and Cut pour le problème de conception de réseaux avec coûts fixes et sans capacité | fr |
dc.type | Thèse ou mémoire / Thesis or Dissertation | |
etd.degree.discipline | Informatique | fr |
etd.degree.grantor | Université de Montréal | fr |
etd.degree.level | Maîtrise / Master's | fr |
etd.degree.name | M. Sc. | fr |
dcterms.abstract | 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. | fr |
dcterms.abstract | 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. | fr |
dcterms.language | fra | fr |
Files in this item
This item appears in the following Collection(s)
This document disseminated on Papyrus is the exclusive property of the copyright holders and is protected by the Copyright Act (R.S.C. 1985, c. C-42). It may be used for fair dealing and non-commercial purposes, for private study or research, criticism and review as provided by law. For any other use, written authorization from the copyright holders is required.