Brevet FR2832828A1 — publié le 20030530

PROCEDE D'AIDE A LA CONCEPTION D'ALGORITHMES D'OPTIMISATION PRENANT EN COMPTE UNE LIMITE DE TEMPS La présente invention se rapporte à un procédé d'aide à la conception d'algorithmes d'optimisation prenant en compte une limite de temps. Elle vise à enrichir le cadre de la programmation par contraintes par l'introduction d'un contrôle temporel explicite dans les algorithmes de recherche. Un problème d'optimisation combinatoire sous contraintes se définit par un ensemble de variables de décision prenant des valeurs parmi des ensembles finis de valeurs, par un ensemble de contraintes sur les variables restreignant les combinaisons de valeurs permises, et enfin par une fonction, qui est, par exemple, s'il s'agit d'un problème de minimisation, une fonction de coût (il s'agirait d'une fonction de profit pour un problème de maximisation). Une solution à un tel problème est une affectation de toutes les variables qui satisfasse toutes les contraintes. Une solution optimale correspond à une solution ayant la plus petite valeur de la fonction de coût parmi l'ensemble des solutions existantes. Le traitement d'un problème d'optimisation combinatoire consiste à rechercher des solutions de faible coût, si possible optimales, ou, le cas échéant, à prouver l'absence de solution. Un exemple classique de problème d'optimisation combinatoire sous contraintes est le problème de la coloration d'un graphe. Une variable est associée à chaque sommet du graphe. Le domaine de valeurs des variables contient les couleurs disponibles. Une contrainte de différence relie chaque paire de variables dont les sommets sont liés par une arête. La fonction de coût correspond au nombre de couleurs différentes utilisées dans la solution. L'étude des problèmes de coloration de graphe sert en particulier dans le domaine des télécommunications, pour les problèmes d'allocation de fréquences à des liens radio dans un réseau hertzien. Une analogie est faite entre les couleurs et les fréquences. La complexité du traitement des problèmes combinatoires est souvent telle que seule la recherche de solutions de faible coût est envisageable dans un temps de calcul raisonnable. Un premier constat lié à la théorie de la complexité est qu'il n'existe pas d'algorithme efficace de recherche de solutions qui soit générique, c'est-à-dire capable de traiter efficacement tous les problèmes combinatoires. Il est nécessaire de développer un algorithme spécifique pour chaque classe de problème. La performance de l'algorithme dépend principalement de l'analyse du problème et de l'utilisation fine des résultats de cette analyse. Par exemple, le résultat de l'analyse peut-être une heuristique guidant le choix des valeurs. Dans le cas du coloriage, une heuristique simple consiste à choisir d'abord la couleur la plus utilisée dans la solution en cours de construction. Egalement, l'ordre d'affectation des sommets est important : pour diminuer la complexité pratique de la recherche, il faut commencer par les sommets le plus reliés aux sommets déjà affectés. De ce constat, il ressort que la conception des algorithmes de recherche est une tâche délicate qui nécessite des outils dédiés. La programmation par contraintes (PPC) offre un cadre technique pour de tels outils. De nombreuses applications d'optimisation, en particulier les applications temps réel embarquées, ont comme contraintes opérationnelles des limites strictes sur l'espace mémoire et le temps de calcul consommés. De façon générale, la limite de temps de calcul concerne tous les systèmes dits en-ligne, c'est-à-dire capables de réagir continûment à des événements extérieurs. C'est le cas par exemple des systèmes de replanification de tâches suite à de nouvelles demandes ou à des événements modifiant le plan initial. Un second constat est que les algorithmes de recherche existants dans les outils de PPC du commerce (flog, Cosytec, etc. ) ne prennent pas en compte explicitement les contraintes opérationnelles citées précédemment. C'est au programmeur de l'algorithme de mettre en oeuvre des moyens pour garantir les limites de mémoire et de temps. De plus, il ne bénéficie d'aucune aide pour décrire comment son algorithme exploite la limite temporelle. Il existe principalement deux classes d'algorithmes de recherche de solutions : (i) les méthodes de recherche globale et (ii) les méthodes de recherche locale. Les premières utilisent des mécanismes de raffinement de problème consistant à décomposer une instance de problème en plusieurs sous-instances indépendantes (produisant un arbre de décisions) et à appliquer un processus de filtrage excluant des affectations partielles jugées insatisfiables ou sous-optimales (processus de propagation des contraintes). Les secondes utilisent des mécanismes de transformation d'affectations complètes (qui ne respectent pas forcément toutes les contraintes). Ces deux approches peuvent être combinées : cela donne les méthodes hybrides, constituées de plusieurs recherches globales et/ou locales. En temps limité, la recherche globale effectue une exploration partielle de l'arbre. On parle alors de recherche partielle. De nombreux algorithmes ont été publiés pour explorer intelligemment l'arbre. On peut citer comme exemple l'algorithme"Limited Discrepancy Search" [voir la référence ? 6 à la fin de la description qui répète une recherche de plus en plus complexe en commençant par explorer les noeuds de l'arbre préférés par l'heuristique de choix de valeur puis en s'éloignant progressivement de ces noeuds. Un autre exemple est celui de l'algorithme"Realtime Heuristic Search" [voir la référence NO 8] qui utilise la limite temporelle pour adapter la profondeur de sa recherche en avant dans un contexte de planifications et d'exécutions entrelacées. Dans le cas de la recherche locale, celle-ci s'adapte assez aisément à une limite temporelle. De nombreux paramètres interviennent sur le réglage d'une recherche locale. Par exemple, le nombre de variables modifiées à chaque transformation. Ces paramètres influent sur la performance de l'algorithme en fonction du temps. On peut citer l'algorithme du recuit simulé [voir la référence No 1] dont la convergence du schéma de décroissance de la température peut être réglée pour terminer au plus juste dans le temps imparti. Enfin la prise en compte du temps dans une recherche hybride implique une répartition des efforts de calcul entre les différentes recherches globales et locales qui la composent. L'article"A Meta-Heuristic Factory for Vehicle Routing Problems (Meta-Programming for Meta-Heuristics)" [voir la référence NO 3] propose de construire automatiquement des algorithmes hybrides à partir d'un ensemble d'opérateurs de recherches élémentaires dédiés aux problèmes de tournées de véhicules. La construction se fait par une méthode d'apprentissage fondée sur un jeu d'instances et pour un temps de calcul donné. La complexité de l'algorithme hybride généré est estimée. Cela permet de ne conserver que les combinaisons et les réglages d'opérateurs qui conduisent à un algorithme dont le temps de calcul tient à peu près dans la limite temporelle. La programmation par contraintes (PPC) offre un langage informatique pour exprimer des problèmes d'optimisation combinatoire sous contraintes. Elle sépare nettement la phase de modélisation du problème, c'est-à-dire sa description sous forme de variables et de contraintes, de la phase de recherche de solutions. Initialement les outils de PPC ont mis l'accent sur la phase de modélisation en proposant un ensemble de contraintes ayant un grand pouvoir d'expression. Plus récemment des avancées ont été faites sur l'aspect langage de la phase de recherche de solutions. Le langage"Optimization Programming Language" (OPL) d'ilog [voir les références No 7 et No 13] offre un langage évolué dédié aux méthodes de recherche globale et partielle. OPL possède certaines fonctionnalités permettant de traiter plus efficacement un problème en temps limité : (i) des stratégies spécifiant un ordre d'exploration et (ii) des méthodes pour limiter la complexité d'une recherche. Une partie de la recherche en Intelligence Artificielle (IA) s'intéresse à la prise en compte de façon plus réaliste des contraintes temporelles dans les systèmes temps réel [voir la référence No 12]. Les algorithmes"anytime"font partie de cette mouvance. Un algorithme "anytime"est un algorithme capable de retourner à tout instant (par exemple avant la fin du temps de recherche imparti) une solution, et qui améliore la qualité de sa solution au cours du temps. Typiquement, les algorithmes de recherche de solutions sont"anytime"par nature si l'on fait l'hypothèse qu'il est possible de rendre une première solution, éventuellement partielle, à tout instant. Les travaux dans ce domaine s'intéressent au contrôle temporel des algorithmes employés en IA. On distingue trois modes de contrôle temporel d'un algorithme de recherche dépendant du type de contrainte temporelle : . Dans le mode contractuel, la limite temporelle est connue avant de faire la recherche. Elle est imposée soit dynamiquement par une requête venant de l'extérieur, soit statiquement par une exigence du système. L'algorithme de recherche doit exploiter au mieux le temps imparti et doit rendre une solution à l'échéance. Dans le mode interruptible, la limite temporelle est inconnue. La recherche sera interrompue en cours de route sur requête de l'extérieur. L'algorithme de recherche doit produire des solutions de qualité croissante au cours du temps. La performance de l'algorithme est jugée en fonction de sa courbe d'évolution de la qualité des solutions. Il est préférable que la progression de la qualité soit plus forte en début de recherche qu'après. . Dans le mode autonome, la limite temporelle est inconnue. C'est le contrôle temporel qui détermine le meilleur instant pour arrêter la recherche et rendre une solution. C'est l'approche principalement étudiée pour les algorithmes"anytime" [voir la référence NO 16 ]. Le contrôle temporel utilise généralement un apprentissage préalable à partir d'expérimentations pour réaliser la sélection et le réglage d'un algorithme de recherche. [voir la référence NO 15 ] étudie la répartition temporelle d'une limite temporelle parmi plusieurs composants d'un algorithme de traitement vocal pour optimiser la qualité en sortie. La présente invention s'applique principalement au mode contractuel. Le passage du mode contractuel au mode interruptible est possible [voir par exemple la référence No 14]. Chaque algorithme de recherche globale (ou partielle) définit un schéma d'exploration d'un arbre de décisions. De chaque schéma, on peut extraire un processus de contrôle temporel qui est le plus souvent adapté au mode interruptible (par exemple l'algorithme "Limited Discrepancy Search" [voir la référence NO 6]) et plus rarement au mode contractuel (par exemple l'algorithme"Realtime Heuristic Search" [voir la référence NO 8 D. Il en est de même dans le cas des algorithmes de recherche locale ou hybride. Cependant, la description du contrôle temporel ne s'appuie pas sur des primitives établies, génériques pour un ensemble de processus de contrôle temporel. C'est à la charge du programmeur d'implanter entièrement chaque contrôle temporel. La PPC ne contient pas non plus de telles primitives pour décrire un processus de contrôle temporel en mode contractuel. Il n'existe pas de primitive dans les systèmes PPC existants, qui facilite l'expression du lien entre une limite de temps et la sélection et le réglage d'un algorithme de recherche. Le cadre général des algorithmes"anytime"ne précise pas non plus comment formaliser ce lien. La présente invention a pour objet un procédé d'aide à la conception d'algorithmes d'optimisation prenant en compte une limite de temps qui fournisse un cadre pour exprimer plus facilement un algorithme de recherche et son contrôle temporel, en particulier en mode contractuel, ce procédé pouvant étendre le cadre de la programmation par contraintes, et permettant de traiter plus efficacement des problèmes avec une limite temporelle. Le procédé conforme à l'invention comporte les fonctions suivantes : - un modèle définissant le problème à traiter, - des heuristiques pour guider les choix de construction d'un arbre de recherche, - une librairie de primitives de recherche pour décrire comment construire un arbre de recherche a priori complet, - une librairie de primitives décrivant des limites d'exploration de l'arbre réglables et faisant apparaître les réglages pertinents, ces réglages pouvant être avantageusement obtenus par apprentissage, - une librairie de primitives décrivant divers enchaînements temporels de recherches partielles telles que figurant dans la librairie de primitives de recherche précitée et décrivant la façon de régler les paramètres de chaque recherche. Selon un aspect de l'invention, les réglages des limites consistent à indiquer les branches à explorer préférentiellement dans l'arbre de recherche. Selon un autre aspect de l'invention, les réglages des limites se font selon l'un des trois modes suivants : figé, progressif et adaptatif. Ainsi, selon l'invention, la prise en compte de la limite temporelle dans un algorithme se fait au travers du réglage de paramètres dimensionnant la complexité de sa recherche La présente invention sera mieux comprise à la lecture de la description détaillée d'un mode de mise en oeuvre, pris à titre d'exemple non limitatif et illustré par le dessin annexé, sur lequel : - La figure 1 est un diagramme illustrant les principales fonctions mises en oeuvre par l'invention et leurs relations mutuelles, - Les figures 2 à 4 sont des diagrammes illustrant les principales fonctions mises en oeuvre par des procédés de l'art antérieur, et - La figure 5 est un diagramme illustrant la succession d'étapes mises en oeuvre par le procédé de l'invention. On va décrire en référence à la figure 1 les différentes fonctions mises en oeuvre par le processus d'aide à la conception d'algorithmes selon l'invention. Ces différentes fonctions sont : . Un modèle 1. Il contient la définition du problème à traiter sous la forme d'un ensemble de variables et de contraintes. . Un ensemble 2 d'heuristiques. C'est un ensemble extensible de fonctions prédéfinies pour ordonner les choix dans la construction d'une solution. Par exemple, des heuristiques pour guider le choix des valeurs. Un ensemble de primitives permet de créer de nouvelles heuristiques à partir d'heuristiques existantes. Par exemple, l'inversion de l'ordre d'une heuristique ou bien la combinaison de deux heuristiques : en cas d'égalité sur la comparaison de deux choix par la première heuristique alors comparaison suivant la deuxième heuristique. Le lien entre modèle et heuristiques correspond à l'examen par les heuristiques de l'état des domaines courants des variables et de la structure du réseau de contraintes de manière à évaluer un choix. Un schéma de recherche 3 (SR). Il donne une représentation structurée de l'espace de recherche. Dans le cas des recherches globales, il décrit la façon de construire l'arbre de décisions, indépendamment de toute contrainte temporelle (arbre a priori complet). Les heuristiques sont utilisées pour paramétrer cette construction. Les primitives associées à ce composant concernent la description des points de choix (les noeuds de l'arbre), la combinaison de points de choix et la fonction de minimisation/maximisation, par exemple une fonction de coût/profit. Un exemple de point de choix est l'énumération des valeurs pour une variable. Un exemple de combinaison de deux points de choix, A et B, est l'enchaînement : à chaque feuille de A, la recherche continue sur B. Le langage OPL [voir la référence NO 7 ] possède un ensemble de telles primitives. Le lien entre modèle et schéma de recherche permet une construction dynamique de l'arbre, en fonction de l'état courant du modèle. . Une stratégie d'exploration 4 (SE). Elle spécifie des paramètres contrôlant la complexité de la recherche. Dans le cas des recherches partielles, ces paramètres précisent quelle partie de l'arbre est à explorer. La SE applique donc un certain nombre de limites sur un SR. Par exemple, une limite sur le facteur de branchement, appliquée à des noeuds de l'arbre. Certaines références [voir par exemple les références N 4 et No 9] proposent un ensemble de primitives exprimant ces limites. Une phase d'apprentissage préalable est nécessaire pour déterminer les valeurs des paramètres qui sont pertinentes. La liste des valeurs pertinentes, triée par complexité croissante, est appelée politique de réglage des paramètres . Une stratégie temporelle 5 (ST). Elle décrit la composition de SEs comme moyen d'expression du contrôle temporel. Une composition est une séquence de SEs, un entrelacement de SEs ou une combinaison des deux. Cette composition permet d'exprimer la plupart des méthodes hybrides : Shuffling [voir la référence NO 2], Hybridations par coopération [voir les références ? 5 et ? 10], Interleaved Depth-First Search [voir la référence NO 11], etc. Il faut toutefois noter que dans ce dernier exemple, il ne s'agit pas d'un algorithme hybride. Il exploite une idée propre aux recherches locales, qui est de diversifier la recherche en répartissant les efforts de calcul sur plusieurs sous-recherches effectuées de manière quasi-simultanée par un processus d'entrelacement. Chaque SE contribue à améliorer la qualité de la solution. Les solutions sont partagées parmi les SEs au travers d'un historique des solutions . Une politique de répartition temporelle vient enrichir une composition en indiquant comment répartir une limite de temps aux SEs de la composition [voir la référence NO 5]. Par exemple, une répartition équitable du temps entre les SEs d'une séquence. Ainsi chaque SE aura sa propre limite temporelle lui permettant de contrôler son exploration. La ST précise également le mode de réglage des paramètres de chaque SE : réglage figé, progressif ou adaptatif [voir la référence NO 4]. Des requêtes 6. Venant de l'extérieur du système, les requêtes demandent le traitement sous contrainte de temps d'un problème combinatoire. Concrètement, les requêtes envisagées (associées à une primitive) sont celles des systèmes en-ligne : > Démarrer une recherche avec ou sans limite temporelle. > Suspendre, continuer ou arrêter une recherche. > Elargir ou réduire la limite temporelle d'une recherche. > Donner des informations sur l'état d'avancement de la recherche. Un contrôle temporel 7 (CT). Le type de requête impose le mode de contrôle temporel (contractuel ou interruptible). Le mode interruptible est simulé par une succession d'activations du mode contractuel avec une limite de temps croissant. En fonction de la limite temporelle et d'une analyse du modèle, le CT sélectionne une ST parmi une liste de STs disponibles. Les règles de sélection sont déterminées par une phase d'apprentissage préalable. Le CT dispose d'outils estimant le temps pour effectuer une recherche, la qualité d'une solution (distance à l'optimum) et l'évolution de la qualité des solutions ( profils de performance ). Ces outils donnent des informations d'état d'avancement pour un utilisateur du système. Ils sont également utilisés pour le réglage adaptatif des paramètres d'une SE. Ils pourraient aussi servir dans le cas du mode autonome du contrôle temporel. C'est également le contrôle temporel qui reçoit et prend en compte les requêtes pendant la recherche [Voir la référence No 5]. Il faut noter que chaque composant possède un ensemble de primitives facilitant l'expression d'un algorithme de recherche prenant en compte une limite temporelle. Les composants ST et SE permettent de faire le lien entre une limite temporelle et le réglage d'un algorithme de recherche. Ces caractéristiques sont des caractéristiques importantes de l'invention (voir figure 5, décrite ci-dessous). La figure 2 montre l'architecture générale d'un système d'optimisation en-ligne. Elle distingue essentiellement deux choses. D'une part le moteur de recherche 8 qui résout effectivement le problème courant, d'autre part le module décisionnel 9 qui pilote la recherche et qui reçoit des requêtes extérieures 10. Le module décisionnel commande, (commandes telles que : lancer une recherche, l'interrompre, modifier les paramètres, interroger le moteur de recherche), le moteur de recherche fournit en retour des résultats (solutions, profil courant, statistiques,...) [voir la référence NO 5]. Cette architecture ne précise pas la façon de contrôler la recherche, ni comment exprimer ce contrôle. La figure 3 montre l'architecture utilisée par la référence NO 3. Cette architecture comprend : un modèle 11, un schéma d'hybridation 12, un processus d'apprentissage 13 et des données d'entrée 14 qui incluent une limite temporelle fixée et un jeu d'instances pour ne traiter que le problème classique de tournées de véhicules (des camions de livraison par exemple), dits VRP en anglais. Dans cette architecture, le contrôle temporel est statique. Il s'agit de générer un algorithme qui soit performant en moyenne pour un jeu d'instances représentatives du problème à traiter et pour une limite temporelle fixée. Cette architecture est très spécifique pour les raisons suivantes : une seule classe de problèmes est abordée (problème classique de tournées de véhicules), le type de requête est très limité (limite temporelle unique) et le contrôle temporel de l'algorithme est indépendant de l'instance en cours. La figure 4 montre l'architecture du langage OPL [voir les références N 7 et No 13]. Le composant 15 Il OPLScript" permet de réaliser une séquence de recherches portant sur des modèles 16 éventuellement différents. Les recherches sont décrites par un schéma de recherche 17 et une stratégie d'exploration 18. OPL ne dispose d'aucun outil ou primitive prenant en compte une limite temporelle explicitement, à l'exception de la primitive 19 "lIcTimeLimit" qui n'a aucun effet sur le réglage de la recherche. C'est pourquoi ce composant se différencie clairement du composant ST de la présente invention. Le composant 18 est différent du composant SE de la présente invention car ce composant 18 offre en plus la possibilité de définir un ordre de parcours des noeuds de l'arbre. Par contre, il ne fait pas l'hypothèse d'un paramétrage explicite de la complexité de la recherche (absence de"politique de réglage des paramètres"). On a représenté en figure 5 un chronogramme montrant comment coopèrent entre elles les différentes fonctions représentées en figure 1. L'environnement extérieur fixe une limite temporelle t pour la recherche. Le cas échéant, cette limite temporelle peut être modifiée en cours de recherche. Le processus de recherche étant lancé, avec cette limite temporelle, en 20, il y a une sélection d'une stratégie temporelle ST, qui, en faisant appel à des règles de sélection 21, choisit une ST parmi une collection 22 de STs. En 23, la limite temporelle t est répartie (t, à tn) aux diverses stratégies d'exploration SE de la ST sélectionnée en fonction de sa "politique de répartition"24 associée. Le mode de réglage des SEs et l'enchaînement des SEs sont également imposés par la ST sélectionnée. Il s'ensuit, en 25, le réglage des limites des n différentes SEs (SE1 à SEn) en fonction des"politiques de réglage"associées à chaque SE particulière (SEI) 26, du mode de réglage imposé par la ST et du temps alloué (t,). Les différentes SEs étant réglées, les limites d'exploration correspondantes déterminent chacune un parcours partiel de SR (en 27), en s'appuyant sur les heuristiques 28 et le modèle 29. L'exécution des différents parcours partiels se fait en séquence (primitive"seq") ou en entrelacé (primitive"int"). Ceci est contrôlé en 23, suivant la ST sélectionnée. Il en résulte (en 30) la production d'une ou de plusieurs solutions, ou même d'aucune si le temps de calcul est insuffisant ou si le problème n'est pas soluble. On notera que les données des éléments 21,22, 24,26 et 28 sont obtenues par apprentissage non décrit par l'invention. En conclusion, la présente invention permet de : Offrir un cadre pour exprimer des algorithmes de recherche prenant en compte une limite temporelle. Ce cadre doit faciliter la lecture et la maintenance de tels algorithmes. Proposer une architecture modulaire pour spécifier de tels algorithmes, avec la possibilité de réutiliser des parties d'algorithme issues des différents composants, favorisant ainsi la capitalisation. Prendre en compte la limite temporelle dynamiquement pour avoir une bonne adéquation de l'algorithme au temps imparti et à l'instance et profiter éventuellement des évolutions des plates-formes matérielles. Étendre le domaine d'application de la programmation par contraintes aux problèmes en-ligne. Références 1.-Aarts & Korst1989 E. Aarts, J. Korst. Simulated Annealing and Boltzmann Machines : a Stochastic Approach to Combinatorial Optimization and Neural Network. John Wiley & Sons, 1989. 2.-Applegate & Cook1991 D. Applegate, W. Cook. A computational study of the job-shop scheduling problem. ORSA Journal On Computing, 3 (2) : 149--156,1991. 3.-Caseau efa/. 1999 Y. Caseau, F. Laburthe, G. Silverstein. A Meta-Heuristic Factory for Vehicle Routing Problems (Meta-Programming for Meta-Heuristics). In Proc. of CP-99, pages 144-158, Alexandria, Virginia, 1999. 4.-Givry efa/. 1999 Simon de Givry, Pierre Savéant, Jean Jourdan. Optimisation combinatoire en temps limité : Depth first branch and bound adaptatif. In Proc. ofJFPLC-99, pages 161-178, Lyon, France, 1999. S.-Givry ef a/. 2000 S. de Givry, Y. Hamadi, J. Jourdan, J. Mattioli, M. Lemaître, G. Verfaillie, A. Aggoun, 1. Gouachi, T. Benoist, E. Bourreau, F. X. Josset, F. Laburthe, B. Rottembourg, P. Boizumault, P. David, R. Debruyne, N. Jussien, S. Loudni, S. Bourgault, M. Lauvergne. Environnement d'optimisation en ligne dédié télécom. Technical report, Thales, ONERA, Cosystec, Bouygues, Ecole des Mines de Nantes et France Télécom, Novembre 2000. Rapport sous-projet 1. 6.-Harvey & Ginsberg1995 William D. Harvey, Matthew L. Ginsberg. Limited discrepancy search. ln Proc. ofIJCAI-95, pages 607-613, Montréal, Canada, 1995. 7.-Hentenryck1999 P. Van Hentenryck. OPL : The Optimization Programming Language. The MIT Press, Cambridge, Mass., 1999. 8.-Korf1990 Richard E. Korf. Real-time heuristic search. Artificial Intelligence, 42 : 189-211,1990. 9.-Laburthe1998 François Laburthe. SaLSA : a language for search algorithms. In Proc. of CP-98, pages 310-324, Pisa, Italy, October 26-30 1998. 10.-Lobjois & Lemaître1997 L. Lobjois, M. Lemaître. Coopération entre méthodes complètes et incomplètes pour la résolution de (V) CSP : une tentative d'inventaire. In Proc. of JNPC-97, pages 67-73, Rennes, France, 1997. 11.-Meseguer1997 Meseguer, P. (1997). Interleave depth-first search. In Proc. of IJCAI-97, Nagoya, Japan, pp. 1382-1387. 12. -Musliner et al. 1995 David J. Musliner, James A. Hendler, Ashok K. Agrawala, Edmund H. Durfee, Jay K. Strosnider, C. J. Paul. The challenges of real-time AI. IEEE Computer, 28 (1) : 58-66, January 1995. 13.-Perron1999 L. Perron. Search Procedures and Parallelism in Constraint Programming. In Proc. of CP-99, pages 346-360, Alexandria, Virginia, 1999. 14. -Russell & Zilberstein1991 S. J. Russell, S. Zilberstein. Composing real-time systems. In Proc. oflJCAI-91, pages 212-217, Sidney, Australia, 1991. 15.-Zilberstein1993 Shlomo Zilberstein. Operational Rationality through Compilation of Anytime Algorithms. PhD thesis, University of California, Berkeley, 1993. 16.-Zilberstein1996 Shlomo Zilberstein. Using Anytime Algorithms in Intelligent Systems. AI Magazine, 17 (3) : 73-83,1996. REVENDICATIONS 1. Procédé d'aide à la conception d'algorithmes d'optimisation prenant en compte une limite de temps, caractérisé en ce qu'il met en oeuvre les fonctions suivantes : - un modèle définissant le problème à traiter (1,29), - des heuristiques pour guider les choix de construction d'un arbre de recherche (2,28), - une librairie de primitives de recherche pour décrire comment construire un arbre de recherche a priori complet (3,27), - une librairie de primitives décrivant des limites d'exploration de l'arbre réglables et faisant apparaître les réglages pertinents, - une librairie de primitives décrivant divers enchaînements temporels de recherches partielles telles que figurant dans la librairie de primitives de recherche précitée et décrivant la façon de régler les paramètres de chaque recherche (5,23, 24). 2. Procédé selon la revendication 1, caractérisé en ce que les réglages des limites consistent à indiquer les branches à explorer préférentiellement dans l'arbre de recherche. 3. Procédé selon la revendication 1 ou 2, caractérisé en ce que les recherches se font selon l'un des trois modes suivants : figé, progressif ou adaptatif. 4. Procédé selon l'une des revendications précédentes, caractérisé en ce que la prise en compte de la limite temporelle dans un algorithme se fait au travers du réglage de paramètres dimensionnant la complexité de sa recherche. 5. Procédé selon l'une des revendications précédentes, caractérisé par le fait que la sélection d'une stratégie temporelle (20) fait appel à des règles de sélection (21) et choisit une stratégie parmi une collection (22) de stratégies temporelles. 6. Procédé selon la revendication 5, caractérisé par le fait qu'une politique de répartition (24) associée à une stratégie temporelle sélectionnée (23) répartit la limite temporelle aux diverses stratégies d'exploration de la stratégie temporelle sélectionnée. 7. Procédé selon la revendication 5 ou 6, caractérisé par le fait que la stratégie temporelle sélectionnée compose le mode de réglage des stratégies d'exploration et leur enchaînement. 8. Procédé selon l'une des revendications 5 à 7, caractérisé par le fait que des politiques de réglage (26) associées à chaque stratégie d'exploration assurent le réglage des limites des différentes stratégies d'exploration (25). 9. Procédé selon la revendication 8, caractérisé par le fait que, les différentes stratégies d'exploration étant réglées, les limites d'exploration correspondantes déterminent chacune un parcours partiel d'une stratégie de recherche (27) en s'appuyant sur les heuristiques (28) et le modèle (29). 10. Procédé selon la revendication 8 ou 9, caractérisé en ce que les données des règles de sélection (21), des stratégies temporelles (22), de la politique de répartition (24), des politiques de réglage (26) associées à chaque stratégie d'exploration, et des heuristiques (28) sont obtenues par apprentissage et expérimentations.