Czy używają programowania półfinałowego w przemyśle?

Nie widzę żadnej wzmianki o tym w ofertach pracy. Widziałem wspomniane programowanie liczb całkowitych, MIP, programowanie nieliniowe z mieszanymi liczbami całkowitymi, LP, programowanie dynamiczne itp., Ale nie SDP. Czy w akademii jest o wiele bardziej trendy niż w przemyśle?

Z powodu mojego ograniczonego kontaktu z pracownikami naukowymi i branżowymi w zakresie systemów elektroenergetycznych uważam, że istnieje duża szansa, że ​​niezależni operatorzy systemów zastosują SDP w optymalnych problemach z przepływem energii, ale zależy to od stopnia, w jakim można skalować głowice jaj udoskonalić obecne metody rozwiązywania większych problemów.

Z mojego ograniczonego doświadczenia w branży energetycznej nikt nie rozwiązuje SDP na taką skalę. Mam pewną ograniczoną wiedzę na temat tego, co robi Nowa Anglia ISO i myślę, że są bardziej zainteresowani włączeniem stochastyczności do swoich istniejących modeli MILP. Od znajomych, którzy pracowali nad systemami zasilania w rządowych laboratoriach badawczych w USA, myślą również o stochastyczności (programowanie stochastyczne, ograniczenia szans, solidna optymalizacja ...).

Z mojego doświadczenia w sektorze dużych firm technologicznych ludzie rozwiązują MILP w najbardziej skomplikowanych i zazwyczaj deterministycznych modelach.

Wydaje mi się, że od strony inżynierii chemicznej wydają się oni zainteresowani MINLP, w szczególności nie wypukłą, kwadratowo ograniczoną optymalizacją, która powstaje naturalnie w przypadku problemów z mieszaniem. Są też problemy związane z PDE i wszystkie inne fajne rzeczy, ale to głównie z mojej wiedzy.

Gdybym musiał spekulować, SDP może być użyty w projektowaniu półprzewodników jako podprogram (np. Dla MAXCUT), ale biorąc pod uwagę brak rozwiązywaczy jakości, domyślam się, że nie ma dużego popytu (przynajmniej, przynajmniej).

Powiedziałbym, że w środowisku akademickim SDP jest bardziej interesujące jako narzędzie sprawdzające, tj. „Spójrz, ten problem to czas wielomianowy!” jeśli potrafisz wymyślić, jak się pokłócić jako SDP. Rozwiązania SDP są tak drażliwe (w porównaniu z innymi wypukłymi klasami problemów), że myślę, że ludzie nie są tak bardzo podekscytowani pomysłem ich faktycznego rozwiązania.

Programowanie półfinałowe i programowanie stożka drugiego rzędu nie zostały tak szybko przyjęte w praktyce, jak wielu z nas miało nadzieję. Byłem w to zaangażowany przez ostatnie 20 lat i bardzo rozczarowujące było powolne postępy. Pozwól mi wskazać niektóre z wyzwań:

1. Chociaż mamy algorytmy wielomianu czasu dla SDP i SOCP, szeroko stosowane pierwotne podwójne wzorce punktów wewnętrznych zazwyczaj wymagają pamięci gdzie jest liczbą ograniczeń. To sprawia, że ​​rozwiązywanie problemów z 50 000 ograniczeń jest możliwe, ale rozwiązywanie problemów z 500 000 ograniczeń jest dziś niepraktyczne. Oczywiście, pojemność pamięci rośnie wykładniczo, więc wiele ważnych problemów ostatecznie da się rozwiązać, ale istnieje wiele problemów, których nie można praktycznie rozwiązać dzisiaj ani w najbliższej przyszłości. Metody pierwszego rzędu, które nie mają wymagań przechowywania są aktywnym tematem badań, ale w obszarze SDP po prostu nie okazały się wystarczająco solidne, aby można je było zastosować w rozwiązaniu ogólnego przeznaczenia. $O(m^{2})$$m$$O(m^{2})$

2. Dostawcy oprogramowania LP nie uważali za stosowne włączenia obsługi SDP w swoich produktach. Zaczyna się pojawiać ograniczona obsługa SOCP.

3. Wiedza na temat programowania półfinałowego rozprzestrzeniała się powoli. Podręcznik Boyda i Vandenberghe'a był bardzo pomocny w tym względzie, ale jest wiele do zrobienia, zanim technologia ta stanie się tak znana, jak starsze techniki optymalizacji.

4. Języki i systemy modelowania (takie jak GAMS, AMPL itp.) Nie zapewniają jeszcze dobrego wsparcia dla SOCP i SDP. Pakiet CVX jest najciekawszą pracą w tym kierunku, ale nawet wymaga nieco wyrafinowania ze strony użytkownika.

SDP znalazł zastosowania na poziomie badawczym w wielu obszarach inżynierii i nauki. Wydaje się prawdopodobne, że w końcu staną się one ważne również w przemyśle.

Większość pracy, o której wiem w laboratoriach związanych z problemami z przepływem energii, dotyczy również optymalizacji stochastycznej, koncentrując się głównie na MILP.

W inżynierii chemicznej są zainteresowani MINLP, a klasyczny przykład to problem mieszania (w szczególności prototypowy problem gromadzenia Haverly'ego), więc często pojawiają się terminy dwuliniowe. Terminy trójliniowe czasami pojawiają się, w zależności od termodynamicznych modeli mieszania lub użytych modeli reakcji. Istnieje również ograniczone zainteresowanie optymalizacją ograniczoną przez ODE lub ograniczoną przez PDE; żadna z tych prac nie używa SDP.

Większość prac związanych z optymalizacją ograniczonych przez PDE, które widziałem (szczególnie myślę o optymalizacji topologii), nie wykorzystuje SDP. Ograniczenia PDE mogą być liniowe i teoretycznie mogą dopuszczać sformułowanie SDP w zależności od celu i pozostałych ograniczeń. W praktyce problemy inżynieryjne wydają się być nieliniowe i dają problemy nie wypukłe, które są następnie rozwiązywane do lokalnych optymów (być może również przy użyciu wielu części). Czasami stosuje się formuły kary w celu wykluczenia znanych suboptymalnych lokalnych optymów.

Widziałem, że to może być stosowane w teorii sterowania. Niewielka ilość pracy, którą widziałem nad „nierównościami matrycy liniowej”, sugeruje, że może być użyteczna, ale teoria kontroli w przemyśle opiera się raczej na sprawdzonych metodach niż na nowatorskich formułach matematycznych, więc wątpię w SDP będą używane przez jakiś czas, dopóki nie udowodnią swojej przydatności.

Istnieje kilka solverów SDP, które są w porządku i rozwiązały problemy, które są dość duże dla środowisk akademickich (ostatnio sprawdziłem to 3-4 lata temu i rozwiązywały dziesiątki do setek tysięcy zmiennych), ale scenariusze przepływu mocy wiążą się ze znacznie większymi problemami (od dziesiątek milionów do miliardów zmiennych) i nie sądzę, że solwery już tam są. Myślę, że mogliby się tam dostać - ostatnio sporo pracy nad metodami opartymi na wewnętrznych matrycach bez matrycy, co sugeruje, że byłoby możliwe skalowanie rozwiązań SDP za pomocą tych technik - ale nikt jeszcze tego nie zrobił, prawdopodobnie ponieważ LP, MILP i wypukłe NLP pojawiają się znacznie częściej i są uznanymi technologiami.