Optymalizacja przy użyciu

techniki Branch and Bound

Autor:
Adam Szklanko

Dnia 21.11.2007

Wprowadzenie

-

Metoda branch and bound w języku polskim określana
metodą podziału i ograniczeń.

-

polega na dekompozycji i sterowanym przeszukiwaniu
zbioru rozwiązań dopuszczalnych danego problemu

Metoda używana do

a)rozwiązywania dyskretnych zadań decyzyjnych
b)problem komiwojażera (NP-trudny)
c)problem plecakowy
d)programowanie liniowe
e)programowanie nieliniowe
g)algorytmy poszukiwań np. najbliższego sąsiada
h)kwadratowego zagadnienia przydziału

Rodzaje węzłów drzewa B&B

•

węzły krytyczne – rozwiązania niepełne o koszcie
mniejszym od od optimum,

•

węzły niedecydujące – rozwiązania niepełne o koszcie
równym optimum,

•

węzły optymalne - o koszcie równym optimum,

•

węzły eliminowane - o koszcie większym od optimum.

•

Każda strategia generuje węzły krytyczne – tworzą
drzewo krytyczne.

Drzewo minimalne

Zawiera węzły, które musza być określone dla

udowodnienia optymalności rozwiązania poprawnego w
wyniku zastosowania dowolnej strategii. W
przetwarzaniu równoległym minimalne drzewo musi być
przeanalizowane, w sekwencyjnym niekoniecznie stąd
wynika możliwość uzyskania pod lub ponad
liniowego przyspieszenia.

Ogólny schemat podziału i ograniczeń

Zbiór wszystkich dopuszczalnych rozwiązań danego

problemu rozbijany jest na problemy.
Każdy taki podzbiór odpowiada problemowi o rozmiarze
mniejszym niż problem wyjściowy (podproblemowi).

Rozwiązywany jest on na jeden z następujących
sposobów:

•

poprzez relaksację

•

bezpośrednio

•

pośrednio

•

poprzez podział

Rozbijanie –> poprzez relaksacje

Polega na takim jego „uproszczeniu”, żeby był o

wiele łatwiejszy do rozwiązania. Termin ten oznacza
usunięcie, osłabienie i może odnosić się do ograniczeń
lub funkcji celu. Problem zrelaksowany jest
rozwiązywany i sprawdzane jest czy znalezione
rozwiązanie może być również rozwiązaniem problemu
niezrelaksowanego.

Jeżeli tak, to jest to rozwiązanie optymalne danego

problemu (podproblemu).

Jeżeli nie, to wartość funkcji celu rozwiązania

problemu zrelaksowanego używane jest jako dolne
ograniczenie dla tego problemu (podproblemu).

Rozbijanie  bezpośrednio

Rozwiązuje się problem (podproblem) przeglądając

wszystkie rozwiązania w danym podzbiorze, obliczając

dla nich wartość funkcji celu i wybierając takie, dla

którego wartość ta jest najmniejsza.

W praktyce problem rozwiązuje się bezpośrednio wtedy,

gdy istnieje już tylko jedno rozwiązanie w podzbiorze

rozwiązań.

Rozbijanie  pośrednio

Rozwiązany jest problem (podproblem), dla którego

stwierdzono, że dolne ograniczenie jest większe od
górnego ograniczenia całego problemu.

Górne ograniczenie (ang. upper bound) to

zazwyczaj wartość funkcji celu najlepszego dotychczas
znalezionego rozwiązania.

Rozbijanie –> poprzez podział

Stosuje się do problemów, których nie da rozwiązać:

-

bezpośrednio (zbiór rozwiązań jest zbyt liczny)

-

pośrednio (dolne ograniczenie jest mniejsze niż górne
ograniczenie)

-

przy pomocy relaksacji (rozwiązanie problemu
zrelaksowanego nie jest rozwiązaniem problemu)

Algorytmy podziału i ograniczeń (B&B)

Każdy algorytm oparty na metodzie podziału i

ograniczeń wymaga precyzyjnego określenia
następujących elementów:

-

reguła wyboru określająca kolejność rozwiązywania
podproblemów,

-

przyjęta relaksacja dostarczająca dolne ograniczenie

-

reguły eliminacji

-

zasada podziału (tworzenie podproblemow)

Strategie wyboru nowych węzłów

Istnieją różne strategie wyboru kolejnych węzłów, z

których kontynuowany jest proces podziału:

–

strategia mieszana

–

podział z węzła o minimalnym dolnym ograniczeniu

–

podział z kolejnego otrzymanego węzła

Przykład  problem komiwojażera

–

(ang. TSP = Travelling Salesman Problem)

–

Dany jest zbiór n miast.

–

Komiwojażer musi:

- odwiedzić wszystkie miasta

- w każdym z nich będąc tylko raz

- i powrócić do miasta z którego wyruszył.

-

Znając odległości pomiędzy każdą parą miast należy tak

ułożyć trasę komiwojażera, aby jej długość była minimalna.

–

TSP to problem trudny (NP-trudny), dla którego nie jest znany

algorytm efektywny, tzn. rozwiązujący ten problem w czasie

wielomianowym.

–

Aby znaleźć optymalne rozwiązanie takiego problemu należy

(w najgorszym przypadku) przeglądnąć wszystkie możliwe

rozwiązania i wybrać najlepsze.

–

W problemie komiwojażera z 20 miastami liczba możliwości to

liczba permutacji n-1 elementowego zbioru czyli (n-1)! .

Wynosi ona 19! > 10

17

.

Algorytm

1.

Redukcja macierzy kosztów i obliczenie dolnego ograniczenia. (ang.

LB = Lower Bound).

2.

Wybór łuku (i,j) według którego nastąpi podział zbioru rozwiązań.

3.

Podział zbioru rozwiązań na dwa podzbiory rozwiązań: z wybranym

łukiem (i,j) (lewe poddrzewo) oraz nie zawierających tego łuku

(prawe poddrzewo).

4.

W lewym poddrzewie: zmniejszenie rozmiaru macierzy,

zapobieżenie pojawieniu się cykli, redukcja macierzy i obliczenie

dolnego ograniczenia.

5.

W prawym poddrzewie: zabronienie łuku (i,j) (wstawienie ∞ w

pozycji (i,j) macierzy), redukcja macierzy i obliczenie dolnego

ograniczenia.

6.

Jeżeli rozmiar macierzy w lewym poddrzewie wynosi 2 × 2 to

dobierane są odpowiednio dwa pozostałe łuki, w przeciwnym

przypadku dla tej macierzy wykonywany jest krok 2.

7.

Rozpatrzenie wszystkich podzbiorów rozwiązań dla których dolne

ograniczenie jest mniejsze od kosztu najlepszego znalezionego

rozwiązania.

Macierz kosztów

1

2

3

4

1

∞

3

93

14

2

33

∞

9

4

3

76

42

∞

21

4

10

45

17

∞

Każdy element a

ij

oznacza

koszt przejścia pomiędzy
miastem i-tym a miastem j-tym,
czyli reprezentuje łuk (i,j) .

Krok 1 – redukcja macierzy
kosztów

1

2

3

4

1

∞

3

93

14

2 33

∞

9

4

3 76

42

∞

21

4

10

45

17

∞

1

2

3

4

1

∞

0

90

11

2

29

∞

5

0

3

55

21

∞

0

4

0

35

7

∞

1

2

3

4

1

∞

0

85

11

2

29

∞

0

0

3

55

21

∞

0

4

0

35

2

∞

Macierz zredukowana
Dolne ograniczenie
LB=(3+4+21+10)+5 =
43

(4,1)(1,2) (2,3) (3,4)

10+3+9+21=22+21=43

Krok 2
Wybór łuku wg którego nastąpi podział. Wybierany jest łuk, który
powoduje największy wzrost dolnego ograniczenia dla rozwiązań
niezawierających tego łuku.

(1,2)=11+21=32
(2,3)=0+2=2
(2,4)=0+0=0
(3,4)=0+21=21
(4,1)=29+2=31

1

2

3

4

1

∞

0

85

11

2

29

∞

0

0

3

55

21

∞

0

4

0

35

2

∞

Wybieramy sumę min
wag w wierszu i kolumnie.

Krok 3
Podział zbioru rozwiązań.
Wybrany łuk to (1,2).
Zbiór rozwiązań dzielony jest na dwa pozbiory:

- lewe poddrzewo – rozwiązania z łukiem (1,2)
- prawe poddrzewo – rozwiązania bez łuku (1,2)

Wszystkie rozwiązania

Rozwiazania

z (1,2)

Rozwiazania

bez (1,2)

LB=43

Krok 4
Macierz lewego poddrzewa

1

2

3

4

1

∞

0

85

11

2

29

∞

0

0

3

55

21

∞

0

4

0

35

2

∞

1

3

4

2

29

0

0

3

55

∞

0

4

0

2

∞

Macierz dla rozwiązań bez łuku (3,4)
Dolne ograniczenie LB=43+

21+11

=75

Krok 5
Macierz prawego
poddrzewa

1

2

3

4

1

∞

∞

85

11

2

29

∞

0

0

3

55

21

∞

0

4

0

35

7

∞

1

2

3

4

1

∞

∞

74

0

2

29

∞

0

0

3

55

0

∞

0

4

0

14

7

∞

Macierz dla rozwiązań z łukiem (1,2)
Dolne ograniczenie LB=42

Drzewo rozwiazań po
pierwszym etapie

Wszystkie rozwiazania

Rozwiazania

z (1,2)

Rozwiazania

bez (1,2)

LB=43

LB=4
3

LB=75

Krok 2 i 3
Wybór łuku i podział zbioru rozwiązań

1

3

4

2

29

0

0

3

55

∞

0

4

0

2

∞

(2,3)=0+2=2
(2,4)=0+0=0
(3,4)=55+0=5
5
(4,1)=2+29=3
1

Rozwiazania

z (1,2)

Rozwiazania

z (1,2) i (3,4)

Rozwiazania

z (1,2) i bez (3,4)

LB=43

Krok 4
Macierz lewego poddrzewa

1

3

4

2

29

0

0

3

55

∞

0

4

0

2

∞

1

3

2 29

0

4

0

2

(1,2) i (3,4)

Macierz dla rozwiązań z łukiem (3,4) i (1,2)
Dolne ograniczenie LB=43

Krok 5
Macierz prawego
poddrzewa

1

3

4

2

29

0

0

3

55

∞

∞

4

0

2

∞

1

3

4

2

29

0

0

3

0

∞

∞

4

0

2

∞

Macierz dla rozwiązań z (1,2) i bez (3,4)
Dolne ograniczenie LB=43+

55

=98

Drzewo rozwiazań po
drugim etapie

Wszystkie rozwiazania

Rozwiazania

z (1,2)

Rozwiazania

bez (1,2)

LB=43

LB=43

LB=75

Rozwiazania

z (1,2) i (3,4)

Rozwiazania

z (1,2) i bez (3,4)

LB=43

LB=98

Krok 6
Uzupełnianie trasy komiwojażera
W macierzy 2x2 dobieramy tak pozostałe dwa łuki, aby utworzyć
kompletną trasę komiwojażera (cykl Hamiltona).

1

3

2

29

0

4

0

2

Wybieramy łuki (2,3) i (4,1) :
(4,1) (1,2) (2,3) (3,4)
->trasa komiwojażera (4,1,2,3,4)
Koszt trasy= LB+

0

+

0

=42+0=43

Górne ograniczenie(LU) = 43

Wszystkie rozwiazania

Rozwiazania

z (1,2)

Rozwiazania

bez (1,2)

LB=43

LB=43

LB=75

Rozwiazania

z (1,2) i (3,4)

Rozwiazania

z (1,2) i bez (3,4)

LB=43

LB=98

Rozwiazanie

(4,1,2,3,4)

UB(koszt)=43

Krok 7
Zgodnie z algorytmem brak

Dziękuje za uwagę

Pytań brak ?!!!!