Au confluent de l'algorithmique et de la modélisation
Un problème à un million de dollars : trouver une solution est-il aussi facile que la vérifier ? Écrit sous la forme « P = NP ? », ce problème est pour l'instant toujours ouvert. Ainsi, montrer qu'un emploi du temps vérifie les contraintes imposées est facile, mais en trouver un qui convienne ? S'il faut les énumérer un par un pour les tester, on risque d'y passer un temps plus long que l'âge du soleil, alors qu'on aimerait avoir la solution dans les cinq minutes ou les vingt-quatre heures. On cherche d'abord à identifier les problèmes que l'on sait résoudre rapidement. Pour les autres, on utilisera si possible des recherches arborescentes intelligentes, des algorithmes exacts efficaces de type cheminement combinatoire, ou des méthodes approchées (métaheuristiques).
Tous les articles de ce dossier
PodcastProgrammation linéaire en nombres entiers | Tangente
Pour résoudre des problèmes d'optimisation, il peut être nécessaire de les mettre en équation dans des modèles mathématiques. La programmation linéaire en nombres entiers permet de le faire en utilisant uniquement des polynômes du premier degré, dont les variables doivent prendre des valeurs entières.
PodcastP est-il égal à NP ?
La question tient en haleine la communauté scientifique depuis plus de quarante ans maintenant. Elle fait partie des « problèmes du millénaire », cette liste de sept énigmes mathématiques majeures posées par l'Institut de mathématiques Clay en 2000. Éclairage.
PodcastLes métaheuristiques : optimisation approchée | Tangente
Problèmes NP-difficiles, explosion combinatoire, modélisation comprenant des millions de variables et un nombre d'inéquations exponentiel… Que faire quand aucune méthode d'optimisation ne fonctionne ? Quelle méthode utiliser lorsque l'on souhaite obtenir une solution rapidement à un problème ?
PodcastCheminement combinatoire : les plus courts chemins | Tangente
Quand on décide de son chemin au fur et à mesure du trajet, on doit, comme dans un labyrinthe, choisir entre plusieurs voies. Et la question se repose à chaque nouvel embranchement, créant ainsi une explosion combinatoire des chemins possibles. Comment contourner cette explosion ?
PodcastRecherche arborescente
Optimiser l'usage d'un télescope pour savoir quelle partie du ciel observer est fondamental. Un tel défi, qui peut se ramener à un problème de coloration, demande des essais que même un ordinateur moderne n'a pas le temps de rendre exhaustifs.