Methods for solving combinatorial pricing problems

Abstract

Le problème de tarification combinatoire (CPP) ou le jeu de tarification de Stackelberg est une classe de problèmes d’optimisation bi-niveaux comprenant deux décideurs dans un ordre séquentiel. Le premier décideur, le leader, maximise ses revenus en contrôlant les prix d’un ensemble de ressources. Le deuxième décideur, le suiveur, réagit aux prix et sélectionne un sous-ensemble de ressources selon un problème d’optimisation combinatoire. Selon le problème du suiveur, le CPP peut être très difficile à résoudre. Cette thèse présente trois articles couvrant plusieurs méthodes de solution exacte pour le CPP. Le premier article aborde la modélisation et le prétraitement pour une spécialisation du CPP : le problème de tarification du réseau (NPP), dans lequel le problème du suiveur est un problème du plus court chemin. Les formulations du NPP sont organisées dans un cadre général qui établit les liens entre elles. Le deuxième article se concentre sur la version à plusieurs marchandises du NPP. À partir des résultats de l’analyse convexe, nous dérivons une nouvelle formulation du NPP et prouvons que le NPP évolue de manière polynomiale par rapport au nombre de marchandises, étant donné que le nombre d’arcs à péage est fixe. Le troisième article nous ramène au CPP général, dans lequel les problèmes du suiveur sont NP-difficiles. En utilisant deux modèles de programmation dynamique différents, les problèmes du suiveur sont convertis en programmes linéaires, auxquels la dualité forte peut être appliquée. En raison de la nature NP-difficile de ces problèmes, des schémas de génération dynamique de contraintes sont proposés. Les méthodes de solution décrites dans chaque article sont étayées par des résultats expérimentaux, montrant leur efficacité en pratique. Cette thèse approfondit notre compréhension de la structure du CPP et introduit des méthodologies innovantes pour y faire face, contribuant ainsi à de nouvelles perspectives pour aborder les problèmes de tarification et bi-niveau en général.

The combinatorial pricing problem (CPP) or Stackelberg pricing game is a class of bilevel optimization problems that consist of two decision makers in sequential order. The first decision maker, the leader, maximizes their revenue by controlling the prices of a set of resources. The second decision maker, the follower, reacts to the prices and selects a subset of resources according to a combinatorial optimization problem. Depending on the follower’s problem, the CPP can be very challenging to solve. This thesis presents three articles covering several exact solution methods for the CPP. The first article addresses the modeling and preprocessing for a specialization of the CPP: the network pricing problem (NPP), in which the follower’s problem is a shortest path problem. The formulations of the NPP are organized in a general framework which establishes the links between them. The second article focuses on the multi-commodity version of the NPP. From the results in convex analysis, we derive a novel formulation of the NPP and with it, we prove that the NPP scales polynomially with respect to the number of commodities, given that the number of tolled arcs is fixed. The third article leads us back to the general CPP, in which the follower’s problems are NP-hard. By utilizing two different dynamic programming models, the follower’s problems are converted into linear programs, to which strong duality can be applied. Due to the NP-hard nature of these problems, dynamic constraint generation schemes are proposed. The solution methods described in each article are backed up with experimental results, showing that they are effective in practice. This thesis deepens our comprehension of the CPP structure and introduces innovative methodologies for addressing it, thereby contributing new perspectives to tackle pricing and bilevel problems in general.