Je cherche une liste de problèmes d'optimisation NP-hard, où il y a une recherche active en heuristique pratique pour les résoudre et il y a des repères communs, que les gens essaient de battre.
Exemples: reconstruction d'arbres phylogénétiques (heuristique par exemple ici ) Vendeur itinérant (pas si actif, mais LKH est assez bien connu)
Plus précisément, je recherche des domaines de recherche, où les gens se soucient vraiment du coût résultant (comme le TSP ou la phylogénie mentionnés ci-dessus). Par exemple, trouver un arbre de décision n'est pas une chose que je recherche, car très peu de gens se soucient de la hauteur de l'arbre résultant.
heuristics
usamec
la source
la source
Réponses:
MaxSAT - les gens se soucient vraiment de cela parce que les solveurs SAT sont si bien développés que souvent la meilleure voie pour votre problème d'optimisation NP préféré dans la pratique est de le réduire à MaxSAT, puis d'appliquer l'un des solveurs bien connus. Découvrez le concours SAT pour les repères, etc.
Les chercheurs de cliques s'utilisent en biologie computationnelle et en combinatoire, et les algorithmes heuristiques sont scandaleusement bons, si je me souviens bien.
De vastes portions d'Operations Research sont consacrées aux algorithmes, y compris les algorithmes heuristiques, pour résoudre les cas de programmation linéaire en nombres entiers ou mixtes.
la source
La recherche opérationnelle présente de nombreux problèmes d'optimisation combinatoire où le développement d'heuristiques pour la minimisation (ou la maximisation) des coûts résultants est un domaine très actif.
Par exemple, un problème de routage de véhicule, un problème de routage d'arc capacitif, des problèmes de spanning tree minimum et des variations de ces problèmes.
la source