NP kompletne lub NP trudne problemy w prawdziwym życiu

17

Czy ktoś ma przykłady z życia, w których regularnie rozwiązuje NP pełne lub trudne problemy NP (heurystykami, szukając rozwiązania nieoptymalnego lub cokolwiek innego) w swojej pracy? Wiem, że występują one w planowaniu, planowaniu, projektowaniu VLSI itp., Ale staram się zorientować, jakie główne branże zatrudniają dziś programistów lub inżynierów, którzy regularnie to robią. Gdyby ktoś rozwinął wiedzę specjalistyczną lub bibliotekę, powiedzmy, optymalizację kombinatoryczną, to gdzie można to wykorzystać jako część pracy programistycznej?

Jakieś konta osobiste?

wysoka przepustowość
źródło
Co rozumiesz przez „regularnie”
Conrad Frix,
@ Conrad, myślę, że to subiektywny pomysł. Powiedziałbym, że więcej niż 5-10% wysiłku skupia się na rozwiązywaniu problemów np. Kompletnych lub np. Trudnych.
highBandWidth
Uważam, że programowanie AI w grach może być kompletne.
Michael K
Istnieje wiele problemów trudnych dla NP (planowanie i planowanie przy użyciu skończonych zasobów jest zwykle trudne dla NP). Jednak optymalizacja kombinatoryczna jest niewłaściwą drogą. Będąc w stanie wygenerować 100! kombinacje tak szybko, jak to możliwe, są o wiele mniej przydatne niż możliwość zastosowania heurystyki specyficznej dla domeny.
David Thornley,
@ David, nie miałem na myśli generowania kombinacji przez kombinatoryczną optymalizację.
Odniosłem się

Odpowiedzi:

8

Niektóre rzeczy, o których mogę myśleć (większość z nich byłam mniej lub bardziej zaangażowana):

  • Środowiska programistyczne dla języków i kompilatorów. Pytania takie jak: czy ta gramatyka generuje dwuznaczny język? (Ten problem jest w rzeczywistości nierozstrzygalny!)
  • Odzyskiwanie danych. Ponowne składanie częściowo utraconych pakietów danych lub odzyskiwanie pofragmentowanych plików. (Złożoność czynnikowa)
  • Bezpieczeństwo oprogramowania Ocena wszystkich możliwych ścieżek wykonania za pomocą oprogramowania w celu ustalenia, czy można przypisać pewne zaobserwowane zachowanie. (Problem z zatrzymaniem?)
  • Logistyka. Optymalizacja wykorzystania transportów na podstawie pakietów do transportu, ich wielkości i miejsca, do którego muszą się udać. (Przynajmniej wykładniczy)

Istnieje wiele standardowych przykładów, takich jak znalezienie najkrótszej trasy, planowanie pielęgniarki itp., Ale jeśli jesteś zwolennikiem optymalizacji kombinatorycznej, wiesz o nich :)

Deckard
źródło
Czy są więc programiści zatrudnieni przez firmy logistyczne, którzy faktycznie zajmują się rozwiązywaniem tych problemów związanych z optymalizacją, czy też większość z tych operacji jest zazwyczaj rozwiązywana raz i jest powtarzana dla większości firm? +1 za kilka przykładów. Czy jesteś / byłeś zaangażowany w którekolwiek z nich?
highBandWidth
Pierwsze dwa, dla których napisałem narzędzia, trzecie to coś, nad czym pracują koledzy. Spodziewałbym się, że duże firmy logistyczne aktywnie prowadzą badania w tej dziedzinie, ponieważ mogą zaoszczędzić miliony dolarów, jeśli osiągną kilka procent dodatkowej wydajności dzięki nowemu algorytmowi :)
Deckard
Przeprowadziłem wywiad dla roli podróżnego sprzedawcy. Duża firma macierzysta miała pokój pełen doktorów niewolników w nadziei na uzyskanie kilku dziesiątych procent poprawy w ich routingu. Co byłoby dla nich warte kilka milionów dolarów ... każdego dnia. Więc te miejsca istnieją. Trasowanie rzeczy i planowanie to dwie duże - wyobraź sobie, że masz 1000 osób i fabrykę, która działa na dwie lub trzy zmiany. Teraz zaplanuj, aby wszyscy pracowali przez następny miesiąc, pamiętając o tych 200 regułach i preferencjach wszystkich ...
9

Użyłem ograniczonego czasowo symulowanego wyżarzania do rozwiązania problemu wędrownego salemana w produkcji panelu dotykowego. Każda milisekunda, którą moglibyśmy się ogolić od czasu cyklu trawienia laserowego każdego panelu, zwiększałaby przepustowość, wykorzystanie, a tym samym rentowność maszyny, dlatego włożyłem wiele wysiłku w minimalizowanie czasu przestoju (ścieżek nie rysujących) między ścieżkami rysowania (które oczywiście nie można go zoptymalizować).

Użyłem algorytmu czasowego, aby obejść twardość NP problemu, ponieważ nie mogliśmy sobie pozwolić na ryzyko, że obliczenie optymalizacji może potrwać dłużej niż czas zaoszczędzony przez bardziej optymalną ścieżkę. Gdy maszyna przemieszczała panel z położenia ładowania do położenia, w którym głowica lasera znajdowała się za najbliższym rogiem, miałem czas na przeprowadzenie niektórych symulacji. Algorytm prawie nigdy nie dobiegł końca w ciągu kilkuset milisekund ruchu, ale prawie zawsze zwracał lepszą ścieżkę zapisu niż jakikolwiek z prostych, nieadaptacyjnych modeli, których zawsze używaliśmy wcześniej (takich jak ścieżki spiralne lub wężowe).

Mark Booth
źródło
2
To super. Ale myślałem, że każdy panel będzie miał ten sam wzór, a ty po prostu rozwiążesz problem raz na zawsze, a nie w kółko dla każdego widżetu. Dlaczego musiałeś to rozwiązywać za każdym razem?
highBandWidth
2
Idealny wzór był taki sam dla każdego panelu, ale mechaniczne wyrównanie panelu, położenie poprzednich warstw w procesie i kafelkowa natura głowicy laserowej oznaczały, że dla każdego panelu trzeba było obliczyć dynamiczny zestaw wzorców podrzędnych indywidualnie, a następnie zoptymalizowane. Praca nad tym była interesującym problemem, zwłaszcza biorąc pod uwagę ograniczenia czasowe.
Mark Booth,
7

Pracuję (właściwie teraz) nad problemem bioinformatycznym polegającym na dopasowaniu wielu lokalnych sekwencji DNA. Chodzi o to, że jeśli wiele sekwencji genów o pewnej wspólnej właściwości (podobny profil ekspresji lub wiązanie tego samego czynnika transkrypcyjnego w eksperymencie z czipem ChIP) wyrównuje się silnie w pewnym momencie, to prawdopodobnie znalazłeś przyczynę ich wspólnej własność. Z drugiej strony jestem bardziej zainteresowany statystycznymi aspektami problemu. Mimo że jest to trudne dla NP, nie tracisz wiele, stosując heurystykę w praktyce. Interesująca część problemu, IMHO, to problem stosunku sygnału do szumu.

dsimcha
źródło
1
czy używasz klasycznych podejść kombinatorycznych / ai czy statystycznych. W pewnym sensie wszystkie współczesne procesy uczenia się grupowego, klastrowania i uczenia maszynowego radzą sobie z problemami np. Kompletnymi, ale zwykle atakowanymi z perspektywy statystycznej. Jest to jednak interesujące i istotne. Czy to jest w środowisku akademickim lub przemysłowym?
highBandWidth
@highBandWidth: Moje podejście jest statystyczne. Jestem w środowisku akademickim. Cały sens badań, które przeprowadzam, polega na tym, że jeśli zignorujesz problemy statystyczne i skupisz się na problemie kombinatorycznym, Bad Things Happen.
dsimcha
3

Naprawdę nie wiem, co oznacza NP zupełne / twarde, ale myślę, że autoplanowanie dostaw jest tego rodzaju.

Masz plan popytu na 90 dni do przodu dla 100 SKU produktów: piwo! SKU 100 produktów pochodzi z:

  • istnieje 10-15 rodzajów podstawowych surowców warzonych na poziomie 1, są one warzone w tysiące litrowych dużych puszkach i zajmuje to dzień;
  • po zaparzeniu należy dodać trochę materiałów (zakwas?) i musi to być odpoczynek przez 10-15 dni, a następnie masz 15-20 rodzajów rzeczy na poziomie 2;
  • w końcu, kiedy będzie gotowy, należy dodać trochę materiałów, to jest poziom 3, zwany piwem do picia, są cc. 30 rodzajów piwa;
  • piwo może być butelkowane jako 3 dl, 5 dl, czasami dostaje specjalne necklacigng (poziom 4), a następnie może być pakowane jako pudełko 5x4, 6-pak (poziom 5).

Dla każdej operacji istnieją „linie” maszynowe: od parzenia po pakowanie. Maszyny mogą wykonywać więcej operacji, powiedzmy, niektóre maszyny pakujące mogą produkować 6 sztuk i 3 sztuki, ale inne mogą produkować tylko 6 sztuk. Istnieją ograniczenia, np. Prędkość lub duży czajnik do zaparzania min. 6000, maksimum, 8000 l piwa (ale jeśli typ piwa jest lekki, wówczas min. To 5000 l, a maks. 7000 l). I tak dalej, na każdym poziomie.

Zadanie: jak wspomniałem, istnieje plan popytu na rodzaj 100 poziomu 5 (butelkowane, pakowane rzeczy). Stwórz optymalny plan produkcji dla wszystkich 5 poziomów, wszystkich maszyn. Zminimalizuj przełączniki maszyn (np. Butelkowanie .5, .5, .5, .3, .3, .3 jest lepsze niż .3, .5, .3, .5, .3, .5, jest mniej swithc, krótszy czas martwy dla maszyn do butelkowania). Ustal priorytet według klienta: niektórzy klienci wymagają wysyłki piwa, gdy pozostało ponad 50% czasu ważności. Itd itd.

Odkrywaj wąskie gardła (eh), twórz alternatywne plany z dodawaniem nieistniejących maszyn do tych punktów, a następnie możesz użyć najlepszego scenariusza wirtualnego, aby zasugerować zakup nowych maszyn.

Czy to jest wystarczająco trudne, czy powinienem powiedzieć, jak działa fabryka włókiennicza ?

(Uwaga osobista: sieć, bank i logistyka są trudnymi obszarami, ale są zabawkami dla dzieci w porównaniu do problemów związanych z produkcją).

Oświadczenie: liczby są zniekształcone ze względów bezpieczeństwa, rząd wielkości jest prawdziwy.

ern0
źródło
Pracujesz nad czymś takim lub narzędziem do rozwiązania takich problemów dla twojego pracodawcy?
highBandWidth
1
Produkcja ma duże znaczenie logistyczne. Pod tym względem zdecydowanie trudniejsze niż finanse. Ale przynajmniej zajmuje się określonymi problemami, a nie przypadkowymi równaniami i luźno określonymi porządkami działania!
Michael K
1
Każdy rodzaj algorytmu szeregowania z najlepszym dopasowaniem zasobów jest prawdopodobnie równoważny problemowi plecakowemu , który jest NP-zupełny.
Scott Whitlock,
Mój przyjaciel stworzył system DP / SP w Excel + VB lata temu. Nie zawiera automatycznego planowania, aplikacja jest zbyt gruba dla programu Excel. Właśnie dlatego stworzyliśmy oparty na MySQL / PHP / AJAX program do współpracy (patrz: przepływ danych - inaczej programowanie oparte na przepływie - podejście) - struktura arkusza kalkulacyjnego (ja) i przyjęliśmy logikę biz z wersji XLS (przyjaciel) . Wdrożyliśmy również automatyczne planowanie (przyjaciel). Napisanie arkusza kalkulacyjnego było szalonym pomysłem, ale działa. Najlepsza część: przełącznik XLS-> SQL jest dość wspaniały! Możemy zrobić wszystko z danymi (np. Autoplan), używając dowolnego narzędzia / platformy (PHP, Java, co chcemy).
ern0
@ ern0, NP-complete / NP-hard w zasadzie odnosi się do tego, jak mało skrótów można nawet przyjąć, zamiast próbować wszystkich możliwości jeden po drugim. Teoretycy poświęcają wiele wysiłku na znalezienie skrótów, które np. Mówią, że jeśli wiemy, że ścieżka ABC będzie zawsze dłuższa niż prąd przemienny bezpośrednio, możemy ją przyspieszyć i udowodnić, że jest w granicach 50% wartości optymalnej. Itd.