Podręcznik

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.