LIPN

Responsable : Christian LAVAULT

Optimisation Combinatoire et Algorithmique Distribuée

Les trois thèmes de recherche développés par l’équipe OCAD (Optimisation Combinatoire et Algorithmique Distribuée) sont à la jonction des disciplines étroitement complémentaires que sont les mathématiques discrètes, l’optimisation combinatoire et l’algorithmique. Ces thèmes concernent les traitements séquentiels et parallèles des structures discrètes et leurs utilisations dans divers domaines informatiques. Son intérêt se porte sur le développement d’algorithmes efficaces (approchés, voire exacts pour certaines instances) pour résoudre des problèmes NP-complets et sur la combinatoire et l’algorithmique des systèmes distribués et parallèles.

Nos différents objectifs concernent donc d’une part, l’Optimisation Combinatoire avec la poursuite des travaux fondamentaux et appliqués en optimisation en nombres entiers (thème 1), l’élaboration de méthodes spécifiques du problème de satisfaction et d’optimisation des systèmes de contraintes (thème 2), et d’autre part, la combinatoire et l’algorithmique pour les systèmes distribués et parallèles (thème 3).

– L’année 2001-2002 a été marquée par l’accueil de Nelson Maculan (professeur à l’Université de Rio de Janeiro) sur un poste de chercheur CNRS et par l’arrivée d’un nouveau membre : Vlady Ravalomanana (Maître de Conférences, Institut Galilée). Elle a en outre été l’occasion de rédiger un chapitre conséquent (une centaine de pages) sur la programmation linéaire en nombres entiers d’un ouvrage consacré aux outils d’analyse numérique pour l’automatique (Hermès, 2002).

– L’année 2002-2003 a vu l’arrivée de trois nouveaux membres : Jean-Christophe Dubacq (Maître de Conférences, IUT de Villetaneuse), Cyril Banderier (Chargé de recherches CNRS) et Laurent Alfandari (Professeur à l’ESSEC).

– En 2003, l’équipe OCAD accueille Alfredo Viola (Professeur à l’Université de Montevideo) sur un poste de chercheur CNRS et Jean-Marie Le Bars (Maître de Conférences à l’Université de Caen) en délégation CNRS au LIPN (2003-2004) et intègre Lucas Létocart (Maître de Conférences, Institut Galilée).

Thème : Optimisation en nombres entiers (Laurent Alfandari, Patrick Boucher, Rafaël Castro de Andrade, Philippe Bourgeois, Virginie Gabrel, Lucas Létocart, Anass Nagih, Nelson Maculan, Ferhan Pekergin, Gérard Plateau, Babacar Thiongane, Vassilis Zissimopoulos).

Note : nos publications citées dans le texte spécifient (entre crochets) les noms des revues et uniquement les sigles des conférences avec les années de référence (cf. Liste des publications).

Les travaux fondamentaux en optimisation en nombres entiers concernent :

• l’accélération du déroulement des méthodes existantes par l’étude d’algorithmes efficaces (de complexité temporelle polynomiale) de réduction de l’espace des solutions réalisables et/ou optimales des problèmes traités :

– construction d’heuristiques (algorithmes gloutons ou approchants polynomiaux) et de métaheuristiques performantes ; étude des propriétés structurelles de voisinages, de voisinages exacts et approchés, de la rugosité des paysages et de fonctions d’autocorrélation. L’utilité des métaheuristiques est désormais bien reconnue, mais bien que leurs bonnes performances aient pu être vérifiées expérimentalement, leur justification théorique est un défi majeur de l’algorithmique qui n’a commencé à être étudié que récemment [Discrete Applied Mathematics 2000, Theoretical Computer Science 2001] :

. recherche tabou pour les problèmes de knapsack hyperboliques [ROADEF’00] et de biknapsack [MIC’01] en variables 0-1 ;

. mise en place (en collaboration avec des membres du LRI, Université de Paris-Sud) d’un nouveau cadre théorique qui relie le comportement des métaheuristiques avec la notion du “ paysage ” des solutions approchées et avec d’autres caractéristiques combinatoires des instances du problème et des propriétés structurelles de voisinages ; la notion de la “ rugosité ” des paysages ainsi développée a permis d’apporter une justification théorique à plusieurs faits observés dans des études expérimentales et d’obtenir un début de classification de problèmes d’optimisation combinatoire. Les recherches dans cette direction ont été renforcées par la mise en place d’une Action Spécifique du MENRT, intitulée Approximation et Recherche Locale impliquant en plus du LIPN, six autres laboratoires de recherche (LaMI, Université d’Evry ; LRI, Université Paris XI ; LMC, Leibniz, GILCO, Université de Grenoble ; LIRMM, Université de Montpellier II) ;

. heuristiques pour le problème de Steiner euclidien dans IRⁿ [1 chapitre de livre Kluwer 02, ROADEF’00].

– conception et résolution de relaxations (Lagrangienne, agrégée, décomposition lagrangienne) ; cette notion de dualité associée aux heuristiques fournit des encadrements aux valeurs des problèmes, et conduit à la réduction de leur taille, ainsi qu’à celle de l’arborescence de parcours des solutions :

. conception d’une nouvelle décomposition lagrangienne pour les problèmes hyperboliques en variables 0-1 [International Journal of Mathematical Algorithms 00] ;

. conception d’une nouvelle dualité lagrangienne pour la programmation concave-convexe [Comptes Rendus de l’Académie des Sciences 00] :

. conception d’une nouvelle relaxation pour le problème de Steiner euclidien [Nonconvex Optimization and its Aplications 01] ;

– réoptimisation des problèmes en nombres entiers avec l’étude approfondie de la résolution du dual lagrangien du biknapsack en variables 0-1, sujet de la thèse de Babacar Thiongane ; après un état de l’art sur l’analyse de sensibilité des problèmes combinatoires [ROADEF’02, 1 article accepté dans RAIRO-Operations Research], plusieurs méthodes (dont MARIE : Metaheuristics Associated with Reoptimization for Integer programming Evoluating instances) ont déjà été élaborées pour résoudre efficacement le dual lagrangien par des méthodes de sous-gradient adaptées [MIC’01, CO’02, CIRO’02, ROADEF’03, Discrete Applied Mathematics, Annals of Operations Research].

D’autre part, ces relaxations sont également exploitées pour élaborer de nouvelles heuristiques :

– enchaînement de métaheuristiques et de relaxations lagrangiennes pour les problèmes hyperboliques en variables 0-1 [ROADEF’00] ;

– heuristique lagrangienne dans MARIE, méthode de réoptimisation dédiée au dual lagrangien du biknapasack en variables 0-1, qui associe la métaheuristique tabou et des techniques de réoptimisation [CO’02] ; combinaison de relaxations et de techniques de perturbations pour des méthodes approchées à variables continues. Cette recherche fait l’objet d’un projet bilatéral CNRS-TÜBITAK (organisme de recherche scientifique et technique de Turquie).

• l’élaboration de méthodes exactes par une étude approfondie des structures de données et des complexités, des algorithmes liés à la programmation dynamique, l’énumération implicite et la programmation linéaire :

. résolution en temps linaire du problème hyperbolique en variables 0-1 sans contraintes [Investigacion Operativa 00] ;

. résolution exacte du sac à dos multidimensionnel en variables bivalentes à l’aide de la combinatoire polyédrique [Operations Research Letters] ;

– dans le cadre de la thèse de Rafaël Castro de Andrade sur l’optimisation stochastique en nombres entiers pour le dimensionnement de réseaux de télécommunications avec demandes incertaines, élaboration de méthodes de Benders et de branch-and-cut. Ces travaux ont été réalisés avec Abdel Lisser (LRI, Orsay), co-directeur de la thèse et Nelson Maculan [INFORMS’00, CO’02, ROADEF’02] ;

• l’élaboration de modélisations appropriées pour la détermination de sous-graphes connexes de poids minimal d’un graphe valué (par exemple, chemin élémentaire, arbre, cycle) [Pesquisa Operacional 03].

Plusieurs applications mettant en jeu l’optimisation en nombres entiers sont ou ont été également traitées (la plupart d’entre elles concernent les réseaux de télécommunications) :

– Optimisation combinatoire multicritère dans le domaine des télécommunications (Patrick Boucher, Virginie Gabrel, Anass Nagih, Gérard Plateau, Babacar Thiongane) : il s’agit de prendre en compte les deux objectifs conflictuels que sont le coût du réseau et la qualité du service proposé sur ce réseau ; ce projet a fait l’objet d’un contrat de type CTI avec France Télécom-CNET (durée de dix-huit mois en 99-01) (autre participant : Daniel Vanderpooten du LAMSADE) [Rapport technique de France Telecom R&D 01].

– Approximabilité et Recherche locale (Lucian Finta, Vassilis Zissimopoulos) : ce projet ASP du MENRT déjà évoqué dans la partie métaheuristiques (septembre 99-septembre 2001), a concerné des recherches théoriques dans les domaines des réseaux et du parallélisme ; l’objectif a été la conception des algorithmes d’approximation et des algorithmes “ on-line ”, et l’étude de la rugosité des paysages des métaheuristiques pour développer des techniques algorithmiques [Journal of Heuristics].

– Recherche opérationnelle et Contraintes pour la conception de réseaux (ROCOCO) (Vassilis Zissimopoulos) : ce projet RNRT (partenaires : ILOG, France-télécom-CNET, LRI et INRIA ; octobre 99-octobre 2001) a concerné le développement de techniques logicielles intégrant l’efficacité de l’optimisation combinatoire et la flexibilité de la programmation par contraintes pour optimiser le dimensionnement et le redimensionnement de réseaux de télécommunications, d’entreprises en particulier [JNPC’01].

– Evaluation des performances des systèmes de télécommunications (Ferhan Pekergin) : développement de la méthode dite de diffusion transitoire comme outil de dimensionnement, contrôle et optimisation des réseaux à hauts débits, les réseaux ATM en particulier. Ce projet entre dans le cadre d’une coopération CNRS-PAN (Académie des Sciences de Pologne).

– Dimensionnement de réseaux de télécommunications à coût minimum (Virginie Gabrel en collaboration avec Michel Minoux et Arnaud Knippel du LIP6) : ce problème se modélise sous la forme d’un problème de multiflot à coût minimum avec des fonctions de coût croissantes en escalier.

– Planification de missions spatiales se posant pour des systèmes satellitaires de type SPOT (Virginie Gabrel) : une modélisation sous la forme d’un programme linéaire en variables 0-1 est proposée pour ce problème combinatoire difficile ; des techniques de génération de colonnes sont mises en jeu pour la résolution exacte [Chapitre de livre].

– Rotations d’équipages en transport aérien (Anass Nagih en collaboration avec François Soumis et Yassir Miladi du GERAD, Montréal, Canada) : ce problème peut être modélisé sous la forme d’un problème de partitionnement. Sa résolution par une technique de génération de colonnes aboutit à des sous-problèmes de plus court chemin avec contraintes de ressources [Optimisation Days’02, Cahiers du GERAD 00 et 02, EJOR, séminaire LAMSADE 00].

Prospectives (du thème Optimisation en nombres entiers)

• réoptimisation pour les problèmes en nombres entiers : poursuite de l’étude de l’enchaînement de résolutions de problèmes voisins (analyse de sensibilité, paramétrisation et incrémentalité) ; l’étude de la résolution efficace du dual lagrangien par un algorithme de type sous-gradient ou de génération de colonnes sera privilégiée ;

• gestion de production et planification en transport ferroviaire, dans le cadre d’une bourse CIFRE SNCF ;

• génération de colonnes adaptée à l’optimisation en nombres entiers.

Thème : Satisfaction et optimisation des systèmes de contraintes (Mohamed Salah Affane, Saïd Belhadji, Hachemi Bennaceur, Faycal Djerourou, Gérard Plateau)

Les problèmes abordés sous ce thème jouent un rôle essentiel en programmation par contraintes (PPC). La PPC permet de résoudre des problèmes combinatoires pouvant contenir divers types de contraintes associées à des applications réelles (par exemple les problèmes classiques de la RO, la planification, l’ordonnancement).

Le problème de satisfaction et d’optimisation de systèmes de contraintes est un problème central de la PPC. Ce problème est défini par un ensemble de variables (objets), chaque variable possède un domaine de valeurs possibles, et un ensemble de contraintes qui peuvent être des équations, des inéquations numériques, des formules symboliques, ou tout simplement des relations sur des sous-ensembles de variables.

L’objectif peut être double, dans le cas d’un problème de décision (CSP), le but est de vérifier la cohérence d’un système de contraintes, dans le cas d’un problème d’optimisation (Max-CSP), le but est de déterminer une meilleure solution suivant un critère donné ou de déterminer le nombre maximum de contraintes satisfaites dans le cas d’un problème sur-contraint.

Un chapitre d’ouvrage [“Optimisation approchée en recherche opérationnelle : Recherche locale, Réseaux neuronaux et Satisfaction de contraintes”, Hermès, 2002 (une trentaine de pages)] a été rédigé pour faire le point sur cette problématique de l’intégration des techniques de recherche opérationnelle en programmation par contraintes.

Les sous thèmes abordés dans ce contexte sont :

Algorithmes pour la satisfaction et l’optimisation

L’objectif visé est la conception de techniques de filtrage et de réduction de l’espace des solutions. Elles permettent l’accélération des algorithmes de recherche de solutions pour la satisfaction et l’optimisation des systèmes de contraintes. Nos travaux s’appuient plus particulièrement sur les techniques de filtrage dites arc consistance et chemin consistance, les techniques de coloriage de graphes, les techniques de recherche locale, et d’une manière générale sur un ensemble d’outils de l’optimisation combinatoire (par exemple les relaxations et le branch and bound) [CP’01, TAST’02, JNPC’02, rapport LIPN 00-01, Constraints].

Les deux autres sous-thèmes ont pour fondement des applications :

Problème d’affectation de fréquences à des lignes de communication radio

Etant donné un réseau de communication composé de plusieurs sites émetteur–récepteur reliés par des voies de communication, l’objectif est d’affecter des fréquences aux voies de communication de sorte à éviter les interférences. La vérification d’un ensemble de contraintes déterminées expérimentalement permet de garantir le bon déroulement des communications. La modélisation de ce problème en termes de CSP binaire conduit à des instances difficiles. Dans le cadre de la thèse de Fayçal Djerourou, nous étudions sur des instances réelles de ce problème, les techniques de recherche locale combinées avec des techniques de filtrage de CSP [ROADEF’02].

Vérification de la validité d’un schéma conceptuel d’une base de données

Différents types de contraintes peuvent intervenir lors de la conception du schéma conceptuel d’une base de données. Afin de créer la base de données, il est nécessaire de vérifier la cohérence globale du système formé par ces contraintes.

Nous étudions la modélisation des différents types de contraintes (par exemple cardinalités, dépendances fonctionnelles, inclusions, exclusions, rôles) et concevons des méthodes pour résoudre les systèmes de contraintes permettant de décider si une base de données est instanciable ou non.

Ces travaux se font en collaboration avec F. Boufares de l’équipe Logique, Calcul et Raisonnement [ECITE’2002].

Prospectives (du thème Satisfaction et optimisation des systèmes de contraintes)

• Elaboration de métaheuristiques performantes pour les problèmes de satisfaction maximale de contraintes.

Thème : Combinatoire et algorithmique pour les systèmes distribués et parallèles (Cyril Banderier, Lélia Blin, Franck Butelle, Jean-Christophe Dubacq, Lucian Finta, Christian Lavault, Jean-Marie Le Bars, Eythan Levy, Gabriel Paillard, Vlady Ravelomanana, Sidi-Mohamed Sedjelmaci, Alfredo Viola).

Note : Les références aux publications spécifient (entre crochets) le premier auteur, le nom (ou le sigle) de la revues ou conférences et l’année (cf. Liste des publications).

L’algorithmique, la combinatoire analytique et, plus généralement, les mathématiques discrètes appliquées à l’étude des systèmes parallèles et distribués couvrent un domaine très vaste et leurs méthodes et leurs outils sont complémentaires. On les retrouve donc naturellement dans la conception et l’analyse des performances des algorithmes distribués, dans l’algorithmique du parallélisme, aussi bien que dans l’étude des graphes aléatoires ou des propriétés algébriques des réseaux d’interconnexion.

Ce thème de recherche est ainsi composé de trois grands axes : 1) l’algorithmique distribuée, 2) la combinatoire des structures discrètes et aléatoires, 3) l’algorithmique des systèmes parallèles. Chacun d’entre eux est lui-même divisé en deux sous-axes de recherche qui en forment l’ossature.

Les deux premiers axes sont intégrés depuis 1998 au groupe de travail ALEA du GDR ALP (Algorithmique, Langage et Programmation). Depuis décembre 2001, ALEA participe à l’action MathSTIC du CNRS dont fait partie l’équipe CADAD (Combinatoire et analyse d’algorithmes distribués, responsable : Christian Lavault), qui regroupe une dizaine d’enseignants-chercheurs et doctorants de notre groupe et du LaRIA (Laboratoire de Recherche en Informatique d’Amiens).

Nos coopérations scientifiques avec des laboratoires ou équipes de recherche en France sont nombreuses et variées : GREYC (CNRS, Univ. de Caen), INRIA (Rocquencourt), LaBRI (CNRS, Univ. Bordeaux 1), LAMA (CNRS, Univ. de Versailles), LIRM (CNRS, Univ. Marseille), LRI (CNRS, Univ. Paris 11), LRIA (Univ. Paris 8), PRiSM (Univ. de Versailles), etc.

Il en va de même pour nos coopérations avec les laboratoires étrangers de plusieurs pays, en particulier des chercheurs renommés : A. Calabrese (CNR, Istituto di Informatica, Naples, Italie), E. Kranakis, D. Krizanc et N. Santoro, (Carleton Univ., Ottawa, Canada), C. Krattenthaler (Un. de Vienne, Autriche, et ENSL), S. Kutten, S. Zaks (Technion, Israël), K. Mehlhorn (Max-Planck-Institüt für Informatik, Saarbrücken, Allemagne), G. Louchard (ULB, Bruxelles, Belgique), D. Merlini (Un. de Florence, Italie), Alfredo Viola (Un. de Montevideo, Uruguay), etc.

Le travail de recherche des deux premiers axes (algorithmique et combinatoire analytique) a fait l’objet de plus d’une dizaine de publications récentes dans des revues internationales avec actes (Discrete Maths, Discrete Applied Maths., Int. J. Foundation, of Comp. Science, J. of Optical Society of America, J. of Parallel. & Distributed Comp., J. of Stat. Planning & Inference, Parallel. Processing Letters, Studia Informatica, Theoretical Computer Science, Wireless Comm. & Mobile Comp.,) et d’une dizaine de conférences internationales avec actes (Annals of Algo., Coll. Math. & Comp. Science, Coll. Mathematical Foundations of Comp. Science, EURO’Combinatorics., FPSAC, IEEE Int. Conf. On Telecom., OPODIS, Random Structures and Algo.).

Le troisième axe (algorithmique parallèle) a également donné lieu à plusieurs publications récentes : deux revues internationales avec actes (J. Comput. & Appl. Math., J. of Algorithms) et cinq conférences internationales avec actes (IEEE Int. Conf. Comp. Syst. Appli., Euro-Par., ICPADS, AICCSA, ISSAC].

Systèmes distribués

Les systèmes distribués se caractérisent par un processus de circulation et d’échange de l’information entre entités autonomes communicantes concourant à la réalisation d’un objectif commun. Le développement d’outils et de méthodes algorithmiques appropriées (combinatoire analytique, méthodes stochastiques, asymptotique complexe, etc.) permet d’analyser plus finement de nombreux algorithmes distribués, en particulier en moyenne. En retour, ces méthodes permettent de concevoir de nouvelles classes d’algorithmes distribués, dont la complexité en communication et/ou en temps est notablement améliorée. Les types de réseaux considérés possèdent ainsi des topologies très diverses et jouissent de propriétés générales (réseaux synchrones ou asynchrones, anonymes, fautifs, etc.). L’algorithmique des réseaux mobiles, par exemple, se prête à des analyses et des recherches qui sont à la frontière de l’algorithmique distribuée, dans des environnements quelconques, anonymes, synchrones et, le cas échéant tolérants aux fautes. C’est là un champ d’investigation très prometteur commun aux deux premiers axes du thème : systèmes distribués et combinatoire des structures discrètes et aléatoires.

1. Réseaux mobiles (algorithmique-analyse en moyenne)

L’intérêt porté aux réseaux mobiles s’accroît sans cesse. Contrairement aux réseaux mobiles de type cellulaire, les réseaux ad hoc (ou MANET) peuvent se déployer rapidement et s’auto-organiser pour fournir des services très divers (séisme, incendie, sauvetage, etc.). Un réseau ad hoc est un système distribué anonyme, synchrone et non centralisé constitué de n stations sans connaissance a priori, ni “ information structurelle ” (exacte ou partielle), sur la structure du réseau (taille n, degré maximal, diamètre, topologie, via sa matrice d’adjacence, etc.). Les stations d’un réseau ad hoc peuvent communiquer à travers k canaux, k ≤ n. Déployées sans infrastructures ni assistance, ces stations doivent être capables de se constituer en une entité auto-organisée. Plusieurs protocoles probabilistes de base peuvent les y aider, entre autres : la diffusion, l’élection anonymes et l’“ initialisation ” qui permet à chaque station d’acquérir une identité unique i (1 ≤ i ≤ n). Les solutions et les performances sont cependant différentes selon que le protocole admet ou non la détection des collisions dans les canaux de communication. (L’analyse est moins difficile dans le cas où les collisions sont détectables.)

Outre ces contraintes, les réseaux ad hoc doivent pouvoir minimiser leur énergie. Les stations étant autonomes, chacune possède un potentiel énergétique limité (sa batterie par exemple). Il faut donc que l’exécution d’un protocole minimise l’énergie dissipée ; c’est chose possible en optimisant le temps d’éveil de chaque station. On dit alors que ce protocole est “ efficace en énergie ” (Energy Efficient), voire optimal si le temps d’éveil des stations atteint sa borne inférieure. Ce problème restait ouvert pour n inconnu. Nous l’avons résolu en proposant récemment deux algorithmes d’élection dans les réseaux radio, dont la complexité moyenne en temps est quasi optimale (asymptotique d’ordre log₂(n), à une constante multiplicative près) et dont le temps moyen d’éveil de chaque station ne dépasse pas log_alog₂(n) (asymptotiquement), pour un paramètre a bien choisi.

Ces travaux ont fait l’objet d’une publication dans une conférence avec actes [Lavault et al., IEEE ICT’03] et d’une soumission.

2. Tolérance aux fautes – Autostabilisation

Le calcul d’une fonction en présence de fautes est un problème fondamental en informatique distribuée. On sait qu’aucune fonction n’est calculable dans un système asynchrone non fiable. Il s’agit là d’une conséquence de l’impossibilité de résoudre le problème du consensus dans un environnement asynchrone : un seul processus fautif à l’émission de messages dans le système suffit pour interdire le consensus.

Dans un environnement distribué asynchrone, les algorithmes distribués tolérants aux fautes constituent donc une classe particulièrement intéressante d’algorithmes. Les fautes sont classées en fautes de processus (pannes, fautes d’émission/réception, fautes byzantines, etc.) ou/et fautes systémiques (corruption arbitraire des données). Les algorithmes autostabilisants, quant à eux, résolvent le problème crucial des fautes systémiques : ils sont tolérants aux fautes transitoires. De très nombreux algorithmes distribués autostabilisants, probabilistes ou déterministes, ont déjà été conçus, dans divers types de réseaux, anonymes (protocoles uniformes d’élection, de parcours, etc.) ou avec identités (exclusion mutuelle, primitives de communication asynchrone équitables, quasi rendez-vous, etc.).

Ces travaux ont fait l’objet de plusieurs publications internationales : trois revues [Lavault et al., Parallel. Proc. Letters (2000, 2002), Studia Informatica (2002)] et une conférence avec actes [Lavault et al., OPODIS’00].

L’analyse de la complexité moyenne en temps de stabilisation de protocoles autostabilisants uniformes (probabilistes) dans des réseaux asynchrones et anonymes utilise les techniques de la combinatoire analytique et des méthodes stochastiques (les marches aléatoires dans les graphes en particulier).

En commun avec le LRIA, nous avons ainsi publié deux algorithmes de construction d’arbres couvrants d’un graphe pondéré quelconque : d’une part, le premier algorithme distribué, autostabilisant d’arbre couvrant de diamètre minimal, dans une revue internationale [Butelle et al., J. of Parallel. and Dist. Comp. (2003)], et, d’autre part, un algorithme d’arbre couvrant de poids minimal, objet d’une conférence internationale avec actes [Butelle et al., OPODIS’01].

Combinatoire

1. Analyse perturbative (Smoothed Analysis)

Il s’agit ici de développer un nouvel outil : une mesure de complexité (intermédiaire entre le pire des cas et la complexité en moyenne) qui semble adéquat pour quantifier la “ difficulté ” d’un problème.

Les nombreux progrès en théorie des nombres de ces dernières années (mois !) montrent qu’il est sage de commencer à regarder sérieusement des cryptosystèmes basés sur des calculs “ difficiles ” autres que le traditionnel couple factorisation/log-discret. Il semble en effet bien plus probable que ces derniers soient mis à mal algorithmiquement, bien avant que l’on assiste à l’avénement des ordinateurs quantiques.

Il paraît donc naturel de regarder en direction des nombreux problèmes classés NP ou assimilés (d’optimisation et de combinatoire). En effet, être “ worst-case-NP ” est fort différent d’être “ average-case-NP ”, qui est lui-même fort différent d’être “ average-case-NP ” sur une région suffisamment grande. C’est en effet de ce dernier point dont on a besoin pour avoir un cryptosystème fiable : dans le “ paysage de complexité ” de l’algorithme, le pire des cas ne doit pas être un pic isolé mais un plateau.

Mais comment quantifier et étudier cette notion de “ problème difficile sur une grande région ” ? C’est là qu’intervient le concept de smoothed analysis (que nous traduisons ici par analyse perturbative) : où sont les instances difficiles ?

Le point de vue est le suivant : si les instances difficiles d’un problème sont “ isolées ” alors une perturbation de ces instances provoque une baisse de la complexité maximale de l’algorithme, tout en fournissant des sorties qui sont proches des sorties non perturbées.

Plus précisément, la complexité perturbée est ainsi définie comme le maximum sur les entrées du temps moyen mis par l’algorithme à s’exécuter sur les perturbations de l’entrée. (Un succès remarquable de cette approche est, pour l’instant, une explication de la complexité polynomiale en pratique de la méthode du simplexe.)

Depuis 2002, des travaux de C. Banderier et K. Mehlhorn ont montré que l’on pouvait utiliser une telle approche pour des problèmes discrets (via des exemples sur des algorithmes de bases en combinatoire). On a alors déjà quelques résultats surprenants (le pire des cas classiques n’est pas en fait la région la plus difficile, etc.) et des paysages de complexité assez variés. Notons au passage que cette étude fait intervenir de l’asymptotique de coefficients de fonctions de variables complexes (vérifiant des équations différentielles d’un certain type) qui apparaissent de façon ubiquitaire en analyse d’algorithme et qu’il y a là divers problèmes toujours ouverts.

Cette approche a donné lieu à quatre récentes publications internationales avec actes : une revue [Banderier et al., Discrete Maths, 2003] et trois conférences [Banderier et al., Coll. Math. Foundation of Comp. Science 2003, Ann. of Algo. 2003 et Rand. Struct. and Algo. 2003].

2. Graphes aléatoires

Les graphes aléatoires constituent un domaine très étudié des mathématiques discrètes. Les deux principaux modèles sont les modèles initiés par Erdös et Rényi (1959) et ce sont ceux qui sont les plus importants pour de nombreuses applications dans diverses branches de la science et notamment de l’informatique théorique. Deux grandes approches méthodologiques s’affrontent pour l’analyse de ces deux modèles de graphes aléatoires : l’approche probabiliste développée par Bollobás et l’approche énumérative et analytique initiée par Wright. La seconde approche prouve des résultats en nombre limité mais d’une précision sans rivale (vitesse de convergence, développement asymptotique, etc.). C’est dans ce dernier cadre que nous nous situons. Nous montrons en particulier que, dans les graphes connexes (la contrainte de connexité s’avère ici une difficulté majeure pour obtenir des résultats probabilistes), les graphes à N sommets et N + o(N^1/3) arêtes ne contiennent pratiquement jamais de sous-graphes multicycliques de taille fixe. Ces résultats sont obtenus en utilisant des méthodes analytiques d’énumération (séries génératrices) et d’asymptotique complexe (intégrale de Cauchy, méthode de col, inégalités de Wright, etc.).

Ils ont donné lieu à plusieurs publications internationales : trois revues [Ravelomanana et al., Th. Comp. Science, Discrete Applied Maths. (2003)] et trois conférences avec actes [Ravelomanana et al., FPSAC’03, Coll. Math. Comp. Science 2002, EURO’Combinatorics’01]. Des résultats similaires sont à l’étude pour les graphes denses ne contenant pas un ensemble prédéfini de configurations interdites. Par ailleurs, nous essayons aussi d’étendre ces résultats aux graphes orientés.

3. Réseaux mobiles (combinatoire analytique)

Les résultats déjà obtenus sur les protocoles “ efficaces en énergie ” dans les réseaux radio ou les réseaux mobiles permettent d’envisager deux classes de problèmes qui relèvent plus directement de la combinatoire des systèmes discrets que de l’algorithmique des systèmes distribués classiques.

La première a trait au routage par permutation des informations dans les réseaux mobiles. Soit n stations, k canaux et I informations, avec 1 ≤ k < n < I ; les informations détenues par une station ne lui sont pas nécessairement destinées. Comme chaque information possède une destination unique, il est possible de concevoir un protocole permettant à chaque station de recouvrer toutes ses informations propres. La complexité en temps du problème se mesure en termes de nombre de diffusions. Certaines solutions ont certes été déjà proposées, mais sous des hypothèses très restrictives. La conception et l’analyse en moyenne d’un protocole absolument général sont à la portée des méthodes classiques utilisées en combinatoire analytique.

La seconde classe de problèmes relève d’une problématique plus ambitieuse. Elle consiste à évaluer l’ensemble des caractéristiques (inconnues) d’un réseau mobile quelconque G. Sans aucune information structurelle sur G, il est possible de construire des algorithmes probabilistes (Monte-Carlo et Las Vegas) de diffusion permettant d’approcher son degré maximal, son diamètre D et enfin son nombre de sommets n, avec une faible erreur — i.e. avec une probabilité supérieure à 1 –  pour tout  > 0 (Monte-Carlo) ou bien avec une probabilité 1 (Las Vegas).

Dans les analyses en moyenne des classes de protocoles “ efficaces en énergie ” (voir Systèmes distribués) comme des classes d’algorithmes ci-dessus, la combinatoire analytique et les méthodes stochastiques permettent désormais d’obtenir des résultats suffisamment précis pour résoudre ces problèmes de manière satisfaisante : séries génératrices, simples ou exponentielles, en une variable ou bivariées, panoplie de techniques offerte par l’asymptotique réelle et complexe (intégrale de Cauchy, lemmes de transfert, transformées de Mellin, méthode de col, etc).

Ces analyses ont fait l’objet de trois publications dans des revues internationales [Ravelomanana et al., Wireless Comm. and Mobile Comp. (2003), J. of Optical Society of America (2002)].

Parallélisme

1. Ordonnancement pour les systèmes parallèles

Nous considérons plusieurs problèmes d’ordonnancement pour les calculs parallèles dans un système multiprocesseurs. Un programme parallèle est représenté par un graphe, où les sommets représentent les tâches et les arcs, les précédences et/ou les communications entre les tâches. Le problème consiste à affecter les tâches aux processeurs et à ordonnancer leur exécution, tout en respectant les contraintes de précédence, dans le but de minimiser la durée d’ordonnancement.

Plusieurs types de problèmes sont étudiés :

– Le cas de l’ordonnancement avec délais de communication unitaires et tâches unitaires pour lequel une amélioration de l’algorithme de E. Lawler a été proposée pour le cas de trois processeurs. Ce résultat à été publié dans une revue internationale [Finta et al., J. of Algo., 2002].

– Le cas des délais de communication longs identiques (et tâches unitaires) est également étudié pour un nombre de processeurs limité .

– Enfin, un autre type de problème est celui avec délais de précédence : deux tâches en précédence ne peuvent être exécutées sans un laps de temps entre la fin de la première et le début de la seconde.

2. PGCD de deux entiers

Le calcul du plus grand commun diviseur (PGCD) de deux entiers est une opération arithmétique fondamentale dont les applications sont multiples. La plupart des logiciels scientifiques utilisent l’algorithme séquentiel d’Euclide, connu depuis 23 siècles. L’algorithme de PGCD de deux entiers de Schönhage est de complexité en temps O(n(logn)²loglogn)) pour des entiers de n bits.

La situation est bien différente en calcul parallèle, puisque le PGCD demeure un des grands problèmes ouverts de la théorie du parallélisme. On ignore en effet si ce problème est dans la classe NC de P ou bien dans la classe P-complet (i.e. la classe la “ plus difficile ” de P). Le problème réside essentiellement dans la difficulté de concevoir un algorithme parallèle de PGCD d’entiers en temps “ polylog ” avec un nombre polynomial de processeurs (quasi-linéaire si possible). Deux directions de recherche s’imposent donc : soit tenter une démonstration directe de l’appartenance du problème à la classe P-complet, soit exhiber un algorithme parallèle de calcul du PGCD de deux entiers appartenant à NC.

Le meilleur algorithme parallèle proposé à ce jour est celui de Chor et Goldreich (1990) de complexité O(n/log(n)) sur un modèle de PRAM-CRCW avec n^1+ processeurs ( constante positive quelconque). Les résultats les plus récents dans ce domaine sont ceux de Sorenson, Jebelean et Weber (1994-1996), dont les algorithmes “ accélérés ” utilisent des techniques de “ réduction k-aire ”. L’amélioration de l’algorithme de Weber en particulier nous a permis de proposer un algorithme parallèle plus performant.

Ces travaux ont été publiés dans une revue [Sedjelmaci, J. Comp. App. Math. (2003)] et deux conférences internationales avec actes [Sedjelmaci, AICCSA 2001, ISSAC’01].

Prospectives (du thème Combinatoire et algorithmique pour les systèmes distribués et parallèles)

1. Étude algorithmique et analytique des réseaux mobiles. Conception et analyse en moyenne de diverses classes de protocoles de base de complexité en temps optimale et “ efficaces en énergie ”. Conception et analyse en moyenne d’algorithmes d’évaluation des caractéristiques (inconnues) de ces réseaux : degré maximal, diamètre, nombre de stations, topologie (matrice d’adjacence), etc.

2. Étude combinatoire et analytique de propriétés des graphes aléatoires. Étude et analyse de la croissance de composantes contraintes de graphes connexes denses et généralisation aux graphes connexes denses orientés. Conception et analyse d’algorithmes distribués probabilistes dans les modèles de graphes aléatoires géométriques (élection, diffusions, circuit hamiltonien, etc.).

3. Etude analytique de nombreux algorithmes (non nécessairement d’optimisation combinatoire) grâce aux outils de l’analyse perturbative, afin de dégager une meilleure vue de leur paysage de complexité (ce qui pourrait aider à long terme à une meilleure compréhension de P ? NP).

4. Étude théorique et pratique générale de la complexité moyenne en temps de stabilisation des algorithmes autostabilisants. Étude du comportement général de ces algorithmes dans divers types de systèmes répartis anonymes.

5. Étude de l’extension à plus de trois processeurs, du résultat du problème d’ordonnancement comportant des tâches et des délais de communication unitaires. Conception et analyse d’algorithmes de calcul du PGCD de deux entiers et de tests distribués de primarité (cribles d’Ératosthène et “ de la roue ”, etc.). Simulations des algorithmes déjà développés par l’équipe. Amélioration des meilleurs algorithmes existants. Généralisation à de nouveaux problèmes utilisant la récursivité.