Nouvelle contraction algébrique appliquée au problème de tarification de réseau

Abstract

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.