2. Metoda podziału i oszacowań

Metoda podziału i oszacowań (B&B ang. branch and bound) stanowi podstawowy paradygmat rozwiązywania NP-trudnych problemów optymalizacji dyskretnej. Dla ustalenia uwagi problem (IP) zapiszmy jako:

\(\min \; c^T x\), p.o.: \(x\in S\), tj.:

\(Ax\geq b\)

\(\displaystyle x\in \mathcal{C}^+.\)

Metoda podziału i oszacowań zakłada:

  • przegląd obszaru rozwiązań dopuszczalnych \(S\) poprzez iteracyjny podział (branch) tego obszaru, czyli wydzielanie podproblemów dzięki dodaniu ograniczeń odcinających część rozwiązań,
  • iteracyjne szacowanie (bound) rozwiązania w każdym podproblemie w sposób przybliżony, niedokładny, co uzyskiwane jest dzięki relaksacji podproblemu - najczęściej jest stosowana relaksacja warunku całkowitoliczbowości, ale też np. relaksacja Lagrange'a, i in..

Podproblemy (podziały) są organizowane w postaci drzewa. Metoda B&B pozwala na systematyczne i efektywne zawężanie zakresu dla optimum globalnego, gdyż w każdej iteracji wyznaczane jest:

  • dolne oszacowanie LB (Lower Bound), czyli wartości f. celu podproblemu wskazująca na jego potencjalną atrakcyjność i potrzebę dalszej eksploracji (lub pominięcia),
  • górne oszacowanie UB (Upper Bound), czyli najlepsza do-tej-pory wartość f. celu podproblemu, w którym osiągnięto rozwiązanie globalnie dopuszczalne, tzw. incumbent solution (np. całkowitoliczbowe, lub ogólnie, takie że \(x\in S\)).
W problemie maksymalizacji znaczenie oszacowań UB i LB jest odwrotne, tj. UB wskazuje na potencjalnie osiągalną wartość maksimum w danym wierzchołku, a LB jest wartością aktualnego najlepszego dopuszczalnego rozwiązania.
Ilustrację koncepcji przedstawia poniższy rysunek. Podstawą metody B&B jest właściwość: w obszarze wydzielonym z większego obszaru na pewno nie znajdziemy lepszego optimum niż w pierwotnym, szerszym zakresie!
Organizacja podziału obszaru dopuszczalnego w postaci drzewa.