2021

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.

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.

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.

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.

Heure:	10:30 - 11:30
Lieu:	Salle B107, bâtiment B, Université de Villetaneuse
Résumé:	Decomposition methods and column/matrix generation approaches for quadratic programming
Description:	Lucas Létocart The purpose of this talk is to present three decomposition approaches for quadratic problems. First, we analyze a simplicial decomposition like algorithmic framework that handles convex quadratic programs in an effective way. We also propose a branch & bound approach based on this simplicial decomposition for the binary case and we introduce warmstart techniques using columns' projection. Then, we propose a methodological analysis on a family of reformulations combining Dantzig-Wolfe decomposition and Quadratic Convex Reformulation principles for binary quadratic problems. Finally, we propose a matrix generation method for quadratically constrained 0-1 quadratic problems based on a Dantzig-Wolfe reformulation. The domain of this relaxation corresponds to the Boolean Quadric Polytope.