Podręcznik
Wersja podręcznika: 1.0
Data publikacji: 01.01.2022 r.
Wykłady
W1…WN, odpowiadające w sumie ok. 10-12 godz. standardowego wykładu
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ą
, której wartość nie jest całkowitoliczbowa: jeśli zapiszemy wartość
, gdzie
jest częścią ułamkową, to warunki podziału mają postać:
- 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
można dzielić węzeł, ze względu na sumaryczną wartość zmiennych, których wartości są zbliżone, czyli dzielimy
i wymagamy aby
lub
(w orginalnym zbiorze
te dwie sumy są ułamkowe i mają zbliżone wartości)
- 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:
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.
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 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.