Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

.title[
# Optymalizacja dyskretna <br>(w tym algorytmy heurystyczne)
]
.subtitle[
## Przykłady problemów
]
.author[
### Jakub Nowosad <br><a href="https://jakubnowosad.com/" class="uri">https://jakubnowosad.com/</a>
]

---

# Typy problemów optymalizacyjnych

- Problem komiwojażera (ang. *traveling salesman problem*, TSP)
- Problem podziału kwadratowego (ang. *quadratic assignment problem*, QAP)
- Problem plecakowy (ang. *knapsack problem*)
- Problem podziału grafu (ang. *graph partitioning problem*, GPP)
- Problem minimalnego drzewa rozpinającego (ang. *minimum spanning tree problem*, MSTP)
- Problem kolorowania grafu (ang. *graph coloring problem*)
- Problem marszrutyzacji (ang. *vehicle routing problem*, VRP)
- [wiele innych...](https://www.csc.kth.se/tcs/compendium/)

---
class: inverse, left, bottom
# Problem komiwojażera

---
# Problem komiwojażera

.pull-left[
- Problem komiwojażera (ang. *travelling salesman problem*, *TSP*) - przedstawiciel handlowy musi odwiedzić pewną liczbę klientów i wrócić do początkowego punktu. (Grafy hamiltownowskie)

- Celem jest znalezienie najkrótszej trasy, która spełnia te warunki.
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-1-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Jesteśmy w stanie określić odległość między każdą parą punktów (czy to w linii prostej czy też wzdłuż, np. sieci drogowej)
- Rozwiązaniem jest taka kolejność punktów, dla której suma odległości między punktami jest minimalna
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-2-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Problem komiwojażera jest NP-trudny
- W efekcie, aby rozwiązać ten problem konieczne jest posługiwanie się algorytmami heurystycznymi
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-3-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Teoretycznie możliwe jest sprawdzenie wszystkich możliwych kombinacji punktów spełniających wejściowe założenia
- `$$(n - 1)! / 2$$`, gdzie `$n$` oznacza liczbę punktów
- Pojawia się tutaj jeden poważny problem - czas obliczeń
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-4-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Teoretycznie możliwe jest sprawdzenie wszystkich możliwych kombinacji punktów spełniających wejściowe założenia
- `$(n - 1)! / 2$`, gdzie `$n$` oznacza liczbę punktów
- Przykładowo:
    * dla `$n = 5$` istnieje 12 kombinacji
    * dla `$n = 10$` istnieje 181440 kombinacji
    * dla `$n = 20$` istnieje 60822550204416000 kombinacji
    * dla `$n = 40$` istnieje 10198941040598720793914236470619042080159170560 kombinacji
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-6-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Przyjmując, że jedna kombinacja może być wyliczona w nanosekundę ( `$10^{-9}$` ), to:
    * dla `$n = 5$` czas obliczeń to 0.00000001 sekundy
    * dla `$n = 10$` czas obliczeń to 0.0002 sekundy
    * dla `$n = 20$` czas obliczeń to 703.96 dni
    * dla `$n = 40$` czas obliczeń to 323184939304596038919219314688 lat
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-8-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Reprezentacja rozwiązania - permutacja (wektor), np. 12435
- Problem komiwojażera może być symetryczny lub asymetryczny
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-9-1.png" style="display: block; margin: auto;" />
]

---
# Problem komiwojażera

.pull-left[
- Problem komiwojażera jest powszechnie używany w planowaniu czy logistyce
- Jest on też stosowany do opisu innych sytuacji, np. w produkcji mikroczipów, sekwencjonowaniu DNA, czy astronomii
- https://en.wikipedia.org/wiki/Travelling_salesman_problem
- https://fronkonstin.com/2018/04/04/the-travelling-salesman-portrait/
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-10-1.png" style="display: block; margin: auto;" />
]

---
class: inverse, left, bottom
# Problem podziału kwadratowego

---
# Problem podziału kwadratowego

.pull-left[
- Problem przydziału kwadratowego (ang. *quadratic assignment problem*, QAP)
- Istnieje zestaw `$n$` lokalizacji i `$n$` funkcji
- Dla każdej pary lokalizacji można wyliczyć odległość
- Dla każdej pary funkcji istnieje jakaś relacja (określana jako waga albo inteakcja), np. liczba dostaw
- Cel - odkrycie takiego przypisania funkcji do lokalizacji, aby zminimalizować sumy odległości przemnożone przez wagi

]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-11-1.png" style="display: block; margin: auto;" />
]

---
# Problem podziału kwadratowego

.pull-left[
Przykłady:
- Optymalne rozmieszczenie działów firmy w jej budynkach 
- Optymalne rozmieszczenie klawiszy na klawiaturze
]

.pull-right[
<img src="01-problemy_files/figure-html/unnamed-chunk-12-1.png" style="display: block; margin: auto;" />
]

---
# Problem podziału kwadratowego

.pull-left[
- Macierz A - macierz odległości - podobne jak w TSP
- Macierz B - macierz interakcji - jak silna jest interakcja między parami funkcjonalności
- Cel - mnożymy odległości razy siłę interakcji, sumujemy wynik i chcemy, żeby uzyskana wartośc była jak najmniejsza
- Jest to również problem permutacyjny
]

.pull-right[
- Macierz A (odległości)

```
##      1    2    3    4    5
## 1 0.00 1.56 1.12 2.13 2.28
## 2 1.56 0.00 1.30 3.68 2.24
## 3 1.12 1.30 0.00 2.87 1.22
## 4 2.13 3.68 2.87 0.00 3.57
## 5 2.28 2.24 1.22 3.57 0.00
```

- Macierz B (interakcji)

```
##   A B C D E
## A 0 7 2 9 6
## B 7 0 5 3 9
## C 2 5 0 5 2
## D 9 3 5 0 4
## E 6 9 2 4 0
```
]

---
# Problem podziału kwadratowego

.pull-left[
- Macierz A (odległości)

```
##      1    2    3    4    5
## 1 0.00 1.56 1.12 2.13 2.28
## 2 1.56 0.00 1.30 3.68 2.24
## 3 1.12 1.30 0.00 2.87 1.22
## 4 2.13 3.68 2.87 0.00 3.57
## 5 2.28 2.24 1.22 3.57 0.00
```

- Macierz B (interakcji)

```
##   A B C D E
## A 0 7 2 9 6
## B 7 0 5 3 9
## C 2 5 0 5 2
## D 9 3 5 0 4
## E 6 9 2 4 0
```
]

.pull-right[
Wynik:

```
## [1] 229.56
```
]

---
# Problem podziału kwadratowego

.pull-left[
- Macierz A (odległości)

```
##      1    2    3    4    5
## 1 0.00 1.56 1.12 2.13 2.28
## 2 1.56 0.00 1.30 3.68 2.24
## 3 1.12 1.30 0.00 2.87 1.22
## 4 2.13 3.68 2.87 0.00 3.57
## 5 2.28 2.24 1.22 3.57 0.00
```

- Macierz B (interakcji)

```
##   B A C D E
## B 0 7 2 9 6
## A 7 0 5 3 9
## C 5 2 0 5 2
## D 3 9 5 0 4
## E 9 6 2 4 0
```
]

.pull-right[
Wynik:

```
## [1] 238.44
```
]

---
class: inverse, left, bottom
# Problem plecakowy

---
# Problem plecakowy

.pull-left[
- Problem plecakowy (ang. *knapsack problem* lub *rucksack problem*)
- Posiadając zestaw elementów o pewnej wadze i wartości należy określić, które z nich wybrać, aby zmieściły się do plecaka o ograniczonej pojemności
]

.pull-right[
<div class="figure" style="text-align: center">
<img src="images/knapsack.png" alt="https://commons.wikimedia.org/wiki/File:Knapsack.svg" width="924" />
<p class="caption">https://commons.wikimedia.org/wiki/File:Knapsack.svg</p>
</div>
]

---
# Problem plecakowy

.pull-left[
- Istnieje zbiór `$I$` elementów
- Każdy element `$i = 1, ..., I$` ma wagę ( `$w_i$` ) oraz wartość ( `$c_i$` )
- Posiadamy plecak o pojemności `$W$`
- Cel - odkrycie takiego przypisania elementów do plecaka, aby uzyskać jak największą sumaryczną wartość
- Cel - jednocześnie nie można przekroczyć łącznej wagi `$W$`
]

---
# Problem plecakowy

.pull-left[
<div class="figure" style="text-align: center">
<img src="images/knapsack.png" alt="https://commons.wikimedia.org/wiki/File:Knapsack.svg" width="924" />
<p class="caption">https://commons.wikimedia.org/wiki/File:Knapsack.svg</p>
</div>
]

.pull-right[
Liczba elementów:
- `$I = 5$`

Ograniczenie (ang. *constraint*):
- `$W = 15$`

Wagi:
- `$w_1 = 12$`, `$w_2 = 2$`, `$w_3 = 1$`, `$w_4 = 1$`, `$w_5 = 4$`

Wartości:
- `$c_1 = 4$`, `$c_2 = 2$`, `$c_3 = 2$`, `$c_4 = 1$`, `$c_5 = 10$`
]

---
# Problem plecakowy

.pull-left[
Warianty:

- Każdy element jest dostępny tylko jeden raz lub jest dostępny wiele razy
- Ograniczenie tylko po wadze lub ograniczenie po wadze i objętości
- Maksymalizacja jednego aspektu (np. wartość) lub wielu aspektów (wartość i kwestie społeczne/przyrodnicze)
- Jeden plecak lub wiele plecaków
- Elementy są niepodzielne lub elementy mogą być podzielne (tzw. ciągły problem plecakowy)
]

---
# Problem plecakowy

.pull-left[
Przykład:

- Wybór inwestycji - elementy ( `$i=1,...,I$` ) to projekty inwestycyjne, wagi ( `$w_i$` ) to koszty projektów, a wartości ( `$c_i$` ) to zyski z projektów. Pojemność ( `$W$` ) to posiadane fundusze
- Wysyłanie kontenerów - elementy ( `$i=1,...,I$` ) to przedmioty, wagi ( `$w_i$` ) to ich objętość, a wartości ( `$c_i$` ) to zysk z ich sprzedaży. Pojemność ( `$W$` ) to pojemność konteneru
- Knapsack problem algorithms for my real-life carry-on knapsack - https://dev.to/victoria/knapsack-problem-algorithms-for-my-real-life-carry-on-knapsack-33jj
- ...
]

---
# Problem plecakowy

<div class="figure" style="text-align: center">
<img src="images/np_complete.png" alt="https://xkcd.com/287/" width="90%" />
<p class="caption">https://xkcd.com/287/</p>
</div>