La "journée" est une aprèsmidi 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
PhD  Supervizors 
Title and Abstract 
Yerlan Kuzbakov
(ESSEC)

Laurent Alfandari 
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 noncompact formulations for connectivity, allocation, and coverage constraints.

Yuanyuan Li (ESSEC) 
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 (TSPRD) 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 sameday delivery services. We propose two reinforcement learning approaches for TSPRD. 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 decisionmaking 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; onestep lookahead policy with value function approximation (VFA) where we build a 2stage 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 (LAMSADE) 
Ali Ridha Mahjoub 
A BranchandCut algorithm to solve the multicommodity 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 Multicommodity flow blocker problem.
Considering a network, a multicommodity flow problem consists in finding a set of arcs routing flow to satisfy all demands, respecting flow conservation constraints and capacity constraints. The multicommodity flow blocker problem is a bilevel optimization problem where a blocker problem, also called master, applies to a multicommodity 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 multicommodity flow problem is not feasible. We introduce a new IP model for the multicommodity flow blocker problem. Our goal is to provide a thin and wellunderstood formulation. This formulation has an exponential number of constraints called cover constraints. Hence, we develop a Branchandcut algorithm to solve this problem and investigate new inequalities to strengthen the model. 
Javaiz Parappathodi (ESSEC) 
Claudia Archetti Ivana Ljubic 
Tailored Bender's Decomposition for Crowdsourced Humanitarian Relief Vehicle Routing Problem The situation is rescue operations in a postdisaster 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 (LIMOS) 
Ali Ridha Mahjoub Ibrahima Diarrassouba 
The ConstrainedRouting and Spectrum Assignment Problem: Polyhedral Analysis and Algorithms In this work we focus on the ConstrainedRouting and Spectrum Assignment (CRSA) problem related to the dimensioning and designing of Spectrally Flexible Optical Networks (SFONs). 
Alexandre Heintzmann (EDF) 
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. 
Charles Nourry (LAMSADE) 
A. Ridha Mahjoub, 
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 sousproblè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: