Une simple heuristique pour rapprocher DFS et LNS pour les COP
Résumé
In this paper, we argue that a combination of wellknown and new search strategies enables Depth First tree Search (DFS) to mimic the behavior of Large Neighborhood Search (LNS), which reduces considerably the gap between the two techniques. In particular, we are able to implement a DFS strategy that shares the scalability properties of LNS, but the optimality of solutions can eventually be proven.
Dans cet article, nous montrons comment une combinaison de stratégies de branchement et de redémarrages pour la recherche en profondeur d’abord (DFS) permet de reproduire le fonctionnement de la recherche par grand voisinage (LNS) pour la résolution de problèmes d’optimisation à contraintes, ce qui permet de rapprocher considérablement les deux techniques. En particulier, nous pouvons implémenter une stratégie DFS qui bénéficie des propriétés de passage à l’échelle de LNS tout en étant capable de prouver l’optimalité des solutions.