Actualités du LIPN - Tag - OCAD

Résolution de problèmes de transport à la personne par génération de colonnes

jcdubacq — Tuesday 20 April 2010

Le séminaire OCAD recevra le 20 avril Thierry Garaix (chercheur, Politecnico di Torino).

Cette présentation met en avant trois problèmes de tournées de véhicules originaux issus de la considération de réseau routiers réels et de critères de qualité de service pour le transport de personnes. Les méthodes proposées sont basées sur des approches de génération de colonnes.

Au cours des dernières décennies, en partant du problème de Voyageur de Commerce, les problèmes de tournées de véhicules académiques ont été enrichis par des contraintes ou des extensions de natures différentes : flotte de véhicules, capacités, fenêtres de temps et ramassage et livraison pour les plus étudiées. Nous disposons ainsi aujourd’hui de méthodes heuristiques ou exactes efficaces sur ces problèmes. Deux enjeux majeurs actuels en terme d’optimisation, sont le passage à des problèmes de grande taille et/ou la prise en compte de nouvelles contraintes (possiblement multicritères). Le transport de personnes et en particulier les transports à la demande s’apparentent directement à ces enjeux en intégrant notamment des contraintes fortes liées à la qualité de service.

Un réseau de transport propose généralement des chemins alternatifs privilégiant tel ou tel critère (coût, temps, sécurité;...). Considérer ces alternatives, génère une forte augmentation de la taille des données définissant l’espace des solutions. Il est donc nécessaire de valider des approches pertinentes sur des réseaux ainsi définis. Un critère usuel d’évaluation de la performance générale d’un système de transport, est le taux moyen de remplissage des véhicules. Cependant, ce critère fractionnaire est rarement (jamais) utilisé comme objectif dans les outils de calcul des tournées. Dans le un cas de transport à la demande, il se révèle peu coûteux en temps de calcul d’y adapter une méthode de génération de colonnes standard.

Dans le cadre de transport de personnes handicapées, la régularité des horaires de ramassage d’un jour sur l’autre, est un critère de qualité de service primordial. C’est aussi une valeur ajoutée à des tournées de livraison pour des clients réguliers. La modélisation de cette contrainte donne un problème original pour lequel est proposé une heuristique basée sur la résolution exacte d’un problème de tournées à fenêtres de temps dures (sans temps d’attentes) et multiples.

Combinatoire des mots et convexité discrète

jcdubacq — Tuesday 13 April 2010

Le séminaire OCAD recevra le 13 avril Xavier Provençal (postdoctorant au LIRMM et au LAMA, Montpellier).

L’étude de la combinatoire des mots a mené à la caractérisation de nombreux langages. Certains admettent (ou sont fondés sur) une interprétation géométrique. Une caractérisation de la convexité discrète en terme de mots de Lyndon et de Christoffels sera présentée. De cette caractérisation, on déduit un test algorithmique optimal et très rapide en pratique. Également, cette vision combinatoire de la convexité discrète met en valeur la notion de « concavité minimale », une notion propre au monde discret. La structure combinatoire particulière de ces mots "non-convexes minimaux" sera également présentée.

Minorité stochastique et de ses particularités

jcdubacq — Tuesday 6 April 2010

Le séminaire OCAD recevra le 6 avril Damien Regnault (ATER au LIF-CMI, Marseille).

Cet exposé commence par la présentation rapide de la règle Minorité stochastique et de ses particularités. Ensuite, je présenterai une application de cette règle pour modéliser la formation de quasi-cristaux.

Considérons un graphe où chaque sommet reçoit la couleur noire ou blanche. Une arête contient une erreur si elle relie deux sommets de la même couleur. Minorité est une dynamique stochastique minimisant rapidement l’énergie. Sous cette dynamique, un sommet, chosi aléatoirement et uniformément parmi l’ensemble des sommets, peut changer d’état si au moins la moitié des arêtes qui lui sont adjacentes sont erronées.. Cette dynamique est sensible à la topologie du graphe et son analyse fine s’est révélée compliquée.

En physique, dans les années 70, il était conjecturé que toutes les structures ordonnées soient périodiques. En 1984, un contre-matériaux fût découvert et reçu le nom de quasi-cristal. Dès 1974, Penrose avait présenté un structure théorique ordonnée et apériodique. Le but de notre projet est de présenter un modèle pour expliquer la formation d’une telle structure. Pour cela, nous considérons le modèle des pavages par coupe et projection (qui contient le pavage de Penrose). En définissant une notion d’erreur et d’énergie sur ces pavages, la règle Minorité procédant par flips permet de converger rapidement expérimentalement vers une structure ordonnée qui selon la famille de pavages par coupe et projection considérée est soit périodique, soit apériodique. Je présenterai nos résultats expérimentaux ainsi que notre analyse de cette dynamique pour les pavages 2 vers 1 (mots sur deux lettres).

Algorithmique des tresses : la forme normale tournante

jcdubacq — Tuesday 30 March 2010

L’équipe OCAD accueille Jean Fromentin (ATER, Laboratoire GREYC, université de Caen).

Une tresse, est un objet géométrique composé de brins qui se croisent.. En mettant bout à bout deux tresses ayant le même nombre de brins, on obtient une nouvelle tresse. Munis de cette opération, l’ensemble des tresses à n brins forme un groupe. Une présentation, par générateurs et relations de ce groupe, est donnée en 1942 par Artin. Une tresse peut alors être vue comme une classe d’équivalence de mots de tresse. Une forme normale est alors un moyen (souvent algorithmique) de sélection pour une tresse d’une mot de tresse distingué la représentant.

L’exposé sera divisé en deux parties. La première sera consacrée à une introduction aux groupes de tresses : point de vue intuitif, structure de groupe, présentation d’Artin, problème du mot, etc. Dans la seconde, je présenterai l’objet central de mes travaux, qui est une nouvelle forme normale des tresses, dite forme normale tournante, et j’expliquerai (un peu) en quoi cette nouvelle forme est intéressante, notamment en liaison avec l’ordre de Dehornoy des tresses. Ensuite, je me concentrerai sur les aspects plus informatiques de cette approche, à savoir la construction d’automates explicites reconnaissant les formes tournantes. Seuls les idées seront présentées dans cet exposé, les détails techniques seront volontairement omis.

Characterizations and Algorithms for Scheduling Problems with Unity-Time Jobs and Unit-Penalty Objective Function

jcdubacq — Tuesday 16 March 2010

L’équipe OCAD accueille Rosiane de Freitas Rodrigues (D.Sc. DCC/ICE - Federal University of Amazonas COPPE-Federal University of Rio de Janeiro, Brazil ).

This work deals with scheduling problems with unit execution time jobs, time-windows constraints, parallel machines and the objective function of minimizing the total number of tardy jobs. The emphasis is on deterministic scheduling, characterization theorems, polynomial time algorithms and their computational complexities, and the use of graph theoretical tools, whenever is possible. New models and characterizations have been proposed, that result in better algorithms. For the problems 1 | pj=1; rj | sum Uj, and P | pj=1; rj | sum Uj, formulated in the 3-field notation, a time complexity of O(n log n) was obtained. For the problems 1 | pj=1; rj | sum wjUj, and P | pj=1; rj | sum wjUj , a better upper bound with O(n² (1+logm/m) ) time complexity was obtained. The best time complexity for such problems was O(n^3m), based on network flows techniques.

We also consider a multi-purpose machine scheduling problem, where jobs should be executed in some machine belonging to a given subset of the set of machines. The problem is PMPM | pj=1; rj | sum wjUj, with n independent unit-time jobs, time window constraints, m identical parallel multi-purpose machines, and the minimization of the total weighted number of tardy jobs. The best previous complexity for this problem is O(n²m(n + log m)), employing network flow techniques. We develop an algorithm that uses basic concepts of computer science to handle more efficiently successive nesting of on-time jobs, with O(n³) overall time complexity.

It is expected that the results serve as a means for better understanding of other scheduling problems, offering new characterizations and more efficient algorithms.

MIP models and exact solution approaches for the discrete lot-sizing and scheduling problem

jcdubacq — Tuesday 9 March 2010

L’équipe OCAD accueille Céline Gicquel (post-doctorant, Laboratoire génie industriel, École Centrale Paris).

Nowadays, industrial companies increasingly find that they must rely on effective supply chains to successfully compete in the global market and networked economy. In particular, production planning plays a major role in supply chain management due to its strong impact on customer service quality and company profitability. Among the most challenging problems to be solved within the production planning process are the decisions on the size and schedule of production lots.
We first provide a basic introduction on lot-sizing problems, as well as a brief overview of the lot-sizing literature. We then focus on a variant of lot-sizing problem known as the discrete lot-sizing and scheduling problem and investigate the integration of two relevant industrial concerns into the basic problem. More precisely, we consider the following operational aspects: the case of sequence-dependent start-up costs and the presence of identical parallel resources.
Both variants are difficult discrete optimization problems which can be modelled as mixed-integer linear programs. We propose, for each of them, an exact solution approach based on the use of tight MILP formulations.

Réduction de graphes pour la segmentation d'images par coupe de graphe

jcdubacq — Tuesday 2 March 2010

L’équipe OCAD accueille Nicolas Lermé (doctorant, LIPN).

In few years, graph cuts have become a leading method for solving a wide range of problems in computer vision and graphics. However, graph cuts involve the construction of huge graphs which sometimes do not fit in memory.

Currently, most of the max-flow algorithms are totally impracticable to solve such large scale problems. In the image segmentation context, some authors have proposed banded of hierarchical approximation methods to get round this problem.

We propose a new strategy for reducing graphs during the creation of the graph where the nodes of the reduced graph are typically located in a narrow band surrounding the object edges.

Empirically, solutions obtained on the reduced graphs are identical to the solutions on the complete graphs. Moreover, the time required by the reduction if often compensated by the time that would be needed to create the remove nodes and the additional time required by the max-flow on the larger graph. Finally, we show experiments for segmenting large volume data in 2D and 3D.

Analyse symbolique des algorithmes de recherche de séquence génératrice optimale dans une structure présentée

jcdubacq — Tuesday 16 February 2010

L’équipe OCAD accueille Ali Akhavi (laboratoire GREYC, université de Caen).

Pour étudier un algorithme de tri classique sur /n/ nombres réels distincts, il suffit d’étudier l’algorithme sur les antécédents de /(1,2,...,n)/, i.e. sur les /n!/ énumérations des éléments de l’ensemble /{1,...,n}/. L’exécution de l’algorithme sur l’ensemble de ces /n!/énumérations permet de constater toutes les exécutions possibles de l’algorithme.
Lorsque les algorithmes sont décrits à la manière des systèmes dynamiques symboliques, chaque exécution est une suite de transformations élémentaires. Afin de caractériser parmi tous les mots sur l’alphabet des transformations élémentaires, ceux qui correspondent à des traces d’exécutions, il suffit donc pour les tris classiques de considérer les traces d’exécutions sur un ensemble générique : l’ensemble des / / énumérations des éléments de l’ensemble /{1,...,n}/.

Nous fournissons un cadre permettant d’exhiber de tels ensembles génériques d’entrées // pour les algorithmes de recherche de séquence génératrice optimale dans une structure présentée (les tris en sont des exemples particuliers mais cela englobe aussi les algorithmes d’Euclide de Gauss et bien d’autres).

Une structure présentée est une structure munie d’un squelette pour sa présentation (ou encore son codage) : un entier pour le cardinal d’une séquence génératrice et un ensemble de mots correspondants aux relateurs. Nous nous intéressons à de tels objets munis d’un préordre, lorsqu’ils possèdent beaucoup (éventuellement une infinité) de séquences génératrices. Nous considérons les algorithmes qui partant d’une séquence génératrice quelconque retournent une séquence génératrice satisfaisant certaines propriétés vis-à-vis du préordre.

Comparaison et évaluation en moyenne de processus d'optimisation pour le problème du vertex cover

jcdubacq — Tuesday 26 January 2010

L’équipe OCAD accueille François Delbot (docteur, IBISC, Université d’Évry).

La théorie de la complexité distingue les problèmes que l’on sait résoudre en un temps polynomial en la taille des données (que l’on peut qualifier de raisonnable), des problèmes NP-complets, qui nécessitent (en l’état actuel des connaissances) un temps de résolution exponentiel en la taille des données (que l’on peut qualifier de déraisonnable).

C’est pour cette raison que la communauté scientifique s’est tournée vers les algorithmes (polynomiaux) d’approximation dont la mesure de qualité se fait le plus souvent grâce au rapport d’approximation en pire cas (pour un problème de minimisation de taille, un algorithme a un rapport d’approximation de k si la taille de toute solution pouvant être retournée par l’algorithme est inférieure ou égale à k fois la taille de la solution optimale).

Dans la littérature, on en vient à considérer qu’un algorithme est plus performant qu’un autre lorsqu’il possède un plus petit rapport d’approximation en pire cas. Cependant, il faut être conscient que cette mesure, désormais "classique", ne prend pas en compte la réalité de toutes les exécutions possibles d’un algorithme (elle ne considère que les exécutions menant à la plus mauvaise solution).

Dans les travaux que je vais vous présenter, nous avons tenté de mieux "capturer" le comportement des algorithmes d’approximation en allant plus loin que le simple rapport d’approximation en pire cas (en nous focalisant sur le problème du Vertex Cover) :

En montrant que les performances moyennes d’un algorithme peuvent être décorélées des performances en pire cas. Par exemple, nous avons montré que dans la classe des graphes spécialement conçus pour le piéger en pire cas, l’algorithme glouton "Maximum Degree Greedy" retourne, en moyenne, des solutions dont la taille tend vers l’optimum lorsque n tend vers l’infini.

En évaluant les performances moyennes d’un algorithme. Nous avons prouvé que l’algorithme online présenté par Demange et Paschos en 2005 (dont le rapport d’approximation en pire cas est égal au degré maximum du graphe) est au plus 2-approché en moyenne dans n’importe quel graphe. Ce résultat, combiné à d’autres, montre que cet algorithme est "en pratique" meilleur que la plupart des algorithmes 2-approchés connus, malgré un mauvais rapport d’approximation en pire cas .

En comparant les performances de différents algorithmes (analytiquement et expérimentalement). Nous avons proposé un algorithme de liste et nous avons prouvé analytiquement qu’il retourne toujours une meilleure solution que celle construite par un autre algorithme de liste récent [ORL 2006] quand ils traitent la même liste de sommets (dans certains graphes particuliers, la différence de taille peut être arbitrairement grande).

Nous avons également comparé analytiquement (en utilisant des outils comme les séries génératrices) les performances moyennes de six algorithmes sur les chemins. Nous les avons ensuite expérimentées sur un grand nombre de graphes de diverses familles bien choisies.

On constate dans ces études que les algorithmes 2-approchés étudiés sont ceux qui obtiennent les plus mauvaises performances en moyenne et que ceux qui ont les meilleurs comportements moyens ont de mauvais rapports d’approximation (fonction du degré max. du graphe).

Tous ces résultats montrent que le rapport d’approximation en pire cas n’est pas toujours suffisant pour caractériser l’intégralité de la qualité d’un algorithme et que d’autres analyses (en moyenne notamment) doivent être effectuées pour en faire le tour.

Expressions booléennes aléatoires : probabilités, complexité et comparaison quantitative de logique propositionnelle

jcdubacq — Tuesday 12 January 2010

Pour son premier séminaire de l’année ce 12 janvier, l’équipe OCAD accueille Antoine Genitrini (ATER, PRISM, Université de Versailles Saint-Quentin-en-Yvelines).

Écrivez une formule booléenne de manière aléatoire, construite avec des ensembles fixés de connecteurs et de littéraux. Quelle est la fonction booléenne « typique » qu’elle représente ? Quelle est la probabilité que la formule calcule la fonction Vrai ? Un littéral ? Ou une autre fonction donnée ? D’autres questions de nature un peu différente peuvent se poser : quelle est la complexité de la fonction booléenne représentée par cette formule aléatoire (i.e. la taille de la plus petite formule la représentant) ? Quelle est la complexité moyenne d’une fonction booléenne définie sur k variables ?

Ces questions mettent en avant le problème suivant : comment définir une distribution de probabilité sur les fonctions booléennes ? Les premiers articles se posant ce genre de questions ont mis en avant deux modèles de formules booléennes aléatoires, basées sur les connecteurs binaires Et/Ou, et qui engendrent une distribution (non uniforme) sur les fonctions booléennes. Ces articles n’ont répondu que très partiellement aux premières questions que j’ai évoquées. On adapte aisément ces distributions au cas de formules construites à l’aide de l’unique connecteur Implication, un des connecteurs de base d’un point de vue logique. Ce modèle de base suscite de l’intérêt car certaines formules représentant des tautologies (formule calculant toujours Vrai) en logique classique ne sont pas des tautologies en logique intuitionniste.

Dans un premier temps, j’exposerai les résultats concernant l’ensemble des fonctions booléennes construites sur l’Implication, puis j’aborderai en détail les tautologies. Dans un troisième temps, j’enrichirai le modèle de formules en utilisant plusieurs connecteurs logiques aléatoires. Enfin, je conclurai l’exposé en abordant différentes perspectives relatives à ces problèmes et sur lesquelles je travaille actuellement.