31e séminaire POC

SPOC 31 "Network Survivability and Interdictions"

Network Survivability and Interdictions

December 10-11, 2026

At Orange Gardens (Châtillon), room "Le Forum"

The registration is free, but mandatory: Register here

See the list of the participants here

Thursday, December 10 — PhD students' presentations

13:30 - 14:00
Welcome Coffee
14:00 - 17:00
PhD students' presentations

Friday, December 11 — Network Survivability and Interdictions

09:00 - 09:30
Welcome
09:30 - 10:15
Annegret Wagler (Université Clermont Auvergne)
Talk title
Abstract

Talk abstract

10:15 - 11:00
Sébastien Martin (Huawei)
Interdiction and blocker notions applied to telecommunication problems
Abstract

Interdiction and blocker notions are two concepts that can be applied to an optimization problem. In this way, the problem becomes a bi-level problem where the inner problem is the optimization problem itself, and the outer problem is the interdiction or blocker adversarial level. This talk will present the interdiction and blocker notions and show the differences and similarities between the two. The impact on complexity of applying these notions to an optimization problem will be explained. These two notions will be illustrated through flow problems (maximum flow, shortest path, multi-commodity flow), with telecommunication use cases shown for each. Some approaches to tackle this kind of problem, based on dual properties or covering approaches, will be explained. The equivalence between the blocker and interdiction notions will be shown for the maximum flow problem, whereas for the shortest path problem this equivalence does not hold. At the end of this talk, some interesting open problems related to flow problems will be presented for future work.

11:00 - 11:15
Coffee break
11:15 - 12:00
Martine Labbé (Université Libre de Bruxelles)
Talk title
Abstract

Talk abstract

12:00 - 14:00
Lunch
14:00 - 14:45
Arie Koster (Aachen University)
Bilevel Network Optimization with One or Multiple Followers
Abstract

In bilevel optimization a leader and follower(s) have to solve entangled optimization problems. The decisions taken by the leader impact the decisions taken by the follower(s), and vice versa. In this talk, we discuss solution approaches for bilevel optimization by means of two network optimization problems. First, the k-truss minimization problem is introduced, where the leader can eliminate a limited number of edges from a graph in order to minimize the size of the resulting k-truss which the follower tries to maximize (a k-truss is a generalization of the clique concept). We show that this problem can be reformulated to a single level problem by strong duality.
In the second problem, we consider network routing by multiple independent followers in a network where the leader can decide to close certain network arcs. The objective of the follower, however, is determined by the routing decisions of the followers. We show that for this type of problems a hierarchical decomposition approach with Lagrangian Benders-like cuts to circumvent the integrality of the lower level problems can be successfully applied.

14:45 - 15:30
André Rossi (Université Paris-Dauphine)
The Survivable One-Fault-Tolerant Ring-Star Problem and Its Resilient Extension
Abstract

This talk introduces the Ring-Star Problem and addresses two variants of this network design problem where at most one hub can fail at a time. In both cases, the primary objective is to minimize the cost of ensuring a robust Ring-Star structure despite the risk of a single-hub failure. The survivable variant assumes a proactive approach where no recourse actions can be taken upon a hub failure. Conversely, the resilient variant allows for reactive measures, meaning additional edges and arcs can be leased to cope with the disruption, provided that the cumulative downtime of the hub does not exceed a specified threshold. Both problems are modeled as integer linear programs (ILPs) which serve as the foundation for a Benders decomposition approach. For the survivable variant, the Benders subproblem is an ILP that achieves integrality through the introduction of facet-defining valid inequalities. Finally, we compare the two proposed strategies in terms of cost relative to the total failure duration.

15:30 - 16:00
Coffee break
16:00 - 16:30
Youssouf Hadhbi (Orange)
Harnessing Combinatorial Optimization for the Design of Sustainable, Secure and Resilient AI Infrastructures: From Resource Orchestration to Attacker-Defender Games
Abstract

The rapid development and deployment of artificial intelligence (AI) are driving the emergence of increasingly complex infrastructures that rely on heterogeneous computing resources, distributed architectures, large-scale data centers and interconnected services. Managing these infrastructures raises major combinatorial optimization challenges involving resource allocation, workload scheduling, service placement, task orchestration and dynamic migration. Beyond performance and operational efficiency, sustainability, cybersecurity and resilience have become critical dimensions in the design and operation of next-generation AI infrastructures. In this work, we explore emerging trends and research directions in combinatorial optimization for sustainable, secure and resilient AI infrastructures. It examines how optimization techniques can support efficient resource management while balancing competing objectives, including computational performance, energy consumption, operational costs, service availability and security requirements.
The work also addresses the growing importance of security-aware optimization and the strategic interaction between attackers and defenders. Bilevel optimization provides a mathematical framework for modeling these interactions, where defenders allocate resources and design protection strategies in response to potential attacks. In particular, attacker-defender models and network interdiction help identify critical infrastructure components, optimize defensive resource allocation and minimize the impact of malicious actions. These approaches enable the integration of cybersecurity considerations into infrastructure-level optimization decisions.
Finally, we explore integer programming, polyhedra, and hybrid approaches that combine exact algorithms with AI-based methods, illustrating their application through a specific case study. The objective is to demonstrate how combinatorial optimization can contribute to the development of AI infrastructures that are not only efficient and scalable, but also sustainable, secure, adaptive and resilient.

16:30 - 17:00
Alexis Schneider (Eindhoven University of Technology)
A Branch-and-Cut for Virtual Network Embedding
Abstract

The Virtual Network Embedding (VNE) problem is the combinatorial core of network slicing in 5G and 6G networks. Traditionally, this problem is modeled either with a compact flow formulation, which can be solved by MILP solvers, or with a path formulation, which has exponentially many variables and therefore requires a Branch-and-Price. We introduce new cut-set inequalities for the flow formulation, and we prove that they strengthen its linear relaxation to exactly the value of the path formulation. We then show that these inequalities can be separated in polynomial time, and we propose an efficient Branch-and-Cut. This work thus achieves the bound of the path formulation with a much simpler implementation (Branch-and-Cut rather than Branch-and-Price), while benefiting from the additional tools of standard MILP solvers (preprocessing, branching, cuts).

17:00 - 17:10
Closing

Organizers: Amal BENHAMICHE and Diego DELLE DONNE


Registered participants: