IREMInstitut de recherche sur l'enseignement des mathématiques de Grenoble

Les problèmes d'optimisation combinatoire sont étonnamment très présents dans notre univers quotidien. Comment remplir un camion lors d'un déménagement, faire un emploi du temps optimal pour un lycée ou une conférence, trouver le plus court chemin entre deux serveurs reliés par Internet, construire un réseau d'approvisionnement énergétique résistant à un nombre donné de pannes, affecter des fréquences pour les bornes de retransmission des téléphones portables... Or, si certains de ces problèmes semblent faciles à résoudre pour de petits exemples, la plupart sont insolubles lorsque le nombre d'objets à traiter devient grand. Pour essayer d'y voir plus clair, les mathématiciens ont mis au point une théorie dans laquelle sont classifiés les problèmes selon le temps que met le meilleur algorithme à donner une solution. On soupçonne que certains d'entre eux sont excessivement difficiles à résoudre. Par exemple, on ne connaît pas de méthode qui résolve le problème d'affectation de fréquence de façon optimale en un temps inférieur à l'âge de l'univers pour des cas de 100 bornes ! La physique statistique est alors d'un grand secours. On sait maintenant par exemple que les méthodes de simulations que les physiciens ont inventées pour simuler des matériaux ferromagnétiques ou des plasmas peuvent servir à approcher la solution des problèmes de combinatoire. La physique donne aussi des intuitions sur ce qui rend ces problèmes difficiles. Notamment, les phénomènes de transition de phase, comme le passage d'un état extrêmement ordonné à un état très peu structuré chez les matériaux ferromagnétiques sont extrêmement difficiles à obtenir par ces méthodes. Reprenant cette idée, les mathématiciens ont essayé de comprendre si les transitions de phase existent aussi en optimisation combinatoire et commencent maintenant à en trouver. Cette vision des choses pourrait bien être dans l'avenir la clé pour une meilleure classification des problèmes et ouvrent des voix prometteuses dans la compréhension de l'efficacité des algorithmes.