Journée "Hors les Murs" 24/11/22
Journée "Hors les Murs" du jeudi 24 novembre 2022
Cette journée est animée par des exposés de doctorants et de jeunes docteurs.
Pour participer à cette journée https://www.lamsade.dauphine.fr/poc/?q=node/95, envoyez votre nom, celui de vos encadrants et quelques lignes de résumé à pierre.fouilhoux@lipn.fr
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 A707
- et simultanément (on l'espère) par ce lien: https://cnrs.zoom.us/j/91085968241?pwd=QklmdFNveHdzVG1FSnB0OW1SM1phdz09
( ID de réunion : 910 8596 8241 / Code secret : SPOC2411 )
Exposés de l'après-midi
14:00
| Orateur | Encadrants | Titre et Résumé |
| Yue Zhang | Pierre Fouilhoux Lucas Létocart |
Enhancing the Bi-objective Branch & Cut algorithm by multi-point separation cutting plane
We propose a Branch&Bound framework (BBBB) to enumerate every non-dominated solution of a Bi-objective Binary linear program. The efficiency of a BBBB is mainly based on the availability to prune the nodes using a comparison between the lower bound and upper bound sets. For purpose of strengthening the lower bound sets, we add valid inequalities using classical separation methods initially from mono-objective optimization background. In this bi-objective context, such a cutting plane approach could be enhanced by multi-point separation algorithms. Beyond that, we adapt our BBBB tree to a dynamic exploration both in objective and variable space parallelly. Using the VoptSolver framework in Julia, preliminary experimental results will be presented to show the efficiency of our algorithm. |
| Alexandre Dupont-Bouillard | Pierre Fouilhoux Roland Grappe Mathieu Lacroix |
Graphe totalement parfait et polyèdre des co-2-plexes |
| Cristian Duran | Sourour Elloumi et Zacharie Ales |
An efficient Benders decomposition for the p-median problem. The p-median problem is a classic discrete location problem with numerous applications. It aims to |
| Minh Hieu Nguyen | Mourad Baiou et Viet Hung Nguyen |
Solutions généralisées de Nash pour les problèmes d'optimisation bi-objectif Dans cet exposé, nous considérons un cas particulier de l'optimisation bi-objectif (BOO), appelé minimisation bi-objectif (BOM), où deux fonctions objectifs à minimiser ne prennent que des valeurs positives. Comme pour BOO, il peut être difficile de déterminer les solutions préférées en raison du grand nombre de solutions dans l'ensemble de Pareto pour BOM. Nous proposons un nouveau critère de sélection des solutions optimales de Pareto préférées en introduisant le concept de solutions rho-Nash Fairness (rho-NF) inspiré de la définition de l'équité proportionnelle. Le paramètre positif rho est introduit pour refléter l'importance relative du premier objectif par rapport au second et les solutions rho-NF sont les solutions optimales de Pareto réalisant un équilibre de Nash proportionnel entre les deux objectifs. Nous nous concentrons sur les solutions rho-NF extrêmes atteignant les plus petites valeurs pour l'un des objectifs. Ensuite, nous proposons deux algorithmes itératifs basés la méthode de la somme pondérée pour trouver des solutions NF extrêmes. En particulier, cet algorithme peut être modifié pour trouver toutes les solutions rho-NF. |
| Thi Quynh TrangVO | Mourad Baiou et Viet Hung Nguyen |
Improving subtour constraints generation in Branch-and-Cut algorithms for TSP with Machine Learning Branch-and-Cut (B&C) is a widely-used algorithm for solving integer programming (IP) problems. In recent years, applying Machine Learning (ML) to improve fundamental decision problems of B&C algorithms is an active research domain. While much of ML research focuses on variable selection, node selection, and cut selection, less attention has been paid to the question of how to design a cutting plane generation strategy in B&C algorithms. This question is crucial since generating cutting planes might become a computational burden when the instance’s size increases. In this work, we focus on improving the subtour elimination constraints (SEC) generation in B&C algorithms for Traveling Salesman Problem (TSP) by ML. SEC is a well-known constraint used to exactly solve TSP. In the IP formulations for TSP, SEC is dynamically generated as cutting planes in the course of B&C algorithms due to its exponential cardinality. Our purpose is to take advantage of ML to address two questions before launching the separation process to find violated SEC cuts on a node of the B&C search tree : 1) Does there exist violated SEC cuts ? 2) If yes, is it worth generating them ? To do this, we propose a ML-based method consisting of two parts : a cut detector to predict the cut existence and a cut decider to decide whether generate cuts. Our method not only can leverage the geometric structure of optimal solutions but it also offers the flexibility of the instance’s size. |
| Francesco Pisanu | Roland Grappe Mathieu Lacroix Roberto Wolfer-Calvo |
Hard problems in box-Totally Dual Integral polyhedra
In this work, we study the complexity of some fundamental |
| Isma Bentoumi | Sébastien Martin A. Ridha Mahjoub Fabio Furini |
The Maximum Flow Blocker Problem (MFBP) is a bi-level optimization problem where a blocker problem is applied to a Maximum Flow Problem. It consists in determining a subset of arcs, called interdicted arcs to be removed from the graph, with minimum cost, such that the remaining maximum flow is not larger than a given input parameter.
We present two integer linear programming formulations for the MFBP which are used to derive the first exact algorithms to optimally solve the problem. The first formulation comes from the bilevel aspect of the MFBP. It has an exponential number of constraints and it is solved via a Branch-and-Cut algorithm. The second one has a polynomial number of variables and constraints and it is solved via a state-of-the-art ILP solver. This second formulation is obtained thanks to a relationship between the MFBP and the maximum flow interdiction problem. The two methods proposed are compared thanks to a computational campaign. |
| Sébastien Kerleau, | Denis Cornaz Clément Royer | On appelle PSS (positive spanning set) une famille de vecteurs convenablement répartis dans l'espace. Ces familles de vecteurs sont particulièrement utilisées en optimisation sans dérivées : en effet, si une fonction f est suffisamment lisse, l'une des directions induites par les éléments d'un PSS est une direction de descente pour f. Dans cet exposé, nous étudierons la structure de certains PSS aux propriétés particulières, appelés PkSS. Nous verrons comment de telles familles peuvent être générées à partir de polytopes convenablement choisis. |
18:00 - Fin de la journée POC:
20:00 - Repas en commun (le restaurant sera choisi ensemble sur place)
Pierre Fouilhoux
Charles Noury
A. Ridha Mahjoub (en visio)
Fatiha Bendali-Mailfert (en visio)
Denis Cornaz
Emiliano Lancini
Zacharie Ales
Mathieu Vallée
Jean Mailfert (en visio)
Youssouf Hadhbi (en visio)