| Titre : | Conception de réseaux de télécommunications fiables avec contrainte de budget | | Type de document : | projet fin études | | Auteurs : | Maria EL HALLAOUI, Auteur | | Langues : | Français (fre) | | Catégories : | e-Logistique
| | Mots-clĂ©s : | FiabilitĂ© de rĂ©seaux, graphe k-arĂŞte-connexe, contrainte valide, algorithme de sĂ©paration, approche plyĂ©drale, algorithme de coupes et branchements. | | Index. dĂ©cimale : | 1968/18 | | RĂ©sumĂ© : | Le problème de conception de réseaux a des applications dans plusieurs domaines notamment les télécommunications et le transport. L'objectif est de concevoir des réseaux efficaces, fiables et à coût réduit tout en proposant des solutions pour satisfaire la demande des utilisateurs et leurs exigences en terme d'efficacité et fiabilité.
Nous nous intéressons plus particulièrement dans ce projet à la conception de réseaux fiables à moindre coût et dont le temps d'installation ne dépasse pas un temps limite. Ce problème est appelé problème du sous graphe 2-arête-connexe avec contrainte de budget.
Nous allons étudier une approche polyédrale pour ce problème qui est bien un problème d'optimisation combinatoire. En effet, A travers une modélisation par les graphes et une formulation mathématique sous forme de programme linéaire en 0-1 que nous proposons, nous expliquerons notre démarche de résolution du problème à savoir l'algorithme de coupes et branchements et nous nous intéressons plus particulièrement à la phase de séparation des contraintes. Nous présentons également deux classes d'inégalités valides pouvant améliorer la formulation de base.
Afin d'obtenir des résultats expérimentaux et pouvoir conclure sur l'efficacité des nouvelles contraintes valides utilisées en pratique et l'impact de la variance du budget sur la résolution de notre problème, nous allons implémenter notre algorithme de Branch and cut en utilisant le langage C++ et le solveur CPLEX et nous allons le tester sur des instances de la SNDLIB[12] et la TSPLIB[13].
|
Conception de réseaux de télécommunications fiables avec contrainte de budget [projet fin études] / Maria EL HALLAOUI, Auteur . - [s.d.]. Langues : Français ( fre) | Catégories : | e-Logistique
| | Mots-clĂ©s : | FiabilitĂ© de rĂ©seaux, graphe k-arĂŞte-connexe, contrainte valide, algorithme de sĂ©paration, approche plyĂ©drale, algorithme de coupes et branchements. | | Index. dĂ©cimale : | 1968/18 | | RĂ©sumĂ© : | Le problème de conception de réseaux a des applications dans plusieurs domaines notamment les télécommunications et le transport. L'objectif est de concevoir des réseaux efficaces, fiables et à coût réduit tout en proposant des solutions pour satisfaire la demande des utilisateurs et leurs exigences en terme d'efficacité et fiabilité.
Nous nous intéressons plus particulièrement dans ce projet à la conception de réseaux fiables à moindre coût et dont le temps d'installation ne dépasse pas un temps limite. Ce problème est appelé problème du sous graphe 2-arête-connexe avec contrainte de budget.
Nous allons étudier une approche polyédrale pour ce problème qui est bien un problème d'optimisation combinatoire. En effet, A travers une modélisation par les graphes et une formulation mathématique sous forme de programme linéaire en 0-1 que nous proposons, nous expliquerons notre démarche de résolution du problème à savoir l'algorithme de coupes et branchements et nous nous intéressons plus particulièrement à la phase de séparation des contraintes. Nous présentons également deux classes d'inégalités valides pouvant améliorer la formulation de base.
Afin d'obtenir des résultats expérimentaux et pouvoir conclure sur l'efficacité des nouvelles contraintes valides utilisées en pratique et l'impact de la variance du budget sur la résolution de notre problème, nous allons implémenter notre algorithme de Branch and cut en utilisant le langage C++ et le solveur CPLEX et nous allons le tester sur des instances de la SNDLIB[12] et la TSPLIB[13].
|
|
196/00 
Faire une suggestion Affiner la recherche
Conception de réseaux de télécommunications fiables avec contrainte de budget / Maria EL HALLAOUI
