Branch and bound

• Podziel i ogranicz
• Algorytm dokładny (nieheurystyczny) - wyszukiwanie optymalnego rozwiązania bez konieczności sprawdzania wszystkich rozwiązań
• Często wolny algorytm
• W najgorszym przypadku wykładniczy wzrost czasu wykonywania algorytmu wraz ze wzrostem rozmiaru danych wejściowych

Branch and bound

• Polega ona na przeszukaniu drzewa reprezentującego przestrzeń rozwiązań problemu

• Dwie procedury:

  • Podział - dzielenie zbioru rozwiązań na rozłączne podzbiory
  • Ograniczanie - pomijanie w przeszukiwaniu gałęzi, o których wiemy że nie zawierają optymalnego rozwiązania. Ograniczenia mogą być dolne (lower bound) lub górne (upper bound)

Brute force (dla porównania)

https://www.geeksforgeeks.org/0-1-knapsack-using-branch-and-bound/

Branch and bound

https://www.geeksforgeeks.org/branch-and-bound-algorithm/

Branch and bound

Ignorujemy rozwiązania, które:

1. Są niemożliwe (mają sumę wag większą niż nasza pojemność)
2. Są gorsze niż obecne najlepsze pełne rozwiązanie

Branch and bound

Kolejność? Wstępna heurystyka

Strategie:

• Wyliczamy gęstość (relację wartości do wagi)
• Sortujemy

Ograniczanie:

• Wkładamy do plecaka posortowane elementy of najcenniejszego aż do zapełnienia plecaka
• Ostatni element może być włożony częściowo
• Np. plecak ma ograniczenie wagi (W) równe 5. Dwa posortowane elementy ważą razem 4 (2 + 2) i mają wartość 10 (6 + 4). Trzeci z posortowanych elementów waży 2 i ma wartość 2. Czyli suma wartości wynosi 6 + 4 + (1/2 * 2) = 11.
• W ten sposób określamy górne ograniczenie (ang. upper bound) - plecak nie będzie bardziej wartościowy niż te kilka najcenniejszych elementów

Branch and bound

https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/

Branch and bound

Algorytm:

1. Sortuj wszystkie pozycje w kolejności malejącego stosunku wartości do wagi. W ten sposób używając algorytmu zachłannego możemy wyznaczyć górne ograniczenie.
2. Zainicjuj maksymalny zysk, maxProfit = 0
3. Stwórz pustą kolejkę, Q.
4. Stwórz węzeł drzewa decyzyjnego i umieść go w kolejce Q. Zysk i waga węzła wynoszą 0.
5. Gdy Qnie jest pusty:
   • Wyciągnij element z Q, nazwijmy go u.
   • Oblicz zysk węzła następnego poziomu. Jeśli zysk jest większy niż maxProfit, to zaktualizuj maxProfit.
   • Oblicz granicę węzła następnego poziomu. Jeśli wartość graniczna jest większa niż maxProfit, to dodaj węzeł następnego poziomu do Q.
   • Rozważ przypadek, gdy węzeł następnego poziomu nie jest uważany za część rozwiązania i dodaj węzeł do kolejki z poziomem jako następnym, ale wagą i zyskiem bez uwzględnienia węzłów następnego poziomu.

Branch and bound

• Implementacja I - https://en.wikipedia.org/wiki/Branch_and_bound#Pseudocode
• Implementacja II - https://www.geeksforgeeks.org/implementation-of-0-1-knapsack-using-branch-and-bound/

Problem komiwojażera I

http://www.cs.put.poznan.pl/mkasprzak/zp/ZP-wyklad5.pdf

Problem komiwojażera II

http://lcm.csa.iisc.ernet.in/dsa/node187.html

Problem komiwojażera II

• Podejście - z jednej strony musi być dany odcinek, a z drugiej danego odcinka nie może być

http://lcm.csa.iisc.ernet.in/dsa/node187.html

Problem komiwojażera II

Ignorujemy (przycinamy) cząstkowe rozwiązania, które:

1. Są dłuższe niż obecne najkrótsze pełne rozwiązanie

Sortujemy:

1. Np. według najkrótszych pojedynczych odcinków

Problem komiwojażera II

http://lcm.csa.iisc.ernet.in/dsa/node187.html

Inne materiały

• https://tarakc02.github.io/branch-and-bound/
• http://web.tecnico.ulisboa.pt/mcasquilho/compute/_linpro/TaylorB_module_c.pdf
• https://www.geeksforgeeks.org/8-puzzle-problem-using-branch-and-bound/
• https://www.geeksforgeeks.org/job-assignment-problem-using-branch-and-bound/
• https://www.geeksforgeeks.org/n-queen-problem-using-branch-and-bound/
• https://towardsdatascience.com/the-branch-and-bound-algorithm-a7ae4d227a69