Thèse Learning-Augmented Optimization For Online Network Design H/F - 75

Établissement : Institut Polytechnique de Paris Télécom SudParis
École doctorale : Ecole Doctorale de l'Institut Polytechnique de Paris
Laboratoire de recherche : SAMOVAR - Services répartis, Architectures, Modélisation, Validation, Administration des Réseaux
Direction de la thèse : Andrea ARALDO ORCID 0000000254486646
Début de la thèse : 2026-11-01
Date limite de candidature : 2026-04-09T23:59:59

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.

SECTION - Relation to existing literature and algorithmic positioning

SUBSECTION - Online network design

For example, graph-specific techniques allow large networks to be represented through smaller structures that preserve key connectivity properties while enabling faster algorithms for network optimization tasks [12, -1]. Similarly, recent work develops scalable algorithmic frameworks for network design problems by maintaining compact graph structures while processing large input graphs [13, -3].

However, these works study settings in which the objective is to compute a single network design for a given problem instance. Even when the input graph is revealed progressively, the goal remains to construct one final network satisfying the design requirements. In contrast, the present project studies online design of dynamic networks, where the network topology itself must evolve over time in response to uncertain and partially observed operating conditions. Extending graph-structure-based algorithmic techniques to this dynamic and anticipatory setting is therefore a central challenge of the proposed research.

Settings where requests arrive sequentially and an agent incrementally purchases edges to satisfy them have been studied, and algorithms with competitive ratios have been proposed [14,15; 16, Ch.11]. However, that line of work typically assumes monotone growth: edges, once purchased, remain available forever. Subsequent work relaxed this assumption through leasing or rental variants of online optimization problems, where resources may be acquired temporarily and expire over time [17,18]. In these models, decisions primarily concern how long individual resources should remain active while demands are served over a largely fixed underlying structure. In contrast, our project treats the network topology itself as the decision variable, requiring the construction and modification of global connectivity patterns over time so as to adapt to stochastic demand and substrate variations.

Another line of work, on dynamic graph algorithms, assumes an exogenous process that inserts or deletes edges. An agent aims to update, in the most time-efficient way, auxiliary structures such as connectivity certificates, spanning forests, or approximate shortest-path distances [19-21]. In contrast, in our setting topology modifications are decision variables, rather than exogenous inputs.

A crucial distinction with classical online network design is that, in those models, connectivity demands arrive and the algorithm incrementally augments the network to satisfy them. In contrast, the present project introduces the additional challenge of decision lag, which requires designing future overlay topologies before the corresponding demands and substrate conditions are fully known. We therefore seek proactive rather than reactive design decisions.

SUBSECTION - Online routing

Another line of work studies competitive algorithms to route requests or flows that arrive over time [22; 16, Ch.9]. In these models the network topology is assumed to be fixed. In contrast, the present project focuses on deciding the network topology itself.

SUBSECTION - Lagged decisions in online algorithms

A vast literature studies delayed feedback [23,24], which is however outside the scope of this project since we deal instead with delayed actions. These have been studied either in settings where each action affects the system only after some time [25], or in settings where actions require long computation times and must therefore be applied asynchronously [26].

In contrast, in our project the decision lag arises from commitment constraints: network reconfigurations must be planned in advance. Closest to our setting, previous work shows how competitive ratios degrade as the decision lag increases [27, Theorems 2, 3, 6].

However, the present project differs from these works in a crucial aspect: in those settings decisions are typically scalars or vectors, whereas here the decision is an entire network topology. Understanding how competitive ratios and regret guarantees degrade with the anticipation interval when the delayed decision is a graph remains largely open.

SUBSECTION - Decisions under uncertainty and learning-augmented optimization

Recent work studies how machine learning can be integrated with combinatorial optimization algorithms [28].

In the predict-then-optimize paradigm, unknown parameters of an optimization problem are first estimated from data and then used as inputs to the optimization model. A. Araldo (PI) recently applied this approach to public transport network reconfiguration [9]. However, minimizing prediction error does not necessarily lead to good optimization decisions. Based on this observation, decision-focused learning methods train predictive models so as to optimize the quality of the final decision rather than the prediction itself [29,30].

Another line of work studies learning-augmented online algorithms, where predictions about future inputs are incorporated into online algorithms while maintaining worst-case guarantees [31,32]. Performance improves when predictions are accurate while remaining bounded otherwise.

For example, [33] proposes a learning-augmented version of the online Steiner tree problem, where terminals arrive sequentially and the algorithm must add edges to connect them to the network, incrementally constructing a Steiner tree. Predictions about future terminals can guide which edges are purchased, while the algorithm retains competitive guarantees with respect to the optimal offline solution.

Complementary approaches arise in stochastic and robust network design, where uncertainty is modeled explicitly rather than predicted from data [34, Ch.10-11].

All aforementioned work either considers single-shot optimization problems, online problems where topology only grows, or online algorithms making simple decisions on a fixed combinatorial structure. They do not address settings where the decision variable itself is a network topology evolving over time, possibly with both additions and removals of edges, and where decisions must be committed in advance, as in the present project.

SUBSECTION - Position of the proposed work

In summary, the proposed research combines insights from network design, online optimization, delayed-decision models, learning-augmented algorithms, and planning. Its central novelty lies in formalizing and solving an online dynamic topology construction problem in which:

- the topology evolves over time
- decisions must be committed time units ahead under uncertainty and partial observability
- operational costs depend both on the network topology and on repeated topology reconfiguration

The overarching aim of the project is to investigate algorithmic foundations for the online design of dynamic networks under uncertainty, partial observability, and decision lag. To pursue this aim, the project focuses on the following research objectives.

1. 'Performance guarantees for online dynamic network design.' In simplified models of dynamic network design, we will investigate whether online algorithms can provide theoretical guarantees such as competitive ratios or regret bounds. In particular, we will examine how these guarantees depend on factors such as the decision lag , the variability of the environment, and uncertainty in network state estimation.

2. 'Use of predictive information in topology design.' We will study how predictions about future demand or substrate conditions can be incorporated into online topology design, and under which conditions prediction-augmented algorithms can improve performance.

3. 'Assessment in application domains.' We will evaluate whether the proposed approaches provide practical advantages in representative applications, including transportation and communication networks.

The detailed framework is in the PDF file downaloadable from here

The project combines tools from online algorithms, graph algorithms, and learning-augmented optimization.

- First, we will analyze simplified versions of the problem in order to identify tractable settings where theoretical guarantees may be obtained. These models will capture core aspects of the problem, such as evolving demand, topology reconfiguration costs, and decision lag. Their analysis will rely on techniques from the theory of online algorithms, e.g., competitive or regret analysis.

- Second, algorithm design will exploit structural properties of graphs to reduce the search space of candidate topologies. For instance, instead of considering the entire substrate or overlay graph, we may restrict attention to smaller subgraphs preserving certain connectivity properties [12,13].

- Third, we will investigate learning-augmented approaches that exploit predictions about future system states. Following recent frameworks for learning-augmented algorithms, predictions may guide algorithmic decisions while maintaining performance guarantees when predictions are inaccurate [31,32].

- Finally, the proposed algorithms will be implemented and evaluated on instances derived from transportation and communication networks. Preliminary work by the supervisor in the transportation domain already suggests that designing network structures online can provide substantial performance improvements: recent results show that such approaches outperform both state-of-the-art dynamic vehicle routing solutions [11] and optimized static network designs [9].