Optymalizacja dyskretna (w tym algorytmy heurystyczne)

class: center, middle, inverse, title-slide

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

---

# Programowanie matematyczne

Typy programowania matematycznego:

- Optymalizacja (programowanie) liniowa (ang. *linear programming (LP); linear optimization*)
- Optymalizacja (programowanie) nieliniowa (ang. *nonlinear programming (NLP)*)

- Optymalizacja (programowanie) całkowitoliczbowa (ang. *integer programming*)
- Inne

Narzędzia:

- http://lpsolve.sourceforge.net/5.5/
- https://cran.r-project.org/package=lpSolve
- https://cran.r-project.org/web/views/Optimization.html
- https://coin-or.github.io/pulp/

---
# Formalizacja

- Jaki jest cel/są cele?
- Jakie decyzje trzeba podjąć?
- Jakie istnieją ograniczenia?
- Jak ocenić wpływ decyzji na cel/e?

---
# Formalizacja

- Jaki jest cel/są cele?  - **Kryteria. Funkcje celu**
- Jakie decyzje trzeba podjąć? - **Zmienne decyzyjne**
- Jakie istnieją ograniczenia? - **Ograniczenia. Przestrzeń rozwiązań dopuszczalnych**
- Jak ocenić wpływ decyzji na cel/e? - **Sposób obliczania funkcji celu**

---
# Zmienne ciągłe, dyskretne, binarne

- Zmienne ciągłe 
- Zmienne dyskretne - utrudnienie problemu (*Branch and Bound*)
- Zmienne binarne - utrudnienie problemu

---
class: inverse, left, bottom
# Programowanie liniowe

---
# Programowanie liniowe

- Przydatne w problemach optymalizacji zasobów:

- Przydzielenie odpowiednio ludzi i sprzętu, aby zminimalizować koszty
    - Zdecydowanie jakie produkty i w jakiej ilości wyprodukować, aby otrzymać największy zysk

---
# Przykład

https://brilliant.org/wiki/linear-programming/

- Fabryka produkuje śróbokręty i młotki. 
- Produkcja śróbokrętu kosztuje 2$ i trwa 3 godziny.
- Wyprodukowanie młotka kosztuje 4$ i trwa 2 godziny.
- Fabryka ma 220 dolarów i 150 godzin w tygodniu, aby wyprodukować te produkty.
- Jeśli każdy śróbokręt sprzedaje się za 6 dolarów i każdy młotek sprzedaje się za 7 dolarów, to ile każdego produktu powinno się produkować w tygodniu, aby zmaksymalizować zysk?

Jest to problem pasujący do programowania liniowego, bo:

1. Wszystkie zależności numeryczne mają charakter liniowy
2. Wartości zmiennych są ograniczone
3. Celem jest znalezionie wartości zmiennych, które maksymalizują pewien aspekt

---
# Przykład - formalizacja

- Jaki jest cel/są cele?  - **Kryteria. Funkcje celu**

- Maksymalizacja zysku

- Jakie decyzje trzeba podjąć? - **Zmienne decyzyjne**

- Określenie liczby wyprodukowanych młotków i śróbokrętów

- Jakie istnieją ograniczenia? - **Ograniczenia. Przestrzeń rozwiązań dopuszczalnych**

- 220 dolarów
    - 150 godzin

- Jak ocenić wpływ decyzji na cel/e? - **Sposób obliczania funkcji celu**

- Funkcja liniowa
    
---
# Przykład - relacje

Koszty produkcji a zasoby:

$$
2x + 4y \le 220
$$

Czas produkcji a dostępny czas:

$$
3x + 2y \le 150
$$

Inne ograniczenia (czasem oczywiste dla nas):

$$
x \ge 0 \\
y \ge 0
$$

---
# Przykład - relacje

.lc[
Razem:

$$
`\begin{cases}
2x + 4y \le 220 \\
3x + 2y \le 150 \\
x \ge 0 \\
y \ge 0
\end{cases}`
$$

]

.rc[
<div class="figure" style="text-align: center">
<img src="images/inequality-constraints.png" alt="https://brilliant.org/wiki/linear-programming/" width="90%" />
<p class="caption">https://brilliant.org/wiki/linear-programming/</p>
</div>
]

---
# Przykład - funkcja celu

- Wykonanie każdego śróbokręta kosztuje $2 i sprzedaje się go za $6. 
- Daje to zysk w wysokości $4 za śróbokręt.
- Wykonanie każdego młotka kosztuje 4$ i sprzedaje się go za 7$.
- Daje to zysk w wysokości 3$ za młotek.

Funkcja celu (funkcja zysku) może być zdefiniowana jako:

$$
p(x,y) = 4x + 3y
$$

---
# Przykład - funkcja celu

- `$P$` - maksymalny możliwy do uzyskania zysk:

$$
P = 4x + 3y
$$

- Rozwiązanie `$y$`

$$
y = -\frac{4}{3}x + \frac{P}{3}
$$

- Oznacza to, że `$x$` jest nachylony `$-\frac{4}{3}$` w stosunku do `$y$`

---
# Przykład - funkcja celu

.lc[
- Rozwiązanie `$y$`

$$
y = -\frac{4}{3}x + \frac{P}{3}
$$

- Oznacza to, że `$x$` jest nachylony `$-\frac{4}{3}$` w stosunku do `$y$`
]

.rc[
<div class="figure" style="text-align: center">
<img src="images/inequality-constraints2.png" alt="https://brilliant.org/wiki/linear-programming/" width="80%" />
<p class="caption">https://brilliant.org/wiki/linear-programming/</p>
</div>
]

---
# Przykład - funkcja celu

.lc[
Miejsca przecięcia czerwonych linii z niebieską powierzchnią określają możliwe rozwiązania

- Przecięcie (0, 55):  `$0 * 4 + 55 * 3 = 165$`
- Przecięcie (12, 48):  `$12 * 4 + 48 * 3 = 192$`
- **Przecięcie (20, 45): `$20 * 4 + 45 * 3 = 215$`**

]

---
# Przykład - funkcja celu

.lc[
Miejsca przecięcia czerwonych linii z niebieską powierzchnią określają możliwe rozwiązania

- Jedna z nich maksymalizuje możliwe rozwiązanie - wierzchołek na przecięciu (20, 45)

- W problemach liniowych optymalne rozwiązanie, będzie zawsze znajdować się na jednym z wierzchołków możliwego obszaru
]

---
# Przykład II

- Fabryka produkuje śróbokręty i młotki. 
- Produkcja śróbokrętu kosztuje 3$ i trwa 3 godziny.
- Wyprodukowanie młotka kosztuje 6$ i trwa 2 godziny.
- Fabryka ma 300 dolarów i 200 godzin w tygodniu, aby wyprodukować te produkty.
- Jeśli każdy śróbokręt sprzedaje się za 5 dolarów i każdy młotek sprzedaje się za 10 dolarów, to ile każdego produktu powinno się produkować w tygodniu, aby zmaksymalizować zysk?

---
class: inverse, left, bottom
# Metoda sympleksów

---
# Metoda sympleksów

- https://www.wikiwand.com/en/Simplex_algorithm

.pull-left[
*Simplex Algorithm*.
Procedura systematycznego sprawdzania wierzchołków w celu znalezienia optymalnego rozwiązania.

Idea:

- Zacznij w którymś krańcowym punkcie
- Obrót (ang. *pivot*) z jednego krańcowego punktu do leżącego krańcowego punktu obok (który nie daje gorszego wyniku)
- Powtarzaj do otrzymania optymalnego rozwiązania
]

.pull-right[
<div class="figure" style="text-align: center">
<img src="images/simplex3d.png" alt="https://pl.wikipedia.org/wiki/Plik:Simplex-method-3-dimensions.png" width="683" />
<p class="caption">https://pl.wikipedia.org/wiki/Plik:Simplex-method-3-dimensions.png</p>
</div>
]

---
class: inverse, left, bottom
# R

---
# R

.pull-left[
$$
p(x,y) = 4x + 3y
$$

$$
`\begin{cases}
2x + 4y \le 220 \\
3x + 2y \le 150 \\
x \ge 0 \\
y \ge 0
\end{cases}`
$$

- Ograniczenie do wartości nieujemnych jest domyślne
]

.pull-right[

```r
library(lpSolve)
obj_fun = c(4, 3)
obj_fun
```

```
## [1] 4 3
```

```r
constraints = matrix(c(2, 4, 3, 2), nrow = 2,  byrow = TRUE)
constraints
```

```
##      [,1] [,2]
## [1,]    2    4
## [2,]    3    2
```

```r
dir_fun = c("<=", "<=")
dir_fun
```

```
## [1] "<=" "<="
```

```r
rhs_fun = c(220, 150)
rhs_fun
```

```
## [1] 220 150
```
]

---
# R

```r
# Rozwiązanie (wartość)
result = lp("max", obj_fun, constraints, dir_fun, rhs_fun)
result
```

```
## Success: the objective function is 215
```

```r
# Rozwiązanie (liczba elementów)
result$solution
```

```
## [1] 20 45
```

---
class: inverse, left, bottom
# Przykłady

---
# Problem plecakowy

Integer Programming

.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[
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$`
]

.pull-right[

```r
library(lpSolve)
wartosci = c(4, 2, 2, 1, 10)
wagi = c(12, 2, 1, 1, 4)
W = 15
mod = lp(direction = "max",
          objective.in = wartosci,
          const.mat = rbind(wagi),
          const.dir = c("<="),
          const.rhs = c(W),
          all.bin = TRUE)

# Rozwiązanie
mod$solution
```

```
## [1] 0 1 1 1 1
```

```r
# Zysk
mod$objval
```

```
## [1] 15
```
]

---
# Problem plecakowy II

```r
library(dplyr)
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)
wartosci = c(4, 2, 2, 1, 10)
wagi = c(12, 2, 1, 1, 4)
n = length(wagi)
W = 15
MIPModel() %>%
  add_variable(x[i], i = 1:n, type = "binary") %>%
  set_objective(sum_expr(wartosci[i] * x[i], i = 1:n), "max") %>%
  add_constraint(sum_expr(wagi[i] * x[i], i = 1:n) <= W) %>%
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i]) %>% 
  filter(value > 0)
```

```
##   variable i value
## 1        x 2     1
## 2        x 3     1
## 3        x 4     1
## 4        x 5     1
```

---
# Inne

https://dirkschumacher.github.io/ompr/

---
class: inverse, left, bottom
# Dodatkowe informacje

---
# Dodatkowe informacje

- https://www.youtube.com/watch?v=haLz9CFRqQs
- https://cran.r-project.org/web/views/Optimization.html
- https://brilliant.org/wiki/linear-programming/
- https://towardsdatascience.com/linear-programming-in-r-444e9c199280
- https://upcommons.upc.edu/bitstream/handle/2117/78335/Modeling+and+Solving+Linear+Programming+with+R.pdf;jsessionid=6932D84F471E2CD236AD5400A5A08340?sequence=1
- https://www.youtube.com/watch?v=da7r3Qyn6ag
- https://www.esri.com/news/arcuser/0402/files/optimize.pdf
- https://gistbok.ucgis.org/bok-topics/linear-programming-and-gis