# Reformulation de dualité forte pour l'optimisation bi-niveau de réseaux non-linéaires

Sophie Demassey

► To cite this version:

Sophie Demassey. Reformulation de dualité forte pour l'optimisation bi-niveau de réseaux non-linéaires. 24ème édition du congrès annuel de la Société Française de Recherche Opérationnelle et d'Aide à la Décision ROADEF 2023, Feb 2023, Rennes, France. hal-03940442

HAL Id: hal-03940442

https://minesparis-psl.hal.science/hal-03940442

Submitted on 16 Jan 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

Public Domain
# Reformulation de dualité forte pour l'optimisation bi-niveau de réseaux non-linéaires

Sophie Demassey¹

Centre de Mathématiques Appliquées, Mines Paris-PSL, Sophia-Antipolis, France
sophie.demassey@minesparis.psl.eu

**Mots-clés** : optimisation bi-niveau, réseaux non-linéaires, programmation non-convexe en nombres entiers

## 1 Optimisation des réseaux non-linéaires

Les graphes flot-potentiel ou flot-tension sont à la base des modèles de nombreux réseaux physiques : le flot mesure la quantité transportée à travers un composant/arc, et il est lié, en fonction de la conductivité ou de la résistance du composant, à la tension ou différence de potentiel qui mesurent l'énergie ou la pression aux bornes/nœuds du composant. [1] Si la relation flot-tension dans les composants peut être supposée linéaire dans certains contextes (réseaux électriques, de chaleur, vasculaires, etc.), ce n'est pas le cas dans les réseaux de transport d'eau et de gaz.

Le problème soujacent en simulation consiste à déterminer un équilibre flot-potentiel stationnaire, c'est à dire une affectation de valeurs de flot $q$ aux arcs et de potentiel $h$ aux nœuds, qui satisfait la contrainte de conservation du flot en chaque nœud et la relation flot-tension en chaque arc, à partir d'une affectation partielle, appelée conditions aux limites, et traduisant, par exemple, la valeur de la demande aux nœuds. En pratique, y compris dans les réseaux non-linéaires, les conditions aux limites assurent l'existence et l'unicité d'un équilibre stationnaire. Il peut être facilement calculé comme le zéro d'un système d'équations $f(q, h) = 0$ par l'algorithme de Newton-Raphson, ou comme la solution minimale d'une fonction strictement convexe $\min F(q)$ qui évalue la dissipation globale de l'énergie.

Les problèmes d'optimisation du dimensionnement ou pilotage des réseaux non-linéaires sont autrement plus difficiles à résoudre, qui ajoutent une couche combinatoire au problème d'équilibre. Statiques (dimensionnement) ou dynamiques (pilotage), ils peuvent se formuler, à l'instar des problèmes d'interdiction, comme la recherche d'un ou d'une suite de sous-graphes ($x \in \{0, 1\}^A$) satisfaisant certaines contraintes structurelles et qui, avec le ou les flots d'équilibre associés, minimisent une certaine fonction de coût. Ils exhibent ainsi une structure bi-niveau évidente couplant un problème discret (en $x$) au premier niveau avec un ou une suite de problèmes non-linéaires (en $q$ et $h$) au second niveau. Les sous-problèmes sont soit irréalisables, soit ils possèdent une solution unique.

Cette structure bi-niveau est exploitée de manière explicite dans les approches metaheuristiques couplées alors à un simulateur pour le calcul d'équilibre, mais généralement pas dans les approches de programmation mathématique, qui intègrent une approximation (typiquement, une approximation linéaire par morceaux) du système non-convexe $f_x(q) = 0$ dans le modèle mathématique de premier niveau, autrement dit, qui résolvent une approximation de la reformulation KKT du problème bi-niveau. Plusieurs travaux proposent de coupler les deux approches de manière itérative (type branch-and-bound et/ou génération de coupes) en maintenant en parallèle une relaxation mathématique $f_x(q) \in P$ pour diriger la recherche et pour le calcul de bornes inférieures et l'appui d'un simulateur pour le calcul de bornes supérieures $x = X \Rightarrow q^X \in \arg \min F_X(q)$. La convergence vers un optimum global est assurée par la finitude des solutions de premier niveau. Cependant, la dualité n'y est généralement pas exploitée
pour inférer des plans coupants pour le modèle de premier niveau ; à l'instar des méthodes OA ou Benders pour limiter l'énumération et accélérer la convergence, dans le cas convexe.

## 2 Reformulation de dualité forte

Dans cette présentation, nous nous intéressons principalement à l'optimisation dynamique avec stock (les châteaux d'eau) des réseaux pressurisés de distribution d'eau potable : le problème de *Pump Scheduling*.

Notre objectif est d'exploiter la structure bi-niveau non-linéaire du problème dans des approches de programmation mathématique, et en particulier, dans cette présentation, la reformulation de dualité forte : il s'agit de la formulation du problème intégrant au modèle de premier niveau la condition de dualité forte $F_x(q) \le G_x(h)$ (où le membre de droite est l'objectif dual, i.e. $\min F_x(q) = \max G_x(h)$, pour un sous-graphe $x$ donné).

Si, pour le problème statique de dimensionnement des réseaux d'eau gravitaires, dit *Water Network Design*, la reformulation de dualité forte offre une reformulation exacte convexe [2], ce n'est pas le cas pour dans le problème dynamique de *Pump Scheduling* du fait de la présence des éléments de stockage. En effet, le stockage se traduit ici par des contraintes couplantes intertemporelles ; ce qui empêche la séparation temporelle du modèle et augmente d'autant la combinatoire du problème. Par ailleurs, le stockage introduit dans la condition de dualité forte des termes bilinéaires $hq$, qui la rendent non-convexe. Pour autant, ces conditions peuvent être exploitées pour accélérer la convergence de méthodes existantes.

Dans cette présentation, nous commençons par présenter une étude de la reformulation non-convexe de dualité forte pour le problème de pump scheduling, puis en proposons deux utilisations :

- la linéarisation des conditions de dualité forte pour la génération de coupes pour accélérer une méthode exacte de branch-and-bound [3];

- la dualisation pour guider la recherche dans une méthode approchée de génération de colonnes [4].

## Références

[1] R. Tyrell Rockafellar. Network flows and monotropic optimization. Athena scientific, 1999.

[2] Byron Tasseff, Russell Bent, Marina A. Epelman, Donatella Pasqualini, Pascal Van Hentenyck. Exact Mixed-integer Convex Programming Formulation for Optimal Water Network Design. arXiv preprint arXiv:2010.03422, 2020.

[3] Gratien Bonvin, Sophie Demassey, Andrea Lodi. Pump scheduling in drinking water distribution networks with an LP/NLP-based branch and bound. *Optimization and Engineering*, 22:1275-1313, 2021.

[4] Gratien Bonvin, Sophie Demassey. Extended linear formulation of the pump scheduling problem in water distribution networks, *Open Proceedings*, International Network Optimization Conference, INOC:11-18, 2019.