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
open p sites while minimizing the sum of the distances of each client to its nearest open site. We
study a Benders decomposition of the most efficient formulation in the literature. We show that
the Benders cuts can be separated in linear time. The Benders reformulation leads to a compact
formulation for the p-median problem. We implement a two-phase Benders decomposition algorithm
that outperforms state-of-the-art methods and allows to exactly solve for the first time several instances, among which are large BIRCH and TSP instances with up to 238025 clients and sites.

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
questions regarding box-totally dual integral (box-TDI) polyhedra. First,
although box-TDI polyhedra have strong integrality properties, we prove
that Integer Programming over box-TDI polyhedra is NP-complete, that
is, finding an integer point optimizing a linear function over a box-TDI
polyhedron is hard. Second, we complement the result of Ding et al.
(Math. Prog. 114(2), 321–334 (2008)) who proved that deciding whether
a given system is box-TDI is co-NP-complete: we prove that recognizing
whether a polyhedron is box-TDI is co-NP-complete.
To derive these complexity results, we exhibit new classes of totally
equimodular matrices — a generalization of totally unimodular matrices
— by characterizing the total equimodularity of incidence matrices of
graphs.

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)


 

Autres participants à la journée

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)