2021


Retour à la vue des calendrier
Jeudi 11 Février
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Linearization techniques for MINLP
Description: Sandra Ulrich Ngueveu We review state-of-the-art linearization and approximation techniques for the solution of non-linear mixed-integer programs. We show in particular how to ensure an a priori guarantee on the quality/feasibility of the solution, a reduction of the size of the converted problem and a minimization of the computing time. We then present an iterative method for the solution of a class of non-linear mixed-integer programs to arbitrary numerical precision. By keeping the scope of the update local from one iteration to another, the computational burden is only slightly increased from iteration to iteration. As a consequence, our method presents very nice scalability properties and is little sensitive to the desired precision. We assess its efficiency for approximating the non-linear variants of three problems: the uncapacitated facility location problem, the multi-commodity network design problem, and the transportation problem. Our results indicate that, as the desired precision becomes smaller, our approach can lead to significant gains in computing times, often being orders of magnitude faster than a baseline method, and scales to approximate larger problems.
Jeudi 18 Février
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Combinatorial Optimization Theory and Algorithms for Set Packing and Location Problems
Description: Mercedes Pelegrin In this talk, we will cover modeling for two optimization problems, as well as Mathematical Programming methods that can be applied to solve them. The first part will be devoted to the set packing problem, one of the seminal problems in Combinatorial Optimization. We will focus on generating hyperplanes to describe the set packing polytope. Namely, we will present a new lifting theorem and illustrate its application to facility location. In the second part of the talk, we will address the problem of identifying a group of key nodes in a network. We will propose a mixed integer nonlinear program (MINLP) that embeds eigenvector centrality in a clustering partition. The resulting model uncovers the group of key nodes (the clusters centroids) and their communities (the clusters). Modeling this idea involves nonlinear equations, which will be linearized to produce a mixed integer linear program (MILP). Symmetry breaking, a recurrent topic in Combinatorial Optimization, will be also addressed. Computational results on synthetic and real-life networks will be presented.
Jeudi 11 Mars
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Learning to solve the single machine scheduling problem with release times and sum of completion times
Description: Axel Parmentier In this work, we focus on the solution of a hard single machine scheduling problem by new heuristic algorithms embedding techniques from machine learning field and scheduling theory. These heuristics transform an instance of the hard problem into an instance of a simpler one solved to optimality. The obtained schedule is then transposed to the original problem. Computational experiments show that they are competitive with state-of-the-art heuristics, notably on large instances.
Mercredi 17 Mars
Heure: 15:00 - 16:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: A snapshot of quantum algorithms for optimization
Description: Giacomo Nannicini There is much hype surrounding quantum computing and its potential applications for optimization. However, the technical details are often lost in translation. In this talk I will give an overview of quantum algorithms that may - one day - be useful for continuous and discrete optimization, highlighting possible sources of advantage as well as limitations. In particular, I will discuss
variational hybrid algorithms for optimization, simulated annealing for counting problems, algorithms for linear systems, and algorithms for SDPs and LPs. I assume no prior knowledge of quantum mechanics.
Jeudi 15 Avril
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Formulations PLNE pour un problème d'ordonnancement juste-à-temps
Description: Anne-Elisabeth FALQ Une contrainte essentielle pour un problème d'ordonnancement sur une machine est le non-chevauchement des tâches: deux tâches ne peuvent être exécutées en même temps.
Les premières inégalités de non-chevauchement ont été proposées par Queyranne (1993) pour le problème de minimisation de la somme pondérée des dates de fins. La famille d'inégalités linéaires proposée décrit exactement l'enveloppe convexe des vecteurs encodant des ordonnancements réalisables par les dates de fins des tâches. Ces inégalités ne coupent pas tous les vecteurs encodant un ordonnancement avec chevauchement mais assurent le non-chevauchement au sens où tous les points extrêmes du polyèdre qu'elles définissent encodent des ordonnancements réalisables, et plus précisément ceux calés à gauche qui forment un ensemble dominant pour ce problème.

Dans cet exposé, nous nous intéresseront particulièrement au problème d'ordonnancement juste-à-temps où toutes les tâches partagent une même date d'échéance commune et où il s'agit de minimiser la somme pondérée des avances et des retards par rapport à cette date.
En s'appuyant sur les propriétés de dominance connues pour ce problème NP-difficile (Hall et Posner, 1991), nous proposerons une formulation basée sur des inégalités de non-chevauchement nouvelles. Cette formulation, qui n'est pas exactement un programme linéaire en nombre entiers (PLNE) puisqu'elle fait apparaître des contraintes d'extremalité, peut être résolue par un solveur de PL implémentant un algorithme de "Branch-and-Cut". Nous expliquerons comment et présenterons quelques résultats expérimentaux.
Dans un second temps, nous proposerons une formulation compacte pour ce problème, que nous renforçons par des inégalités dites de dominance. Ces inégalités sont ainsi nommées car elles traduisent la dominance des solutions localement optimales, où local s'entend pour un voisinage généré par une famille d'opérations sur les solutions. Pour chaque opération considérée, une inégalité élimine les solutions qu'on pourrait améliorer en appliquant la transformation. De ce fait, ces inégalités coupent des point entiers, et diffèrent en cela des inégalités classiques de renforcement. Grâce à des résultats expérimentaux, nous montrerons le gain d’efficacité qu'apporte ces inégalités de dominance.
Jeudi 22 Avril
Heure: 10:30 - 11:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Extraction et partitionnement pour la recherche de régularités : application à l'analyse de dialogues.
Description: Zacharie ALES Dans le cadre de l'aide à l'analyse de dialogues, un corpus de dialogues peut être représenté par un ensemble de tableaux d'annotations encodant les différents énoncés des dialogues. Afin d'identifier des schémas dialogiques mis en œuvre fréquemment, nous définissons une méthodologie en deux étapes : extraction de motifs récurrents, puis partitionnement de ces motifs en classes homogènes constituant des régularités.

Deux méthodes sont développées afin de réaliser l'extraction de motifs récurrents : LPCA-DC et SABRE. La première est une adaptation d'un algorithme de programmation dynamique tandis que la seconde est issue d'une modélisation formelle du problème d'extraction d'alignements locaux dans un couple de tableaux d'annotations.

Le partitionnement de motifs récurrents est réalisé par deux formulations originales du problème de K-partitionnement sous la forme de programmes linéaires en nombres entiers. Lors d'une étude polyèdrale, nous caractérisons des facettes d'un polyèdre associé à ces formulations (notamment les inégalités de 2-partitions, les inégalités 2-chorded cycles et les inégalités de clique généralisées). Ces résultats théoriques permettent la mise en place d'un algorithme de plans coupants résolvant efficacement le problème.

Nous développons le logiciel d'aide à la décision VIESA, mettant en œuvre ces différentes méthodes et permettant leur évaluation au cours de deux expérimentations réalisées par un expert psychologue. Des régularités correspondant à des stratégies dialogiques que des extractions manuelles n'avaient pas permis d'obtenir sont ainsi identifiées.