Lista problemów trudnych dla NP, w których prowadzone są aktywne badania w zakresie praktycznej heurystyki

9

Szukam listy problemów związanych z optymalizacją trudnych NP, gdzie są aktywne badania w praktycznej heurystyce w celu ich rozwiązania i istnieją wspólne testy porównawcze, które ludzie próbują pokonać.

Przykłady obejmują: rekonstrukcja drzewa filogenetycznego (heurystyczny na przykład tutaj ) komiwojażera (nie tak aktywny, ale LKH jest dość dobrze znana)

Mówiąc dokładniej, szukam obszarów badań, w których ludzie naprawdę dbają o związane z tym koszty (takie jak TSP lub filogeneza wspomniane powyżej). Np. Znalezienie drzewa decyzyjnego nie jest rzeczą, której szukam, ponieważ bardzo niewiele osób dba o wynikową wysokość drzewa.

usamec
źródło
1
Ta lista jest za długa, co sprawia, że ​​pytanie to jest zbyt szerokie. Jeśli chcesz mieć tak szeroką listę, proponuję sprawdzić kompendium problemów NP-zupełnych: nada.kth.se/~viggo/problemlist/compendium.html
Kaveh
Ta lista jest ładna, ale koncentruje się głównie na przybliżeniu. Chcę listę skupiającą się na praktycznej heurystyce.
usamec
Czy sprawdziłeś, że ma algorytmy heurystyczne, którymi jesteś zainteresowany? Myślę, że są raczej otwarci na różne algorytmy. (Zgaduję, że wiesz, co oznacza heurystyka w kontekście informatyki teoretycznej, a nie tylko odnosząc się do rzeczy, które po prostu wydają się działać, jeśli nie, zobacz centrum pomocy .) W każdym razie nierozstrzygnięte pytania zwykle nie są dobre , jeśli nie jesteś zadowolony z tej listy, powinieneś dokładniej określić, dlaczego jesteś zainteresowany, i zawęzić zakres pytania.
Kaveh
5
To rozsądne pytanie. Być może PO może wyjaśnić więcej. Czy chodzi o problemy, dla których heurystyka jest wykorzystywana w praktyce, czy chodzi o problemy, dla których aktywnie prowadzone są badania akademickie w heurystyce?
Chandra Chekuri
6
Jedną szeroką klasą problemów jest grupowanie. Heurystyka k-średnich, k-median i powiązanych problemów jest dość aktywnym obszarem badań. Również metryki i powiązane problemy z wnioskami graficznymi.
Chandra Chekuri

Odpowiedzi:

5

MaxSAT - ludzie tak naprawdę dbają o to, ponieważ solwery SAT są tak dobrze rozwinięte, że często najlepszą drogą do twojego ulubionego problemu optymalizacji NP jest w praktyce zmniejszenie go do MaxSAT, a następnie zastosowanie jednego z dobrze znanych solverów. Sprawdź konkurs SAT na testy porównawcze itp.

Wyszukiwarki klików są wykorzystywane w biologii obliczeniowej i kombinatorykach, a algorytmy heurystyczne są szokująco dobre, o ile pamiętam.

Ogromne części badań operacyjnych są poświęcone algorytmom, w tym heurystycznym, do rozwiązywania przypadków programowania liniowego liczb całkowitych lub mieszanych.

Joshua Grochow
źródło
Dzięki. Czy masz jakieś linki do faktycznych dokumentów i zestawów danych porównawczych?
usamec
1

Badania operacyjne wiążą się z wieloma kombinatorycznymi problemami optymalizacji, w których rozwój heurystyki w celu minimalizacji (lub maksymalizacji) kosztów wynikowych jest bardzo aktywny.

Na przykład problem z trasowaniem pojazdu, problem z trasowaniem łuku pojemnościowego, problemy z minimalnym drzewem opinającym i odmiany tych problemów.

użytkownik2307639
źródło
Czy możesz podać kilka punktów odniesienia?
usamec
Czy możesz podać jakieś odpowiednie wskazówki?
Yuval Filmus,
1
Możesz przeglądać czasopisma, takie jak programowanie matematyczne, badania operacyjne, sieci, nauki o zarządzaniu itp., Aby znaleźć wiele artykułów na temat heurystyki dotyczących problemów optymalizacji kombinatorycznej.
Chandra Chekuri
1
Przykładem jest CARP: logistik.bwl.uni-mainz.de/benchmarks.php
user2307639,