Skip to content Menu Close

LIRMM Lab
Research
Partnership
Student life
Our commitment
- Green LIRMM
  - Mobility
  - Energy
  - Digital
  - Waste
  - Events
  - Research
  - Various
- Open Science
- Gender equality
News
Directory
Contact & Venue
Employment

Search for:

Search for:

Search for:

LIRMM Lab
Research
Partnership
Student life
Our commitment
- Green LIRMM
  - Mobility
  - Energy
  - Digital
  - Waste
  - Events
  - Research
  - Various
- Open Science
- Gender equality
News
Directory
Contact & Venue
Employment

Teams

Computer Science department

curlGET failed: SSL certificate problem: certificate has expired

Former teams:

ZENITH: Gestion de données scientifiques

Microelectronics department

curlGET failed: SSL certificate problem: certificate has expired

Robotics department

curlGET failed: SSL certificate problem: certificate has expired

Former teams:

EXPLORE: Underwater exploration

WebIris, Prenez soin de vos yeux !

What is happening at LIRMM

See all LIRMM seminars

Les prochains séminaires

Show/hide all

October 2025

Tuesday 21 October

11 h 45 min: Jannis Kurtz, «Towards Explainable (Integer) Optimization»
In recent years, there has been a rising demand for transparent and explainable AI models. Although significant progress has been made in providing explanations for machine learning (ML) models, this topic has not received the same attention in the Operations Research (OR) community. However, algorithmic decisions in OR are made by complex algorithms which cannot be considered to be explainable or transparent as we will argue in this talk. To tackle this issue we present two promising concepts to provide explanations for (integer) optimization problems. In the first part we introduce the concept of counterfactual explanations and show how it can be used to calculate explanations for linear integer optimization problems. We show that the resulting problem is Sigma_2^p-hard but can be solved in reasonable time for certain special cases. In the second part we present a model-agnostic method called CLEMO which can provide explanations for any type of optimization algorithms (exact or heuristic). The idea is to approximate the input-output relationship of an optimization algorithm by an interpretable ML model.
https://info-web.lirmm.fr/collorg/ec377c6b-4a58-4fb8-9c8d-c93d5843418c

Thursday 23 October

10 h 00 min – 10 h 45 min: Eric Brandwein, «Kernelization dichotomies for hitting minors under structural parameterizations»
For a finite collection of connected graphs F, the F-Minor Deletion problem consists in, given a graph G and an integer l, deciding whether G contains a vertex set of size at most l whose removal results in an F-minor-free graph. We lift the existence of approximate polynomial kernels for F-Minor Deletion by the solution size to approximate polynomial kernels parameterized by the vertex-deletion distance to graphs of bounded elimination distance to F-minor-free graphs. This results in exact polynomial kernels for every family F that contains a planar graph, and an approximate polynomial kernel for Planar Vertex Deletion. Moreover, combining our result with a previous lower bound, we obtain the following infinite set of dichotomies, assuming NP is not contained in coNP/poly: for any finite set F of biconnected graphs on at least three vertices containing a planar graph, and any minor-closed class of graphs C, F-Minor Deletion admits a polynomial kernel parameterized by the vertex-deletion distance to C if and only if C has bounded elimination distance to F-minor-free graphs. For instance, this yields dichotomies for Cactus Vertex Deletion, Outerplanar Vertex Deletion, and Treewidth-t Vertex Deletion for every integer t ≥ 0. Prior to our work, such dichotomies were only known for the particular cases of Vertex Cover and Feedback Vertex Set. Our approach builds on the techniques developed by Jansen and Pieterse [Theor. Comput. Sci. 2020] and also uses adaptations of some of the results by Jansen, de Kroon, and Wlodarczyk [STOC 2021].

Joint work with Marin Bougeret and Ignasi Sau.
https://info-web.lirmm.fr/collorg/6f7cd66b-68ac-4f33-89d6-473622557eb8

November 2025

Thursday 13 November

14 h 00 min: Imran Meghazi, «Quantum model for CVRPTW»
The capacitated vehicle routing problem with time windows (CVRPTW) is often faced by Postal services in the context of package delivery or other time-sensitive operations. We provide an implementation on gate based quantum computer of a model inspired by classical route first, cluster second technique. The quantum paradigm allows to overcome suboptimality inherent property of this decomposition. In the current NISQ (Noisy Intermediate-Scale Quantum) era, the most important limitation is the number of available qubits which makes time windows and capacity constraints hard to tackle. We introduce a qubit-efficient split-inspired modeling which adds only a linear number of decision qubits to standard quantum formulations for Traveling Salesman Problem (TSP). This paper proposes a quantum algorithm for the capacitated vehicle routing problem with time windows (CVRPTW) based on Grover Search framework. This problem is often faced by Postal services in the context of package delivery or other time-sensitive operations. We provide an implementation on gate based quantum computer of a model inspired by classical route first, cluster second technique. The quantum paradigm allows to overcome suboptimality inherent property of this decomposition. In the current NISQ (Noisy Intermediate-Scale Quantum) era, the most important limitation is the number of available qubits which makes time windows and capacity constraints hard to tackle. We introduce a qubit-efficient split-inspired modeling which adds only a linear number of decision qubits to standard quantum formulations for Traveling Salesman Problem (TSP).
https://info-web.lirmm.fr/collorg/1620253a-4571-43b7-8745-585e46ec7f62

Accès rédacteur
Intranet
Réservation de salle

Informations légales
Webmail
Copyright © 2025 LIRMM

« Accessibilité : non conforme »