Journée "Hors les Murs" 09/12/21

Journée "Hors les Murs" du jeudi 9 décembre 2021

Lieux et autres infos

La "journée" est une après-midi qui commence à 14h.

Les exposés seront en hybrides

- depuis le laboratoire LAMSADE de l'université Paris Dauphine
   en salle P505
- et simultanément (on l'espère) par ce lien zoom


Exposés de l'après-midi

PhD Supervizors

Title and Abstract

Yerlan Kuzbakov

Laurent Alfandari
Claudia Archetti
Ivana Ljubic

Location problems with interconnected facilities
Location problem with interconnected facilities is a cost minimization problem deciding on which facility nodes to open and how to allocate customers to open facilities, under an additional constraint that all open facilities should be interconnected, i.e., neighboring open facilities should be within some radius r≥0 from each other. Interconnectivity between the facilities is an important feature for modeling communication between sensors, or in the context of designing the radio networks. In this work, we consider two problem variants:•the Median Problem with Interconnected Facilities (MPIF), and•the Covering location Problem with Interconnected Facilities (CPIF). For the former problem, we are bound to cover all customers by open facilities, and we search for a subset of facilities to open so that the opening plus allocation cost is minimized. For the latter problem, we incur a penalty for not covering a customer, and the goal is to find a subset of facilities to open so that the sum of facility opening cost together with the penalties for customers that remain uncovered is minimized. We introduce new ways to model the MPIF and the CPIF problems by combining non-compact formulations for connectivity, allocation, and coverage constraints.

Yuanyuan Li 


Claudia Archetti
Ivana Ljubic
Reinforcement Learning Approaches for the TSP with Stochastic and Dynamic Release Dates
Traveling salesman problem with the stochastic and dynamic release date (TSP-RD) is a problem in which a supplier receives goods from his suppliers then distributes them to customers. The customers are associated with a release date indicating the time when his or her parcel is available at the distribution center and the release dates are considered to be stochastic and dynamically updated along with the distribution. The problem finds application in same-day delivery services. We propose two reinforcement learning approaches for TSP-RD. We model the problem as a Markov decision process. We assume that, at each decision epoch, we are given the sets of known customers and unknown customers respectively. We generate a number of scenarios representing realizations of release dates. Then for each scenario, we approximate the value of future states using a batch approach. Eventually, two approximation approaches are proposed to derive a decision-making policy: policy function approximation through a consensus function (PFA) in which a deterministic model is used for determining the set of requests to serve within a route starting immediately and the set of requests included in future routes, and a consensus function based on the solutions obtained over all scenarios determines the final solution; one-step look-ahead policy with value function approximation (VFA) where we build a 2-stage stochastic model in which the first stage is to calculate a route containing requests to deliver in the current decision epoch, while the second stage relates to the rewards obtained in the states from the next decision epoch by integrating all scenarios with equal probability. Finally, through running the simulations with a myopic approach as the benchmark, we prove the satisfying performance of the two proposed approaches, especially with the VFA.

Isma Bentoumi


Ali Ridha Mahjoub
Sébastien Martin
Fabio Furini

A Branch-and-Cut algorithm to solve the multi-commodity flow blocker problem

We are interested in evaluating the strength of a network, by determining the maximum number of failures that it can face. This can be done by solving a Multi-commodity flow blocker problem.
Considering a network, a multi-commodity flow problem consists in finding a set of arcs routing flow to satisfy all demands, respecting flow conservation constraints and capacity constraints. The multi-commodity flow blocker problem is a bilevel optimization problem where a blocker problem, also called master, applies to a multi-commodity flow problem, also called follower. It consists in finding the minimum number of arcs that have to be destructed from the network such that the multi-commodity flow problem is not feasible.
We introduce a new IP model for the multi-commodity flow blocker problem. Our goal is to provide a thin and well-understood formulation. This formulation has an exponential number of constraints called cover constraints. Hence, we develop a Branch-and-cut algorithm to solve this problem and investigate new inequalities to strengthen the model.

Javaiz Parappathodi


Claudia Archetti
Ivana Ljubic

Tailored Bender's Decomposition for Crowdsourced Humanitarian Relief Vehicle Routing Problem

The situation is rescue operations in a post-disaster scenario. The location of victims to be rescued are assumed to be known apriori and deterministic. There are supply points across geography which are ready with relief materials. There are volunteers across the geography who are willing to go to the supply points, pick up relief materials and get them to the victims at their respective locations. The objective is to design routes for the volunteers that aims at minimizing the time required to reach out to the last person in need. The solution methodology uses a Benders Decomposition approach that utilizes some interesting properties of the problem to reduce computational requirements.

Youssouf Hadhbi


Ali Ridha Mahjoub
Ibrahima Diarrassouba

The Constrained-Routing and Spectrum Assignment Problem: Polyhedral Analysis and Algorithms

In this work we focus on the Constrained-Routing and Spectrum Assignment (C-RSA) problem related to the dimensioning and designing of Spectrally Flexible Optical Networks (SFONs).
The C-RSA can be stated as follows. Consider an undirected, loopless, and connected graph G, an optical spectrum S of available contiguous frequency slots, and a multiset of traffic demands K
between pairs of origins and destinations. The C-RSA consists of assigning for each traffic demand k ∈ K a path in G between its origin and destination, and an interval of contiguous frequency slots in S so that some technological constraints are satisfied, and some linear objective function is optimized. It’s well known to be NP-hard problem. To the best of our knowledge, a polyhedral approach to the C-RSA has not been considered before. The main aim of our work is to provide a deep polyhedral investigation and design a cutting plane method for the problem. First, we propose an integer linear programming formulation namely cut formulation. We carry out an investigation of the related polytope defined by the convex hull of all its solutions. Moreover, we identify several classes of valid inequalities for the polytope and study their facial structure. We further discuss their separation problems. Using these results, we devise a Branch-and-Cut (B&C) algorithm for the problem, and discuss computational results using this algorithm. A second part of this work is devoted to an extended formulation namely path formulation. A column generation algorithm is developed to solve its linear relaxation. Using this, we devise Branch-and-Price (B&P) and Branch-and-Cut-and-Price (B&C&P) algorithms to solve the problem, along with some computational results are presented. We also provide an extensive comparative analysis of performance between the B&C, B&P and B&C&Palgorithms using two types of instances: random and realistic ones.

Alexandre Heintzmann


Cécile Rottner
Pascale Bendotti

Etude polyédrale du Sac-à-dos Matriciel Symétrique en Poids

Le Sac-à-dos Matriciel Symétrique en Poids (SADMSP) est une variante très particulière du problème de sac-à-dos. Soit un sac-à-dos avec N*M objets. Les objets sont répartis en N groupes de M objets, avec des contraintes de précédence particulières, ce qui donne un effet matriciel lorsqu'on représente graphiquement les objets. Les poids sont dit symétriques car l'objet I a le même poids, peu importe le groupe J dans lequel cet objet se situe. Contrairement aux poids, les valeurs des objets ne sont pas symétriques.
Résoudre le SADMSP consiste à maximiser la valeur des objets sélectionnés, en respectant une contrainte de sac-à-dos globale, et les contraintes de précédence. L'objectif des travaux en cours est de décrire les facettes de ce problème, passant par une structure qui permet de ne pas avoir à gérer toutes les symétries. A terme, l'objectif est de concevoir un algorithme intelligent, permettant d’intégrer ces facettes efficacement au sein d'un Branch and Cut. Cet algorithme pourra par la suite être étendu à d'autres problèmes, ou à des problèmes métiers connus.

Charles Nourry


A. Ridha Mahjoub,
Hassene Aissi.

Etude de formulations étendues pour le problème de l'arbre couvrant budgeté

 Le problème de l'arbre couvrant budgeté consiste à trouver un arbre couvrant de poids minimum respectant plusieurs contraintes de sac à dos. Ce problème possède de nombreuses applications, notamment dans le domaine de la télécommunication, et on peut également le retrouver comme sous-problème de certaines décompositions. L'objectif principal de notre travail est de comprendre l'impact de ces contraintes de budget sur les polyèdres connus du problème de l'arbre couvrant afin de concevoir des algorithmes efficaces. En plus de l'étude polyédrale de ce problème, nous étudions différentes formulations étendues dans le but de générer des inégalités valides via leurs projections.

18:00 - Fin de la journée POC:

20:00 - Repas en commun  (le restaurant sera choisi ensemble sur place)


Participants à la journée