Czy magnesy mogą pomóc podejmować lepsze decyzje w przedsiębiorstwie? Model Isinga i QUBO

W 1925 roku fizyk Ernst Ising badał, jak oddziałują na siebie maleńkie magnesy. Wyniki rozczarowały go do tego stopnia, że odszedł od fizyki. Ponad 20 lat później przypadkiem dowiedział się, że jego „porażka” ma już własną nazwę, model Isinga, i jest jednym z najsłynniejszych modeli w fizyce.

Dziś model noszący jego nazwisko znajduje zastosowanie daleko poza fizyką, między innymi w matematycznych problemach optymalizacji.

Co magnesy mają wspólnego z ERP?

Na co dzień rozwijam system ERP dla firm produkcyjnych i wiem jedno: w fabryce trudno podjąć decyzję, która nie wpłynie na coś innego. Mamy ograniczone zasoby, sprzeczne cele i mnóstwo zależności. Rozwiązanie dobre dla jednego obszaru niekoniecznie jest najlepsze dla całej organizacji.

Z magnesami Isinga jest podobnie. Każdy może przyjmować jeden z dwóch stanów, a jego ustawienie wpływa na pozostałe. Cały układ dąży do konfiguracji o możliwie najniższej energii.

Stąd pomysł: a gdyby wybrane problemy przedsiębiorstwa zapisać jako układ oddziałujących ze sobą magnesów? Matematycznie jest to możliwe. Co więcej, komputery kwantowe mogą okazać się szczególnie skuteczne w rozwiązywaniu takich problemów. Czy będą lepsze od klasycznych algorytmów, to wciąż otwarte pytanie.

Jak magnes zamienia się w decyzję

Fizyk opisuje taki układ jednym wyrażeniem, jego energią:

$E = -\sum_{i<j} J_{ij}\, s_i s_j \;-\; \sum_i h_i s_i, \qquad s_i \in \{-1,+1\}$

Tu $s_i = \pm 1$ to kierunek magnesu (w górę lub w dół). $J_{ij}$ mówi, czy dwa magnesy wolą się ustawić zgodnie czy przeciwnie i jak mocno. A $h_i$ to zewnętrzne pole, które popycha pojedynczy magnes w jedną stronę.

Teraz wystarczy podmienić słowa:

• kierunek magnesu to decyzja tak/nie,
• oddziaływanie to koszt lub zysk z tego, że dwie decyzje podjęto razem,
• zewnętrzne pole to koszt pojedynczej decyzji,
• najniższa energia to najlepszy zestaw decyzji naraz.

Od magnesów do QUBO

Prosta zamiana zmiennych zmienia magnesy w zwykłe bity (0/1), a energię w funkcję kwadratową bitów:

$s_i = 2x_i - 1, \quad x_i \in \{0,1\} \qquad\Longrightarrow\qquad E(\mathbf{x}) = \mathbf{x}^{\top} Q\, \mathbf{x} + \text{const}$

W informatyce nazywa się to QUBO (Quadratic Unconstrained Binary Optimization). I tu jest sedno: ten sam zapis opisuje problem wyboru najlepszej kombinacji spośród $2^n$ możliwych.

Dlaczego to trudne

Bo nie da się zadowolić wszystkich par jednocześnie. Przy kilkuset decyzjach liczba kombinacji przekracza liczbę atomów we wszechświecie, a dobre ustawienie jednej pary psuje inną. Fizycy nazywają to frustracją, menedżerowie sprzecznymi celami.

Najbardziej zaskakuje mnie to, że ten sam wzór może opisywać układ magnesów i zarazem decyzje w fabryce. Sto lat temu to równanie opisywało żelazo. Czy opisze też fabrykę na tyle dobrze, żeby dało się na tym oprzeć realną optymalizację, czy to tylko zgrabna analogia, warto sprawdzać na konkretnych problemach.