Learning-Augmented Optimization for Online Network Design // Learning-Augmented Optimization for Online Network Design

Network design is typically treated as an offline planning task: a topology is computed before deployment and then remains largely unchanged during operation. However, many real-world networks operate in dynamic environments where demand and operating conditions evolve over time. In such settings, adapting the network during operation may significantly improve performance. While this idea appears in some application domains, it has not yet been systematically formalized from an algorithmic perspective. This project aims to develop a general framework for the online design of dynamic networks.

We will focus on networks built as an overlay on top of underlying physical substrates. Examples include virtual networks (e.g., 5G network slices), which are reshaped to match changing workloads;[1,2] programmable communication infrastructures or reconfigurable data-centers, where connectivity can be modified to better match traffic patterns;[3,4] All these examples are overlays on top of a substrate network, which is composed of physical servers and links. Other examples are public transport networks (composed of several lines), operated on top of the road network (substrate network). In all these settings, we consider the topology of the overlay network as a decision variable rather than a fixed input.

Uncertainty in these systems originates from two exogenous drivers: (i) the demand and (ii) the properties of the substrate network. Demand (i) can be represented by sequences of requests or by commodity flows. Properties (ii) may be link capacity, congestion levels, failures, or latency conditions in communication infrastructures, which can alter the performance of overlay virtual networks built on top of them. Similarly, fluctuations in traffic conditions in the road network (substrate) modify the effective travel times of bus lines (overlay network). We assume exogenous drivers are stochastic, possibly non-stationary, and unknown in advance. In such cases, performance can be improved if the overlay topology is allowed to evolve dynamically so as to adapt to changing demand and exogenous variations of the substrate network.

Two further challenges need to be tackled. First, the state of the network is often only partially observable. Measurements are typically sparse, incomplete, and possibly “multimodal” (i.e., of different nature). This complicates the task of determining appropriate overlay network reconfigurations. Second, real networks need a certain time of reconfiguration (e.g., the time to move vehicles in a public transport network, the time to migrate microservices in a virtual computer network). This requires making proactive design decisions sufficiently in advance.

There exists a mature theory of dynamic networks, but its focus is descriptive: discovering patterns, learning representations, or predicting future links.[5–7] In contrast, we focus on prescriptive capabilities, i.e., deciding how the network should evolve so as to maintain certain performance objectives.

Although dynamic network design problems can be formulated using generic combinatorial optimization models, such approaches typically treat the network simply as a collection of decision variables and constraints. In contrast, a large body of work shows that network design problems can often be solved much more efficiently by exploiting structural properties of graphs.

The overarching aim of the project is to establish a general methodology for the online design of dynamic networks in the presence of uncertain and partially observable exogenous drivers.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Network design is typically treated as an offline planning task: a topology is computed before deployment and then remains largely unchanged during operation. However, many real-world networks operate in dynamic environments where demand and operating conditions evolve over time. In such settings, adapting the network during operation may significantly improve performance. While this idea appears in some application domains, it has not yet been systematically formalized from an algorithmic perspective. This project aims to develop a general framework for the online design of dynamic networks.

We will focus on networks built as an overlay on top of underlying physical substrates. Examples include virtual networks (e.g., 5G network slices), which are reshaped to match changing workloads;[1,2] programmable communication infrastructures or reconfigurable data-centers, where connectivity can be modified to better match traffic patterns;[3,4] All these examples are overlays on top of a substrate network, which is composed of physical servers and links. Other examples are public transport networks (composed of several lines), operated on top of the road network (substrate network). In all these settings, we consider the topology of the overlay network as a decision variable rather than a fixed input.

Uncertainty in these systems originates from two exogenous drivers: (i) the demand and (ii) the properties of the substrate network. Demand (i) can be represented by sequences of requests or by commodity flows. Properties (ii) may be link capacity, congestion levels, failures, or latency conditions in communication infrastructures, which can alter the performance of overlay virtual networks built on top of them. Similarly, fluctuations in traffic conditions in the road network (substrate) modify the effective travel times of bus lines (overlay network). We assume exogenous drivers are stochastic, possibly non-stationary, and unknown in advance. In such cases, performance can be improved if the overlay topology is allowed to evolve dynamically so as to adapt to changing demand and exogenous variations of the substrate network.

Two further challenges need to be tackled. First, the state of the network is often only partially observable. Measurements are typically sparse, incomplete, and possibly “multimodal” (i.e., of different nature). This complicates the task of determining appropriate overlay network reconfigurations. Second, real networks need a certain time of reconfiguration (e.g., the time to move vehicles in a public transport network, the time to migrate microservices in a virtual computer network). This requires making proactive design decisions sufficiently in advance.

There exists a mature theory of dynamic networks, but its focus is descriptive: discovering patterns, learning representations, or predicting future links.[5–7] In contrast, we focus on prescriptive capabilities, i.e., deciding how the network should evolve so as to maintain certain performance objectives.

Although dynamic network design problems can be formulated using generic combinatorial optimization models, such approaches typically treat the network simply as a collection of decision variables and constraints. In contrast, a large body of work shows that network design problems can often be solved much more efficiently by exploiting structural properties of graphs (see §4.1).

The overarching aim of the project is to establish a general methodology for the online design of dynamic networks in the presence of uncertain and partially observable exogenous drivers.
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/11/2026

Concours IPP ou école membre*Contrat doctoral Hi!Paris*

Institut Polytechnique de Paris Télécom SudParis

626 Ecole Doctorale de l'Institut Polytechnique de Paris

Excellent analytical skills To apply, please send: - Your CV, - An explanation of 5 lines explaining why you are the best fit for this position (with factual non-vague or generic elements) - All the marks of your BSc and MSc level courses; Sending your ranking is not mandatory (but it is a big plus). Send all this material to andrea.araldo@telecom-sudparis.eu VISA is sponsored. The PhD is fully funded
Excellent analytical skills To apply, please send: - Your CV, - An explanation of 5 lines explaining why you are the best fit for this position (with factual non-vague or generic elements) - All the marks of your BSc and MSc level courses; Sending your ranking is not mandatory (but it is a big plus). Send all this material to andrea.araldo@telecom-sudparis.eu VISA is sponsored. The PhD is fully funded