Nouvelle contraction algébrique appliquée au problème de tarification de réseau
Thèse ou mémoire / Thesis or Dissertation
Date de publication
Autrices et auteurs
Identifiant ORCID de l’auteur
Contributrices et contributeurs
Direction de recherche
Publié dans
Date de la Conférence
Lieu de la Conférence
Éditeur
Cycle d'études
Maîtrise / Master's
Programme
Affiliation
Mots-clés
- Optimisation biniveaux
- Théorie des graphes
- Réduction de graphe
- Bilevel optimization
- Graph theory
- Graph reduction
Organisme subventionnaire
Résumé
Résumé
Le problème de tarification de réseau est un problème classique d’optimisation combinatoire dans un graphe. Dans celui-ci, un fournisseur cherche à maximiser le profit tiré d’un sous-ensemble d’arcs qu’il contrôle aux dépens d’usagers cherchant à minimiser leur coût de passage. La littérature sur ce programme biniveaux présente des reformulations et des techniques de prétraitement, mais les techniques de réduction de graphe sont rares. Dans ce travail, nous proposons une nouvelle réduction de graphe et l’appliquons à ce problème. D’une part, nous formalisons algébriquement la réduction de graphe basée sur la fusion d’arcs et d’autre part, nous l’appliquons au processus de résolution du problème de tarification. Au vu de la grande dispersion des résultats, il est vraisemblable qu’il n’existe aucune garantie théorique. Pourtant, il y a de nombreux cas où la réduction est bénéfique. Ces transformations sont issues d’un échantillonnage dont le procédé est lié à la détermination des cliques maximum, c’est-à-dire les plus grands ensembles de sommets deux à deux adjacents. Un algorithme simple pour déterminer les cliques maximum ayant des résultats préliminaires prometteurs est présenté. Les résultats préliminaires d’application de la transformation de graphe indiquent que des gains de temps substantiels sont possibles, mais qu’une connaissance préalable du réseau est nécessaire à l’obtention de bonnes réductions. Bref, ce mémoire présente une nouvelle transformation de graphe, en fait la formalisation algébrique puis en fait l’application sur un problème biniveaux.
The network pricing problem is a classic combinatorial optimization problem in a graph. In this problem, a provider seeks to maximize the profit from a subset of arcs it controls at the expense of users who seek to minimize their cost of passage. The literature on this bilevel program presents reformulations and preprocessing techniques, but graph reduction techniques are rare. In this work, we propose a new graph reduction and apply it to this problem. On one hand, we algebraically formalize graph reduction based on arc merging, and, on the other hand, we apply it to the process of solving the pricing problem. Given the wide dispersion of the results, it is likely that there are no theoretical guarantees. However, there are many cases where the reduction is beneficial. These transformations are the result of sampling, whose process is linked to the determination of maximum cliques, i.e., the largest sets of adjacent vertices. A simple algorithm for determining maximum cliques is presented, with promising preliminary results. As for the application of graph transformation, the preliminary results can show substantial time savings, but also lead to the conclusion that prior knowledge of the network is necessary to obtain good reductions. In short, this work presents a new graph transformation, formalizes it algebraically and then applies it to a bilevel problem.
The network pricing problem is a classic combinatorial optimization problem in a graph. In this problem, a provider seeks to maximize the profit from a subset of arcs it controls at the expense of users who seek to minimize their cost of passage. The literature on this bilevel program presents reformulations and preprocessing techniques, but graph reduction techniques are rare. In this work, we propose a new graph reduction and apply it to this problem. On one hand, we algebraically formalize graph reduction based on arc merging, and, on the other hand, we apply it to the process of solving the pricing problem. Given the wide dispersion of the results, it is likely that there are no theoretical guarantees. However, there are many cases where the reduction is beneficial. These transformations are the result of sampling, whose process is linked to the determination of maximum cliques, i.e., the largest sets of adjacent vertices. A simple algorithm for determining maximum cliques is presented, with promising preliminary results. As for the application of graph transformation, the preliminary results can show substantial time savings, but also lead to the conclusion that prior knowledge of the network is necessary to obtain good reductions. In short, this work presents a new graph transformation, formalizes it algebraically and then applies it to a bilevel problem.
Table des matières
Notes
Notes
Autre version linguistique
Ensemble de données lié
Licence
Approbation
Évaluation
Complété par
Référencé par
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). Sauf si le document est diffusé sous une licence Creative Commons, il ne peut être utilisé que dans le cadre d'une utilisation équitable et non commerciale comme le prévoit la Loi (i.e. à des fins d'étude privée ou de recherche, de critique ou de compte-rendu). Pour toute autre utilisation, une autorisation écrite des titulaires des droits d'auteur sera nécessaire.