Math @ Work
Problemi di Ottimizzazione
Stefano Gualandi / @famo2spaghi / stefano.gualandi@gmail.com
... ma cosa vuol dire ottimizzare?
“Il raggiungimento del risultato più vantaggioso possibile con i termini dati o in relazione a un determinato fine.”
Ottimizzazione per la Treccani
“In matematica applicata, e in particolare nella teoria delle decisioni, Problemi di Ottimizzazione, le questioni attinenti alla ricerca dei criteri di scelta tra diverse opzioni o di determinazione del valore di particolari parametri, di solito riconducibile alla ricerca del massimo o del minimo di funzioni che costituiscono la rappresentazione matematica del problema”
In questo corso:
$$\begin{align}\min \;& f(x,y)& \\\; &g(x,y) \leq 0 \\ & x \in \mathbb{R}^n \\ & y \in \mathbb{Z}^p \end{align}$$
In questa parte del corso:
$$\begin{align}\min \;& c^Tx + d^Ty & \\\; & A x + G y \leq b \\ & x \in \mathbb{R}^n \\ & y \in \mathbb{Z}^p \end{align}$$
In cui $c\in \mathbb{R}^n, d \in \mathbb{R}^p, A \in \mathbb{R}^{n \times k}, G \in \mathbb{z}^{p \times k}$, $b \in \mathbb{R}^k$.Mixed Integer Linear Programming (MILP)
In forma espansa:
$$\begin{align}\min \;& \sum_{i \in 1 \dots n} c_i x_i + \sum_{j \in 1 \dots p} d_j y_j & \\\; & \sum_{i \in 1 \dots n} a_{ih} x_i + \sum_{j \in 1 \dots p} g_{jh} y_j \leq b_h \quad h = 1 \dots k \\ & x_i \in \mathbb{R} \quad i = 1 \dots n \\ & y_j \in \mathbb{Z} \quad j = 1 \dots p \end{align}$$
In questa parte del corso:
MATH @ WORk, uh?
Come si formula e risolve un Problema di Ottimizzazione?
$$\begin{align}\min \;& c^Tx + d^Ty & \\\; & A x + G y \leq b \\ & x \in \mathbb{R}^n \\ & y \in \mathbb{Z}^p \end{align}$$
Come risolve un Problema di Ottimizzazione al computer?
Usando Python...
... e un “solver”
Cos'é un “solver”?
$$\begin{align}\min \;& c^Tx + d^Ty & \\\; & A x + G y \leq b \\ & x \in \mathbb{R}^n \\ & y \in \mathbb{Z}^p \end{align}$$
Un software che dati $c, d, A, G, b$, o dimostra che il problema non é ammissibile, oppure cerca la soluzione ottima del problema.
Importanza dei Solver
Knapsack Problem
Canzoni = ["Roma-Bangkok", "Maria Salvador", "The Scientist",
"Sabato", "Gli Immortali", "With or Without You",
"Save Room"]
Rating = [3, 2, 5, 3, 5, 3, 2]
Spazio = [22.3, 25.3, 35.1, 22.9, 25.1, 12.3, 15.2]
Memoria = 70
Knapsack Problem
$$\begin{align}\max \;& cx & \\\; & A x \leq b \\ & x \in \mathbb{\{0,1\}}^p \end{align}$$
$c\quad$ é il vettore di Rating
$A\quad$ é la riga di Spazio
$b\quad$ é la Memoria a disposizione
$x\quad$ é la variabile decisionale sulle canzoni
Soluzione in Python
from gurobipy import *
m = Model()
m.modelSense = GRB.MAXIMIZE
X = {}
for i in range(len(Canzoni)):
X[i] = m.addVar(vtype=GRB.BINARY, obj=Rating[i])
m.update()
m.addConstr(quicksum(Spazio[i]*X[i]
for i in range(len(Canzoni))) <= Memoria)
m.optimize()
IPython Notebook
Obiettivi del corso
- Imparare le nozioni di base di Python
- Imparare a scrivere modelli di ottimizzazione
- Imparare a risolvere problemi di ottimizzazione
- Stimolare la vostra curiosità
- Stimolare la vostra curiosità
- Stimolare la vostra curiosità
Strumenti da utilizzare
- Un browser, possibilmente Google Chrome
- Anaconda Python (http://www.continuum.io)
- Come solver useremo Gurobi (http://www.gurobi.com)
Affronteremo i seguenti problemi:
- Il problema del commesso viaggiatore
- Il Vehicle Routing Problem
- La gestione ottima dei Data Center di Google
1. Il problema del commesso viaggiatore
DEMO: IPython Notebook
2. Vehicle Routing Problems
La gestione ottima dei Data Center di Google
Multi-Knapsack
$$\begin{align} \min & \sum_{i \in A} \sum_{j \in C} c_{ij} x_{ij} & \\ & \sum_{i \in A} r^1_j x_{ij} \leq cap^1_j & \forall j \in C \quad \mbox{RAM} \\ & \sum_{i \in A} r^2_j x_{ij} \leq cap^2_j & \forall j \in C \quad \mbox{CPU} \\ & \sum_{i \in A} r^3_j x_{ij} \leq cap^3_j & \forall j \in C \quad \mbox{Disco} \\ & x_{ij} \in \{0,1\} & \forall i \in A, \forall j \in C \\ \end{align} $$