2. Metoda podziału i oszacowań

2.4. Reguły podziału węzła

Wyróżniamy następujące reguły podziału podproblemów.

Podział na 2 części (dytochomiczny)
  • przy stosowaniu relaksacji liniowej wprowadzane są dwa ograniczenia na zmienną x_i, której wartość nie jest całkowitoliczbowa: jeśli zapiszemy wartość x_i=n+d, gdzie d jest częścią ułamkową, to warunki podziału mają postać:
    • x_i \leq n
    • x_i \geq n+1
  • generalizacja podziału, tzw. ograniczenie GUB (generalized upper bound): w zadaniach przydziału, w których wymagamy aby tylko jedna zmienna miała wartość niezerową, czyli z ograniczeniami postaci \sum_i x_i = 1 można dzielić węzeł, ze względu na sumaryczną wartość zmiennych, których wartości są zbliżone, czyli dzielimy S = S_1 \cup S_2 i wymagamy aby \sum_{i\in S_1} x_i =0 lub \sum_{i\in S_2} x_i =0  (w orginalnym zbiorze S te dwie sumy są ułamkowe i mają zbliżone wartości)
Wybór zmiennej do podziału -- najczęściej wiele zmiennych nie będzie mieć wartości całkowitoliczbowych, konieczne strategie wyboru, np.:
  • wg największej/najmniejszej niedopuszczalności - wybierana zmienna, której wartość jest najdalej/najbliżej od jej wartości zaokrąglenia
  • na podstawie szacowanej wartości zmiennej: różne sposoby szacowania pogorszenia funkcji celu, aby ocenić opłacalność wymuszenia ograniczenia danej zmiennej
    • wyliczanie kar (penalty) na podstawie kosztów zredukowanych zmiennej, dla której sprawdzamy koszty wyjścia z bazy (w metodzie dual simplex),
    • szacowanie pseudokosztów zredukowanych na podstawie wartości f. celu, w której zmienna wymuszona na wartość całkowitoliczbową,
    • szacowanie pseudocen dualnych - j.w. tylko w odniesieniu do cen dualnych, a nie kosztów zredukowanych,
    • silny podział (strong branching) - wyliczenie wartości f. celu w kilku iteracjach algorytmu simplex, przy ustalonej (całkowitoliczbowej) wartości zmiennej;
    • użycie priorytetów podanych przez użytkownika.

Użycie hiperpłaszczyzn (branch and cut)
  • Na podstawie znajomości struktury problemu dodajemy odcięcia angażujące większą liczbę zmiennych, uzyskane np. poprzez agregację niektórych ograniczeń.

Podział na wiele części (politochomiczny)
  • Przykładowo, w problemie komiwojażera (TSP), dla relaksacji opartej na drzewie rozpinającym możemy wybierać wiele restrykcji dla konkretnego podproblemu, gdyż sprowadzają się one do usunięcia konkretnych krawędzi z aktualnej drogi TSP; przykład można znaleźć w książce W. L. Winstona „Operations research - Applications and Algorithms" Thomson Learning (2004);
  • priorytet zmiennej do wyboru na podst. znajomości problemu: w najprostszym przypadku wg wektora cen.

Rozwiąż metodą B&B problem komiwojażera dla 5 miast, z kosztami połączeń podanymi w tabeli:
A B C D E
A - 132 217 164 58
B 132 - 290 201 79
C 217 290 - 113 303
D 164 201 113 - 196
E 58 79 303 196 -
 Jako UB przyjmij rozwiązanie dopuszczalne naiwne, tj. koszt drogi A-B-C-D-E-A = 789.
Jako LB przyjmij rozwiązanie zadania minimalnego drzewa rozpinającego (minimum spanning tree).  Wskazówka - zastosuj podział politochomiczny w następujący sposób. W każdej iteracji metody B&B wybierz z aktualnego rozwiązania drzewa rozpinającego to miasto, które jest połączone z więcej niż dwoma innymi miastami, tj. miasto reprezentowane przez wierzchołek o stopniu większym niż dwa. Wydziel nowe podproblemy odrzucając kolejno możliwość użycia każdego z owych połączeń przy konstrukcji nowego drzewa rozpinającego.