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.3. Rola funkcji szacującej jakość rozwiązań w podproblemie
Funkcją szacującą (ang. bounding function) nazywamy metodę pozwalającą wyznaczyć jakość rozwiązań w podproblemie zrelaksowanym.
Liczba wierzchołków drzewa B&B może rosnąć wykładniczo, dlatego ważne jest:
- Wyznaczenie oszacowania LB możliwie dużej wartości, blisko wartości optymalnej co pozwala na szybkie zamykanie podproblemów;
- Wyznaczenie oszacowania możliwie mało czasochłonne;
- Idealnie jeśli w podproblemie oprócz oszacowania LB potrafimy stosunkowo łatwo wyznaczyć rozwiązanie dopuszczalne;
- Dwie ogólne metody szacowania optymalnej f. celu:
- relaksacja części ograniczeń, optymalizacja w łatwiejszym (szerszym) zbiorze
, takim że
;
- modyfikacja f. celu tak, że
, np. poprzez zastąpienie sumą kosztów implikowanych aktualnym ograniczeniem na zmienne.
- Relaksacja Lagrange’a: połączenie tych strategii – silne, ale czasochłonne,
- Najczęściej stosowana relaksacja liniowa, czyli odrzucenie warunku całkowitoliczbowości.
- relaksacja części ograniczeń, optymalizacja w łatwiejszym (szerszym) zbiorze
Kwestie dodatkowe - rola preprocessingu i heurystyk:
- Zastosowanie metody płaszczyzn tnących (cutting planes) przed rozpoczęciem algorytmu B&B - Zacieśnienie sformułowania LP w węźle 0;
- Duże znaczenie ma też stosowanie algorytmów obliczeń współbieżnych.