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
14:00
| 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 non-compact 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 (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 (LAMSADE) |
Ali Ridha Mahjoub |
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 (ESSEC) |
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 (LIMOS) |
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). |
|
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 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: