Boris-Detienne

In this talk, we will introduce a new exact algorithm to solve two-stage stochastic linear programs. Based on the multicut Benders reformulation of such problems, with one subproblem for each scenario, this method relies on a partition of the subproblems into batches. The key idea is to solve at most iterations only a small proportion of the subproblems by detecting as soon as possible that a first-stage candidate solution cannot be proven optimal. We also propose a general framework to stabilize our algorithm, and show its finite convergence and exact behavior. We report an extensive computational study on large-scale instances of stochastic optimization literature that shows the efficiency of the proposed algorithm compared to nine alternative algorithms from the literature. We also obtain significant additional computational time savings using the primal stabilization schemes.

Welcome to my page

Many real-life decision-making problems under uncertainty include some form of interaction between the actions of the decision-maker and the realization of uncertain parameters. For instance, in medical appointment scheduling, no-shows of the patients are typically related to the schedules themselves whereas, in long-term medical treatments, the state of a patient evolves depending on past medication (decision-dependent uncertainty). On the other hand, in planning organ transplants, the uncertainty related to the compatibility of donors and patients needs to be investigated via expensive medical tests (information discovery) under a given budget constraint. It is therefore essential to incorporate the interactions of the decision-maker with the uncertain parameters within optimization under uncertainty models. This project proposes the study and solution of robust optimization models formalizing such interactions under a single mathematical framework with decision-dependent uncertainty sets.

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.

Robust optimization has evolved as a key paradigm for handling data uncertainty within mathematical optimization problems: it requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. Project DROI proposes to study primal and dual approximations for such problems.

EDF is the major French multinational electric utility company owned by the French state.

Optimizing nuclear unit outages is of significant economic importance for the French electricity company EDF, as these outages induce a substitute production by other more expensive means to fulfill electricity demand. This problem is quite challenging given the specific operating constraints of nuclear units, the stochasticity of both the demand and non-nuclear units availability, and the scale of the instances. To tackle these difficulties we used a combined decomposition approach. The operating constraints of the nuclear units were built into a Dantzig-Wolfe pricing subproblem whose solutions define the columns of a demand covering formulation. The scenarios of demand and non-nuclear units availability are handled in a Benders decomposition. Our approach is shown to scale up to the real-life instances of the French nuclear fleet.

Supervisors

• Ayse Arslan (Edge)
• Boris Detienne (Edge)
• Aurélien Froger (Edge)

Publications

Collaborations

EDF

EDF-Inria Challenge - Generation expansion planning problems

EDF is the major French multinational electric utility company owned by the French state. Our collaboration is part of the EDF-Inria Challenge, and specifically a project titled “Decomposition algorithms for solving generation expansion planning problems”.
[Read more]

---

Seminars

Mariam Sangaré

Postdoctoral researcher, Centre Inria de l'université de Bordeaux

Cooperative game theory and cost allocation in energy communities

 February 20, 2025

An energy community (EC) is a legal entity involving prosumers and consumers who produce, consume, and exchange energy. The members of these communities can cooperate to maximize the community’s social welfare. In practice, this naturally raises the question of cost sharing in the community, as the members may have different contributions to social welfare. In this presentation, we empirically highlight the benefits of cooperation for the community and the individual members. Then, we present some cost-sharing mechanisms that guarantee fairness and the stability of the grand coalition composed of all prosumers and consumers. Finally, we present some results on instances built with real-world data from our partner Sween’s demonstrator, Smart Lou Quila, in South France.

[Read more]

---

See all related topics to #mariam-sangare

Supervisors

• Ayse Arslan (Edge)
• Boris Detienne (Edge)

Publications

Projects

DROI

Primal and dual bounds for adjustable robust optimization

Robust optimization has evolved as a key paradigm for handling data uncertainty within mathematical optimization problems: it requires little historical information, can be used without characterizing probability distributions and often leads to tractable optimization problems that can be treated with existing deterministic optimization paradigms. However, the picture is more complex when some of the decisions (referred to as recourse decisions) can be adjusted after the uncertain data is known, to mitigate the effects of uncertainty, leading to adjustable robust optimization problems. Adjustable problems with discrete variables or multiple decision periods are particularly difficult to solve and, up to now, no scalable exact method has emerged. Project DROI proposes to study primal and dual approximations for such problems.

[Read more]

---

New results

A semi-infinite constraint generation algorithm for two-stage robust optimization problems

 July 24, 2025

Authors: Patxi Flambard, Ayse Nur Arslan, Boris Detienne
Abstract: In this paper, we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse. These problems have been the subject of exact solution approaches, notably constraint generation and constraint-and-column generat [Read more]

---

Seminars

Patxi Flambard

PhD student, Centre Inria de l'université de Bordeaux

A semi-infinite constraint generation algorithm for adjustable robust optimization

 April 17, 2025

In this talk we consider two-stage linear adjustable robust optimization problems with continuous and fixed recourse. These problems have been the subject of exact solution approaches, notably, constraint generation (CG) and constraint-and-column generation (CCG). Both approaches repose on an exponential-sized reformulation of the problem which uses a large number of constraints or constraints and variables. The decomposition algorithms then solve and reinforce a relaxation of the aforementioned reformulation through the iterations which require the solution of bilinear separation problems. Here, we present an alternative approach reposing on a novel reformulation of the problem with an exponential number of semi-infinite constraints. We present a nested decomposition algorithm to deal with the exponential and semi-infinite natures of our formulation separately. We argue that our algorithm will lead to a reduced number of bilinear separation problems solved while providing a high quality relaxation. We perform a detailed numerical study that showcases the superior performance of our proposed approach compared to the state-of-the-art and evaluates the contribution of different algorithmic components.

[Read more]

---

See all related topics to #patxi-flambard

The project:

Strategic Power Systems Development for the Future (PowerDev), funded by PEPR TASE, studies optimization methods and reliability/resilience engineering applied to large-scale electrical power systems. The project is led by CentraleSupélec at the University of Paris Saclay and is composed of a consortium of higher education institutions across France (CentraleSupelec, UVSQ, University Grenoble Alpes), as well as research organizations (Inria, CNRS).

Research topic and objectives:

Modern power systems are expected to become increasingly complex to design and operate due to the growing number of renewable energy sources (RES). Renewable energy generation is, by nature, intermittent and introduces an amount of uncertainty that severely affects the physical responses of the power system, particularly in terms of voltage control and frequency regulation [1]. Moreover, RES integration within the power system requires the introduction of many new power electronic devices, which add to the system’s complexity and increase its possible failure modes [2,3]. Combined with unexpected initiating events, these two main features can lead to cascading failure risks, triggering disastrous consequences to the power grid and, most notably, large-scale blackouts [4-7]. The economic and societal consequences to the impacted regions are usually massive, with economic loss measured in the tens of billions of dollars [8]. The main objective of this project is to evaluate and optimize the resilience of power systems in the context of a massive insertion of renewable energies. The project aims to elaborate a comprehensive and integrated set of decision support tools by considering extreme events in present and future climates, the complexity of the power grid, and socio-economic scenarios.

RTE is France’s Transmission System Operator. It is in charge of the high and ultra-high voltage electricity transmission network in France and of the electricity exchanges with the neighbouring countries. Its main role is to guarantee in real time the balance between electricity production and consumption.

In 2019, a contract was signed with RTE for a PhD on algorithms to speedup Benders’ decomposition. The PhD student was Xavier Blanchot under the supervision of François Clautiaux and Aurélien Froger.

SNCF is the French Railway operator. This project was funded by TER Nouvelle Aquitaine.

This collaboration funded the PhD thesis of Mohamed Benkirane. The subject of the thesis was an integrated optimization approach for timetable and rolling stock rotations planning in the context of passenger railway traffic. Our approach was based on a time-space hyper-graph model, which can handle trains composed by multiple self-powered railcars on part of their paths.