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:
    1. relaksacja części ograniczeń, optymalizacja w łatwiejszym (szerszym) zbiorze S^R, takim że  S\subseteq S^R;
    2. modyfikacja f. celu tak, że  g(x)≤f(x), 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.