NP kompletne lub NP trudne problemy w prawdziwym życiu

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?

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 :)

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).

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.

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.