Efficient algorithms to solve scheduling problems with a variety of optimization criteria

La programmation par contraintes est une technique puissante pour résoudre, entre autres, des problèmes d’ordonnancement de grande envergure. L’ordonnancement vise à allouer dans le temps des tâches à des ressources. Lors de son exécution, une tâche consomme une ressource à un taux constant. Généralement, on cherche à optimiser une fonction objectif telle la durée totale d’un ordonnancement. Résoudre un problème d’ordonnancement signifie trouver quand chaque tâche doit débuter et quelle ressource doit l’exécuter. La plupart des problèmes d’ordonnancement sont NP-Difficiles. Conséquemment, il n’existe aucun algorithme connu capable de les résoudre en temps polynomial. Cependant, il existe des spécialisations aux problèmes d’ordonnancement qui ne sont pas NP-Complet. Ces problèmes peuvent être résolus en temps polynomial en utilisant des algorithmes qui leur sont propres. Notre objectif est d’explorer ces algorithmes d’ordonnancement dans plusieurs contextes variés. Les techniques de filtrage ont beaucoup évolué dans les dernières années en ordonnancement basé sur les contraintes. La proéminence des algorithmes de filtrage repose sur leur habilité à réduire l’arbre de recherche en excluant les valeurs des domaines qui ne participent pas à des solutions au problème. Nous proposons des améliorations et présentons des algorithmes de filtrage plus efficaces pour résoudre des problèmes classiques d’ordonnancement. De plus, nous présentons des adaptations de techniques de filtrage pour le cas où les tâches peuvent être retardées. Nous considérons aussi différentes propriétés de problèmes industriels et résolvons plus efficacement des problèmes où le critère d’optimisation n’est pas nécessairement le moment où la dernière tâche se termine. Par exemple, nous présentons des algorithmes à temps polynomial pour le cas où la quantité de ressources fluctue dans le temps, ou quand le coût d’exécuter une tâche au temps t dépend de t.

Étude exploratoire portant sur l'analyse comparative de la cohérence globale pour des textes écrits à l'aide d'un idéateur d'un traitement de textes et du crayon/papier

En 1983, un « nouveau » type de logiciels que nous avons appelé « idéateur » est apparu sur le marché de la micro-informatique. Ces logiciels combinent les facilités du traitement de textes avec l'utilisation particulière du « chaînage » de texte. Ce chaînage permet entre autre les manipulations suivantes du texte; classer, mettre en ordre prioritaire, sous-catégoriser des ensembles, lancer les items au hasard, effacer, déplacer ou copier un ou des items, etc. (Pour plus de détails, voir le chapitre 1.2 et les annexes 1 à 3). Après une étude pour situer le cadre de notre recherche (voir le chapitre II) et la traduction du logiciel MaxThink, nous avons introduit cet idéateur dans une classe de français correctif, de niveau collégial. Nous avons choisis ces sujets parce ces étudiant-e-s se servaient déjà de l'ordinateur à l'intérieur des cours et qu'ils (elles) avaient intérêt (pensions-nous) à utiliser l’idéateur pour améliorer leur français. Tous ces sujets ont eu à suivre le cours sur la manipulation de MaxThink. Un design expérimental de catégorie « semi-contrôlée » a été mis en place pour isoler l'influence des trois instruments servant à la composition ; l'idéateur (MaxThink), un traitement de texte traditionnel (Editexte) et le crayon/papier. Le pré-test et le post-test consistant à composer sur un thème déterminé était à chaque fois précédé d'un brainstorming afin de générer une liste d'idées". Par la suite, les textes ont été soumis à trois juges qui ont eu à coter la cohérence globale individuelle pré-test/post-test et la cohérence de groupe au pré-test ainsi qu'au post-test. Deux analyses statistiques non-paramétriques utiles pour un nombre restreint de sujets (trois sous-groupes de quatre sujets) ont été utilisées: analyse de variance (formule KRUSKAL-WALLIS) et analyse des probabilités d'occurrence des distributions (formule HODGES-LEHMANN). En conclusion, nos recommandations tiennent compte de l'analyse statistique des résultats et des commentaires des étudiant-e-s.

Jeux de policiers et voleurs, Modèles et applications

Les jeux de policiers et voleurs sont étudiés depuis une trentaine d’années en informatique et en mathématiques. Comme dans les jeux de poursuite en général, des poursuivants (les policiers) cherchent à capturer des évadés (les voleurs), cependant ici les joueurs agissent tour à tour et sont contraints de se déplacer sur une structure discrète. On suppose toujours que les joueurs connaissent les positions exactes de leurs opposants, autrement dit le jeu se déroule à information parfaite. La première définition d’un jeu de policiers-voleurs remonte à celle de Nowakowski et Winkler [39] et, indépendamment, Quilliot [46]. Cette première définition présente un jeu opposant un seul policier et un seul voleur avec des contraintes sur leurs vitesses de déplacement. Des extensions furent graduellement proposées telles que l’ajout de policiers et l’augmentation des vitesses de mouvement. En 2014, Bonato et MacGillivray [6] proposèrent une généralisation des jeux de policiers-voleurs pour permettre l’étude de ceux-ci dans leur globalité. Cependant, leur modèle ne couvre aucunement les jeux possédant des composantes stochastiques tels que ceux dans lesquels les voleurs peuvent bouger de manière aléatoire. Dans ce mémoire est donc présenté un nouveau modèle incluant des aspects stochastiques. En second lieu, on présente dans ce mémoire une application concrète de l’utilisation de ces jeux sous la forme d’une méthode de résolution d’un problème provenant de la théorie de la recherche. Alors que les jeux de policiers et voleurs utilisent l’hypothèse de l’information parfaite, les problèmes de recherches ne peuvent faire cette supposition. Il appert cependant que le jeu de policiers et voleurs peut être analysé comme une relaxation de contraintes d’un problème de recherche. Ce nouvel angle de vue est exploité pour la conception d’une borne supérieure sur la fonction objectif d’un problème de recherche pouvant être mise à contribution dans une méthode dite de branch and bound.

Extended formulations, nonnegative factorizations, and randomized communication protocols

An extended formulation of a polyhedron P is a linear description of a polyhedron Q together with a linear map π such that π(Q)=P. These objects are of fundamental importance in polyhedral combinatorics and optimization theory, and the subject of a number of studies. Yannakakis’ factorization theorem (Yannakakis in J Comput Syst Sci 43(3):441–466, 1991) provides a surprising connection between extended formulations and communication complexity, showing that the smallest size of an extended formulation of $$P$$P equals the nonnegative rank of its slack matrix S. Moreover, Yannakakis also shows that the nonnegative rank of S is at most 2^c, where c is the complexity of any deterministic protocol computing S. In this paper, we show that the latter result can be strengthened when we allow protocols to be randomized. In particular, we prove that the base-2 logarithm of the nonnegative rank of any nonnegative matrix equals the minimum complexity of a randomized communication protocol computing the matrix in expectation. Using Yannakakis’ factorization theorem, this implies that the base-2 logarithm of the smallest size of an extended formulation of a polytope P equals the minimum complexity of a randomized communication protocol computing the slack matrix of P in expectation. We show that allowing randomization in the protocol can be crucial for obtaining small extended formulations. Specifically, we prove that for the spanning tree and perfect matching polytopes, small variance in the protocol forces large size in the extended formulation.

Approximation limits of linear programs (beyond hierarchies)

We develop a framework for proving approximation limits of polynomial size linear programs (LPs) from lower bounds on the nonnegative ranks of suitably defined matrices. This framework yields unconditional impossibility results that are applicable to any LP as opposed to only programs generated by hierarchies. Using our framework, we prove that O(n^1/2-ε)-approximations for CLIQUE require LPs of size 2^nΩ(ε). This lower bound applies to LPs using a certain encoding of CLIQUE as a linear optimization problem. Moreover, we establish a similar result for approximations of semidefinite programs by LPs. Our main technical ingredient is a quantitative improvement of Razborov's [38] rectangle corruption lemma for the high error regime, which gives strong lower bounds on the nonnegative rank of shifts of the unique disjointness matrix.

On the extension complexity of combinatorial polytopes

In this paper we extend recent results of Fiorini et al. on the extension complexity of the cut polytope and related polyhedra. We first describe a lifting argument to show exponential extension complexity for a number of NP-complete problems including subset-sum and three dimensional matching. We then obtain a relationship between the extension complexity of the cut polytope of a graph and that of its graph minors. Using this we are able to show exponential extension complexity for the cut polytope of a large number of graphs, including those used in quantum information and suspensions of cubic planar graphs.

Classic Nintendo games are (computationally) hard

We prove NP-hardness results for five of Nintendo's largest video game franchises: Mario, Donkey Kong, Legend of Zelda, Metroid, and Pokémon. Our results apply to generalized versions of Super Mario Bros.1-3, The Lost Levels, and Super Mario World; Donkey Kong Country 1-3; all Legend of Zelda games; all Metroid games; and all Pokémon role-playing games. In addition, we prove PSPACE-completeness of the Donkey Kong Country games and several Legend of Zelda games.

Dynamically balanced and plausible trajectory planning for human-like characters

International audience

The Descent of Pluto: Interactive dynamics, specialisation and reciprocity of roles in a Wikipedia debate

International audience

Introduction to geodesics in sub-Riemannian geometry

International audience

Vocabulary and language model adaptation using information retrieval

International audience

Using Kullback-Leibler Distance for Text Categorization

International audience

Développement d'une librairie de code et d'outils bio-informatiques faciliant l'analyse de grandes quantités de données génomiques

Thèse décrivant l'écriture d'outils spécialisés facilitant l'analyse de grandes quantités de données provenant de technologie de séquencage haut débit.

Amélioration de la technique des anneaux piézoélectriques (P-RAT) à l'aide des simulations 3D

La vitesse des ondes de cisaillement est généralement mesurée en laboratoire en utilisant des éléments piézoélectriques comme les bender elements (BE). Cependant, ces techniques présentent certains problèmes au niveau de l’émission à la fois des ondes primaires et de cisaillement, les effets de champ proche, les effets de bords, et l’incertitude au niveau de l’interprétation du signal. Une nouvelle technique, baptisée technique des anneaux piézoélectriques (P-RAT) a été développée dans le laboratoire géotechnique de l'Université de Sherbrooke afin de minimiser / éliminer les difficultés associées aux autres techniques, en particulier, la pénétration des échantillons, obligatoire pour la technique BE. Cette étude présente une description de la technique P-RAT ainsi que les résultats des simulations numériques réalisées avec le code informatique COMSOL afin d'étudier l'interaction entre les composantes du P-RAT et l'échantillon testé (sol ou solide). L’étude démontre l’efficacité du concept de la méthode P-RAT et présente des modifications pour améliorer la fiabilité et la performance de la méthode P-RAT afin d’étendre son applicabilité dans le domaine du génie civil. L’implémentation de la dernière génération de P-RAT dans une cellule triaxiale et une autre œdométrique était l’aboutissement de cette étude.

Analyse prospective jusqu'en 2025 de la demande en recherche des pays du sud dans le domaine des "ressources vivantes" - Rapport final

L'accélération des changements dans tous les domaines, qu'il s'agisse d'environnement, de technologies ou de la vie des sociétés humaines, est une donnée majeure de notre temps. Jusqu'au XIXe siècle, les hommes gardaient une relative maîtrise des révolutions, qu'elles soient techniques (la vapeur, l'électricité, l'atome, ... ) ou sociales (la démocratie, le communisme, etc). A la fin du XXe siècle, la complexité des sociétés humaines, le foisonnement des découvertes scientifiques rapidement exploitées par l'industrie à des fins économiques et l'interdépendance croissante de toutes les activités dans des écosystèmes fragilisés ont conduit les communautés humaines à davantage subir les révolutions: mondialisation d'une économie de plus en plus immatérielle, explosion de l'informatique dans tous les secteurs, évolution du climat, bouleversement des modes de vie et de la vie même (actions sur les génomes animaux, voire humains) ... Aussi, cette accélération des changements rend d'autant plus indispensable une capacité d'anticiper les tendances et les enjeux qui déterminent l'avenir afin de disposer d'une liberté de réflexion et d'action indépendante de la stricte contrainte des évènements.