Metodi e modelli di ottimizzazione discreta

Appunti molto dettagliati di tutte le lezioni del corso di MMOD1.
Gli appunti coprono tutti gli argomenti del corso che si dividono principalmente in formulazioni, Bound per funzione obiettivo, Algoritmi ed infine dei cenni di complessità computazionale.
Nello specifico vengono trattate le formulazioni dei problemi di Matching, Minimo Node Cover (MNC), Max Indipendent Set (MIS), Max Clique, Assegnamento, Set Covering/Partitioning/Packing, Scheduling, Bin Packing, Knapsack binario e intero e viene spiegato come scrivere i vincoli per definire delle formulazioni.
La parte che riguarda i bound tratta : Rilassamento Lineare, Bound tramite teoria della dualità, Dualità tra MNC e MM, Rilassamento combinatorio e Rilassamento Lagrangiano.
Gli algoritmi si dividono in : Algoritmi Esatti (Totale Unimodularità (TUM), Branch & Bound, Programmazione Dinamica per TSP e Knapsack); Algoritmi approssimati per TSP e Algoritmi euristici (Greedy per Knapsack e Set Covering, Ricerca Locale per TSP e Knapsack e Ricerca Tabù).

Esame Metodi e Modelli di ottimizzazione discreta

Facoltà Ingegneria

Dal corso del Prof. Nicoloso Sara

Università Università degli Studi di Roma Tor Vergata

Publisher edoardo.musche

A.A. 2022-2023

106 pagine

1 download

Appunti esame

Vota 3,5 / 5 (2)

Scarica

Estratto del documento

INDICE APPUNTI

Knapsack Binario P.3
Max Matching P.6
Min Node Cover P.8
Max Indipendent Set P.9
Max Clique P.10
Assegnamento P.11
Vincoli e Exor P.13
Set Covering P.21
Set Partitioning P.22
Set Packing P.23
Regione non Convessa P.25
Scheduling P.27
Attivazione y nella f.o. P.33
Bin Packing P.34
Diversi tipi di Vincoli P.37
Knapsack Intero P.41
Poliedri e Formulazioni P.42
Combinazione Convessa P.45
Bound per la f.o. P.47
Rilassamento Lineare P.51
Bound tramite Dualità P.52
Dualità MM e MNC P.53
TSP e Rilassamento Combinatorio P.58

Rilassamento Lagrangiano P.61

Algoritmi

Totale Unimodularità P.64
Branch & Bound P.65
Programmazione Dinamica P.70
PD per Knapsack P.73
PD per TSP P.74

Algoritmi Approssimati

TSP 2-Approx P.78
TSP 3/2-Approx (Christofides) P.82

Algoritmi Euristici

Greedy Knapsack Binario P.83
Greedy Set Covering P.85
Ricerca Locale P.87
Ricerca Locale TSP P.88
Ricerca Locale TSP Simmetrico P.89
Ricerca Locale Knapsack P.93
Ricerca Tabù P.94

Complessità Computazionale

Problemi in forma di Decisione P.96
Ricerca Binaria P.97

3x₁ + 5x₂ → max. 3x₁ = 2 → 2.5

x₁, x₂ ε ℤ {0,1}

x₁, x₂ ε ℚ ≤ 5

{0,2} ε ℤ = r

{x₁ = 2.5, x₂ = 5} → ε ℚ ≠ ℤ

→ la variabile x₁ ci dicese contribuisce o menoalla j-esima coefficc.di quanto contribuisce

Possiamo anche utilizzare una variabile y_i:

y_i = {0₂, x_i ε { → 1x_i ε {

t.c. x₁ + y₂ = 1x₂ + y₂ = 1logicamente opposta

x₁ e y_i paglo variabili complementari

Posso dire che:max Z = x₁ - y₂ e x₁ = 1 - y₂

max Z = ∞ - y₂ + 5y₂ (*)

Prova che mi permette di valutare gli Zeri:quando le variabili non annullano il coefficiente

[2 - 2y₂ = 0], Σ(1 - x_i) = 1.0

→ r = 2y₂ + 1 = 2y₂ intera

dover porti la transizione

Max Z = -5y₂ + 9x₂ ε S,2

Utilità: se ci fossero più utilità dovrei decidere spesso toccare, mentre posta passivo da zero e escludo quanto aggiungere

Calcolando obiettivo o elemciottengo la stessa fogl.

… 8y₂ + t_ij

Mi dice che per rispettare il vincolo devo lasciare degli oggetti, t.c.la loro fortuna ma almeno capacità totale = 2 dove Z è la differenzatra il peso dei 2 oggetti x_i + 2.0 meno la capacità: 20 - 2y₂

Se stolt fosse di MCivi avrebbe la soluzione banale vuota che rispetta il vincolo.

La scelta degli oggetti mi definisce gli insiemi S ⊂ r o ℤ ovvero una bipartizionein modo che S ⊂ 3 − A con S elementi preli 3 − basement

Max Matching:

Dato: Grafico G = (V, E)
Ora bisogna trovare → one vettore di archi ("link")su ogni nodo incida ≤ con un arco di M

Informazione:|M| è sia MAX

Insieme Universo E (archi) → definisco una variabile y arco di E

_{x_e} = {0 ⊂ R em

|E| = |7|

→ x → |(2,1,0,1,3,0,2)

|M| = |6| = 0°° "i" nei vettori di incidenza

|M| = Σ_{x = R, z}

3 .0 . max Z = ∑ |E| → .Zo . → Devo prendere + Archi possibili

voglio prendere il minimo numero di archi t.c. ogni lodo ha almeno un arco incidente

per capire se utilizzare A o A’ basta guardare se la soluzione <Z nei lodi o sugli archi

Assegnamento:

Dati: n¹ persone, m¹ lavori

Costo c_i,j t.c. se la persona i fa il lavoro j, i=1,...,n; j=1,...,m

tutti possono fare tutto

Trovare: chi fa cosa → abbinare persone e lavori

minimizzato il costo complessivo e ogni lavoro va portato a termine

e ogni operaio deve fare qualcosa (lineare (non è compatto))

grafo bipartito persone - lavori:

completo, t.c. incideno tutti i lavori

Dato G bipartito completo nei pesato sugli archi

Trovare: un matching perfetto (c.l.)

- ogni nodo P_i incida un arco di M
- ogni nodo L_j incida un arco di M

imbro le soluzioni perchè non avrebbe senso prendere persone per uno stesso lavoro se devo minimizzare
Potre servire come:
dato G bipartito completo = (P∪L,E)
pesato sugli archi c_ij ≥ 0 ∀ (i,j) ∈ E

→ Trovare un matching perfetto:

t.c. min ∑ C_ij
(i,j)∈M

x_ij = {1 se (i,j)∈M
0 se pi fa lavoro j e (i,j)∈E
0 altrimenti

f.o.
min z = ∑ C_ij * x_ij
(i,j)∈E

∑ X_ij = 1, j = 1,...,m → tutti i lavori devono essere svolti da qualche persona
∑ X_ji = 1, i = 1,...,m → ogni lavoratore deve svolgere solo un lavoro

variabili: x ∈ {0,1}³

x ∈{0,1}³²

La y mi permette di generare 2 cui e separare i 2 vincoli che non potrebbero coesistere, non posso risolvere ∑ x_i ≠ 3, perciò non posso introdurlo nel simplice.

s.t.) {y₂ = {j|insieme di cardinalità 2 o 4}}

s.t. ∑ x_i ≤ 2 - My e ∑ x_i ≥ 2 + My

x ∈ {0,1}ⁿ y ∈ {0,1}

x_i = 2, i = 1 a 3, n = con z.

∑ x_i ≥ 4 + M(1-y)

.y = 0 → ∑ x_i z ≤ 2 → ∑ x_i ≥ 2 → 4 + M → z = 0 → 2 ∑ x_i = 4 + M

Diventano insufficienti

∑ x_i = z

Non possiamo utilizzare l'uguaglianza perché non varrebbe per entrambi i casi. Pa'øvale 2 → z = 4

.y = 2 , __∑ x_i z ≥ 2M - 4 = o = ∑ x_i = 2 + M = ∞

∑ x_i z ≥ 4

∑ x_i ≤ 4

∑ x_i = 4

Potrei risolverlo anche così:

j.t.: ∑ x_i = 2 + 2t

x ∈ {0,1}ⁿ t ∈ {0,1}ⁿ

s.t.: y₂ = {sottinsiemi che escludo g elementi}

A = {Q₂, Q₃...Q_m} {m,7,4}

x ∈ A ⊆ X ⊆ ∃ Q : x

2 + x = A ⊆ X ⊆ ∃ Q : x

Vettore indue\nta del \ga{1}\e

min

max

z = ∑ x_i c_i

(∑ x) = ∑ c_i

Per escludere gli elementi blusa contare gli Zeri

Devo considerare le tensione (1-x) per ogni variabile

Set Covering

Dati: un insieme A = {a₁, a₂, ..., a_m} di m elementicosti c_i ≥ 0 i = 1, ..., muna famiglia ℱ = {A₁, A₂, ..., A_n} A_i ⊆ A; i = 1, ..., m

Trovare:un sottoinsieme X di A non necessariamente della famiglia ℱ

t.c.:costo complessivo di X sia min → ∑c_ivenga scelto almeno un elemento da ogni A

Es.Variabili: X_i = {0,1}, i ∈ XVettore di incidenza nel generico sottoinsieme,insieme universale A

f.o.: min z = ∑_i=1ⁿ c_i X_i

(Vincoli) s.t.x₁ + x₃ + x₉ ≥ 2x₃ + x₄ + x₇ + x₉ ≥ 2x₃ + x₆ ≥ 2x₀ ≥ 2

x_i ∈ {0,1}³⁰

Formulazione Vettoriale:

min z = C xs.t. BX ≥ 2x ∈ {0,1}³

B matrice m × n → Matrice dei Coefficienti

x₁ x₂ x₃ x₄ x₅ x₆ x₇ x₈ x₉ x₁₀B = | 1 0 1 0 0 0 0 0 0 | | 0 0 1 1 0 0 1 0 0 | | 0 0 0 0 0 0 0 0 1 | ...

Le colonne si dicono in quanti sottoinsiemi si trovano i diversi elementiLa somma per colonna mi dice in quanti sottoinsiemi si trova ogni elementoLe righe sono vettori di incidenza del sottoinsieme corrispondente

Anteprima

Vedrai una selezione di 23 pagine su 106