Ich suche nach einer Liste von NP-harten Optimierungsproblemen, bei denen es aktive Forschung in der praktischen Heuristik gibt, um sie zu lösen, und es gibt gemeinsame Benchmarks, die die Leute zu schlagen versuchen.
Beispiele sind: Phylogenetische Baumrekonstruktion (zum Beispiel hier heuristisch ) Reisender Verkäufer (nicht so aktiv, aber LKH ist ziemlich bekannt)
Insbesondere suche ich nach Forschungsbereichen, in denen sich die Menschen wirklich um die daraus resultierenden Kosten kümmern (wie TSP oder Phylogenie, die oben erwähnt wurden). Zum Beispiel suche ich keinen Entscheidungsbaum, da nur sehr wenige Menschen sich um die resultierende Baumhöhe kümmern.
heuristics
usamec
quelle
quelle
Antworten:
MaxSAT - Die Leute interessieren sich tatsächlich dafür, weil SAT-Löser so gut entwickelt sind, dass der beste Weg für Ihr bevorzugtes NP-Optimierungsproblem in der Praxis häufig darin besteht, es auf MaxSAT zu reduzieren und dann einen der bekannten Löser anzuwenden. Schauen Sie sich den SAT-Wettbewerb für Benchmarks usw. an.
Clique-Finder werden in der Computerbiologie und Kombinatorik eingesetzt, und die heuristischen Algorithmen sind, wie ich mich erinnere, schockierend gut.
Ein großer Teil von Operations Research befasst sich mit Algorithmen, einschließlich heuristischer, zur Lösung von Fällen der linearen Programmierung mit ganzen oder gemischten ganzen Zahlen.
quelle
Operations Research hat viele kombinatorische Optimierungsprobleme, bei denen die Entwicklung von Heuristiken zur Minimierung (oder Maximierung) der resultierenden Kosten ein sehr aktiver Bereich ist.
Zum Beispiel Fahrzeugroutingproblem, kapazitives Lichtbogenroutingproblem, minimale Spanning Tree-Probleme und Variationen dieser Probleme.
quelle