Bonjour à tous,

Vous êtes cordialement invités à la soutenance de thèse de Quang Minh Bui, telle qu'annoncée ci-dessous

Jury

Résumé:

The combinatorial pricing problem (CPP) or Stackelberg pricing game is a class of bilevel optimization problems that consist of 2 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 3 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 2 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.