This project aims at proposing theoretical and practical results for hard combinatorial optimization problems in an uncertain environment. These problems have in common the fact that the parameters needed to assess the validity of the solution and compute its cost are unknown. Uncertainty in decision making can be caused by several external factors. The most common are related to stochastic parameters (service demand, time needed for a task, prices, …). Incomplete information can also come from the presence of competitors whose policies are not known to the decision maker.

When the incomplete information comes from some stochastic parameters, two major paradigms are commonly used: stochastic optimization (including chance-constrained optimization), and robust optimization. In the former case, one assumes that a probability distribution is known for the uncertain parameters. In the latter, only its support is used, i.e. one only needs to define plausible scenarios without knowing their probability of occurrence.

When the incomplete information comes from competitor policies, game theory offers a set of tools for addressing the resulting problem. Stackelberg games have the capability to model a situation where an opponent (so-called follower) reacts to the decisions that are taken by the decision-maker (leader).

Both uncertain and game-theoretical combinatorial optimization problems raise considerable difficulties. They have in common the fact that one has to solve intertwined optimization problems (multi-stage or multi-level), where even the existence of a solution can be theoretically and computationally challenging. As an example, for Stackelberg games, even if both the leader and follower have an LP to solve, the problem becomes NP-hard.

In this project, we focus on a broad class of optimization problems that combine network-design and routing problems. In these problems, the goal is to decide the structure of a network that will be used to offer some services to customers or citizens, and policies for operating the network and modifying dynamically the design of this network along a given time period to adapt to the new situation.

The project is structured over the following topics:

  1. Theoretical analysis and algorithms for multi-stage network design
  2. Finding suitable approximations for routing problems
  3. Theoretical analysis, algorithms, and case studies for joint multi-stage network design and routing

The consortium

  • French partners

    • Bordeaux Mathematics institute, University of Bordeaux (principal coordinator: Francois Clautiaux)
    • Kedge Business School (local coordinator: Olga Battaïa)

  • Russian partners

    • Sobolev Institute of Mathematics (principal coordinator: Yuri Kochetov)