Retour sur trace et séparation et évaluation

Le retour sur trace et la séparation et évaluation sont des paradigmes de recherche systématique qui explorent l'espace des solutions candidates sous forme d'arbre, élaguant les sous-arbres qui ne peuvent pas mener à une solution valide ou optimale afin de rendre les recherches, autrement exponentielles, traitables en pratique.

Definition

Le retour sur trace est une recherche en profondeur de l'arbre des solutions candidates partielles qui élague une branche dès l'instant où le candidat partiel ne peut être complété en une solution valide ; la séparation et évaluation complète cela avec des bornes numériques sur l'objectif, de sorte que les branches dont la meilleure valeur possible ne peut surpasser la solution courante (incumbent) sont écartées.

Scope

Ce sujet aborde les techniques de recherche exhaustive organisées autour d'un arbre de recherche : le retour sur trace, qui abandonne les candidats partiels dès qu'ils violent une contrainte, et la séparation et évaluation, qui utilise des bornes sur le meilleur objectif réalisable pour élaguer les sous-arbres en optimisation. Il inclut des exemples de satisfaction de contraintes (problème des N-dames, coloration de graphes, Sudoku) et des exemples d'optimisation combinatoire (problème du voyageur de commerce, programmation en nombres entiers), et discute de la raison pour laquelle ces méthodes restent précieuses pour les problèmes NP-difficiles malgré un coût exponentiel dans le pire des cas.

Core questions

• Comment l'espace des solutions d'un problème est-il modélisé comme un arbre de recherche d'affectations partielles ?
• Quelles vérifications de contraintes permettent au retour sur trace d'élaguer prématurément les branches infaisables ?
• Comment les bornes inférieures et supérieures sont-elles calculées pour élaguer les branches en optimisation ?
• Comment l'ordre de branchement et d'évaluation (bounding) affecte-t-il les performances pratiques ?
• Pourquoi ces méthodes sont-elles utilisées pour les problèmes NP-difficiles malgré des cas exponentiels dans le pire des cas ?

Key concepts

• arbre de recherche
• exploration en profondeur
• propagation de contraintes
• élagage
• fonctions de bornage
• solution courante
• problème des N-dames
• relaxation de la programmation en nombres entiers

Key theories

Élagage de l'arbre de recherche

Les deux paradigmes organisent les solutions candidates sous forme d'un arbre exploré en profondeur ; la correction provient de l'exhaustivité, tandis que l'efficacité résulte de l'élagage des sous-arbres qui ne peuvent manifestement pas contenir une solution valide ou améliorante.

Fonctions de bornage dans la séparation et évaluation

La séparation et évaluation maintient la meilleure solution trouvée jusqu'à présent et une borne (par exemple, une relaxation PL) sur la meilleure valeur atteignable dans chaque sous-arbre ; un sous-arbre est écarté lorsque sa borne ne peut pas améliorer la solution courante.

Clinical relevance

La séparation et évaluation est la pierre angulaire de l'optimisation combinatoire exacte en recherche opérationnelle, incluant les solveurs de programmation en nombres entiers et en nombres entiers mixtes utilisés pour l'ordonnancement, le routage et la planification. Le retour sur trace est à la base des solveurs de contraintes, de la recherche de type SAT, des solveurs de puzzles et des analyseurs syntaxiques (parsers), où la recherche systématique avec élagage est la voie pratique vers des réponses exactes.

History

Le retour sur trace a été systématisé en tant que technique générale dans les années 1950 et 1960, notamment décrit par Golomb et Baumert. La séparation et évaluation a été introduite par Ailsa Land et Alison Doig en 1960 pour la programmation linéaire en nombres entiers et est depuis devenue centrale dans l'optimisation combinatoire, alimentant les solveurs modernes de programmation en nombres entiers mixtes.

Key figures

• Ailsa Land
• Alison Doig
• Solomon Golomb
• Robert Bixby

Seminal works

• landdoig1960
• cormen2009

Frequently asked questions

Quelle est la différence entre le retour sur trace et la séparation et évaluation ?

Le retour sur trace est généralement utilisé pour les problèmes de faisabilité et de satisfaction de contraintes et élague les branches qui violent les contraintes. La séparation et évaluation vise l'optimisation et élague en outre en utilisant des bornes numériques, écartant tout sous-arbre dont le meilleur objectif possible ne peut surpasser la meilleure solution déjà trouvée.

Si ces méthodes sont exponentielles dans le pire des cas, pourquoi les utiliser ?

Pour les problèmes NP-difficiles, aucun algorithme exact polynomial n'est connu, mais un élagage efficace élimine souvent la grande majorité de l'arbre de recherche sur des instances réelles, de sorte que les solveurs de séparation et évaluation et de retour sur trace trouvent régulièrement des solutions optimales de manière avérée bien plus rapidement que ne le suggèrent leurs bornes dans le pire des cas.