Comment passer pour un vieux c... en quelques secondes
Par David Monniaux le lundi, octobre 22 2012, 14:04 - Enseignement - Lien permanent
(Contexte : une « petite classe » sur le voyageur de commerce dans un cours de logique, calculabilité et complexité.)
un étudiant : Que pensez-vous du recuit simulé pour résoudre le voyageur de commerce ?
moi : Je ne sais pas, la dernière fois que j'ai programmé ça c'était en 1995.
l'étudiant : J'avais 5 ans !
Commentaires
Les problemes de voyageurs de commerce se resolvent aujourd'hui avec des heuristiques dites de Kernighan-Lin qui partent d'une solution preexistante et font des ameliorations locales en calculant de maniere exhaustive un voisinage dit k-opt (calculer tous les echanges de 2 arcs par exemple). On sait caracteriser la composante connexe des solutions ainsi obtenues. Quand on arrive au minimum local, on fait un mouvement dit "bridge" dont on peut prouver qu'il sort la solution de la composante connexe, puis on continue les k-opt. Le calcul de la solution initiale est tres probleme dependant (TSP symmetrique ou pas, VLSI, etc). Apres si on veut on peut mettre le probleme dans un moteur de programmation lineaire en nombres entiers avec generation de coupes "cycle-cut" (plus generalement, generation de contraintes a la volee) et un peu plus avance du branch-cut-and-price qui est de la generation combinee de variables et contraintes a la volee, autrement dit on permet au voyageur seulement d'aller d'un noeud a d'autres noeuds proches, puis on ajoute des arcs potentiels (= variables) a la volee dans le programme lineaire. Tu trouveras de l'information sur les methodes lineaires dans http://www.tsp.gatech.edu/
L'idee des voisinages polynomiaux "k-opt" + mouvement hors de la classe de connexite "bridge" est generalisable a de nombreux problemes mais s'il faut coder l'algorithmique sous-jacente au cas par cas. C'est cela que l'on appelle en fait les methodes a la Kernighan-Lin.
Il existe des moteurs de recherche locale qui generent les mouvement / voisinages automatiquement a partir d'une formulation equationelle donc t'evitant de devoir ecrire toute algorithmique probleme dependante par exemple http://www.localsolver.com/ En revanche j'ignore s'ils arrivent a automatiquement "retrouver" Kernighan-Lin.
Par contre, le recuit simule, pour le TSP c'est nul. De maniere generale les methodes qui exploitent la structure d'un probleme mettent la raclee aux methodes generiques.
Puisque la motivation initiale du billet était l'age du capitaine, je précise que Kernighan-Lin date des années 70 donc si en 1995 tu utilisais encore du recuit simulé, tu étais déjà dépassé.
Aussi tu peux rajouter une question a ton devoir du genre "proposer un algorithme itératif pour le TSP utilisant les contraintes de coupe-cycle mais sans les poser toutes".
On resout le TSP sans les contraintes de cycle, si la solution n'a pas de cycle on a fini (TSP optimal), sinon on rajoute un coupe-cycle juste pour couper le cycle solution et on recalcule la solution optimale.
Les moteurs MILP actuels (ex. Gurobi) savent optimiser une séquence de problèmes emboités en redémarrant "a chaud" donc cet algorithme est moins mauvais qu'on ne pourrait le penser : on ne résout pas M problèmes NP-difficiles (ou M est le nombre d’itérations) mais un problème un peu augmenté.
Exercice plus difficile (pour toi) : tu viens de résoudre un problème NP avec un branch-and-bound et tu as l'arbre de recherche complet en mémoire. On ajoute une contrainte au problème. Quelles nœuds de l'arbre de recherche faut-il recalculer ? Même question quand on ajoute une variable au problème et non plus une contrainte.
@Couard: En 1995, j'ai implémenté le recuit simulé pour le TSP parce que j'étais étudiant et que c'était ce que l'on m'avait demandé.
Quant au TSP avec contraintes de cycle intelligentes, on a un énoncé là dessus rédigé par Leo Liberti... mais de toute façon on n'a déjà pas le temps de faire toute la feuille actuelle...
Les méthodes « je rajoute les contraintes au fur et à mesure que je les viole », je connais aussi (un peu) ; évidemment ça suppose un outil incrémental. C'est d'ailleurs un peu l'idée de cet article.
Un jour il va falloir qu'on mette en commun les connaissances des communautés d'optimisation combinatoire / linéaire, de SAT / SMT / démonstration automatique et d'analyse syntaxique de langages NP (automates à pile avec unification, Prolog, grammaires attribuées / catégorielles / de propriété).
Je suis certain qu'on fait plein de découvertes dupliquées sans le savoir.
Ce serait bien d'avoir un Master spécialisé.
@Couard: Et pourquoi pas un wiki d'informatique théorique ? Mais cela existe sans doute déjà.
Pour moi "informatique théorique" est une insulte doublée d'un oxymore...
Mon sentiment est qu'il est essentiel de bien connaitre les 3 variantes des méthodes de résolution effective de problèmes NP-difficiles (logique, numérique, symbolique), du moins si l'on décide de se travailler dans l'une d'entre elles.
Le problème est a mon sens moins une absence d'information (les livres sont la, les articles aussi) qu'un manque de direction. Ce que j'aimerais c'est éviter aux autres de découvrir par hasard le lien entre ces domaines.
Dans mon cas précis le hasard s'appelle Caml, le fait qu'a un moment c’était a la mode même en optimisation combinatoire (FaCiLe), le fait qu'il n'y ait que peu de livres utilisant Caml dont un de Harrison sur la démonstration automatique de théorèmes, le fait qu'un ancien SMLer soit parti chez Microsoft et ait écrit un SMT en Caml, le fait qu'un peu avant l’interprétation abstraite était le sujet a la mode en Caml (encore avant c’était les compilateurs optimisants, maintenant ce sont les compilateurs formalisés), le fait qu'il y ait eu une mode de parseurs complexes (GLR, backtrackants) en programmation fonctionnelle car cela s'y prête bien et on en a besoin pour les compilateurs, le fait qu'en creusant un peu du cote des parseurs complexes on retombe sur des problèmes combinatoires et logiques (unification, automates d'arbres, systèmes d’équations de mots). Enfin le fait que je connais tout un tas de personnes qui travaillent avec Caml et qu'il est de bon ton de jeter un coup d’œil a ce qu'il font pour pouvoir papoter 5 minutes devant la machine a café.
Mais fondamentalement, si Caml n'avait pas été poussé dans l'enseignement et la recherche en France je n'aurais jamais mis le nez hors de mon code C/C++ et mes équations - comme nombre de mes collègues.
D'ailleurs c'est aussi parce que la densité d'information y est plus élevée qu'il est important d'enseigner Caml (plutôt que C, C++, C# ou Java que l'on peut apprendre seul avec un bouquin passe-partout). C'est comme naguère le Scheme au MIT.