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
Friday, December 11 — Network Survivability and Interdictions
Abstract
Talk abstract
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.
Abstract
Talk abstract
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.
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.
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.
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).
Organizers: Amal BENHAMICHE and Diego DELLE DONNE
Registered participants: