Podręcznik

2.5. Strategia przeszukiwania: wybór węzła do eksploracji

W ostatniej części tego rozdziału przedstawiamy najpopularniejsze strategie przeszukiwania drzewa BB, gdzie kluczową trudnością jest zachowanie odpowiedniego kompromisu między szybkością znalezienia rozwiązania dopuszczalnego i optymalnego.

Wyróżniamy strategie: 

• BeFS (best first search): wybierany wierzchołek o najlepszym oszacowaniu (inaczej best bound)
  • modyfikacja: best estimate z wykorzystaniem pseudokosztów, lub pseudocen dualnych,
  • wierzchołki krytyczne – takie, dla których oszacowania b. bliskie optimum; nie da się ich prosto wyeliminować i muszą być rozpatrzone aby udowodnić optymalność rozwiązania – możliwy problem z pamięcią, gdy dużo takich wierzchołków;
• BFS (breadth first search): wszerz
  • z każdym poziomem liczba wierzchołków rośnie wykładniczo;
• DFS (deapth first search): wgłąb, można użyć rekurencji
  • jeśli rozwiązanie dopuszczalne jest daleko od optimum to drzewo b. głębokie;
• Selekcja: DFS i BeFS – gdy wybór między gałęziami o dużych różnicach w oszacowaniach;

Sprawdź różnicę w działaniu solwera cplex, np. dla zadania scalableWarehouse, gdy ręcznie narzucisz strategię wyboru kierunku i węzłów (MIP branching direction, MIP node selction strategy).