Appunti di teoria Ricerca Operativa 2

formulazioni

Knapsack

assegnamento n persone -> m persone

Limiti inferiori o superiori: quando le variabili devono essere comprese in un insieme non convesso di valori richiesti.

• y ≥ x Nmin - y → y = 1 se x ∈ [min max]
• x ≤ Nmax ⋅ y → y = 0 altrimenti

costi fissi di attuazione: con funzione lineare al costo con salto in zero

economie di scala: generalizza i costi fissi di attuazione

Selettore ad insieme finito: Σxᵢ = 1 caso particolare dell’uso di variabili binarie

• > 1
• < 1

Unione di Vincoli (BIG M): quando va soddisfatta la condizione Ax ≮ b ed almeno un’altra tra le disponibili:

• aˢʸx ≤ 6 + M(1 - u)
• aˢʸx ≶ g + M u

distribuzione centri:

formulazioni

Knapsack

assegnamento n persone —> m persone

Limiti inferiori o superiori: quando le variabili devono essere comprese in un insieme non convesso di valori richiesti. x > Nmin - y y = 1 se x ∈ [min max] x < Nmax - y y = 0 altrimenti

costi fissi di attivazione: con funzione lineare il costo con salto in zero

economie di scala: generalizza i costi fissi di attivazione

Selettore ad insieme finito: Σ x_i = 1 caso particolare dell'uso di variabili binarie > 1 < 1

Unione di vincoli [BIG M]: quando va soddisfatta la condizione Ax >= b ed almeno un'altra tra le disponibili:

• a^T x ≤ 6 + M (1 - y)
• a’ ^T x ≤ 9 + M y

distribuzione centri:

rilassamenti lineari

min c^Tx{ Ax > b x > 0, intero

- l'eliminazione del vincolo di interezza comporta l'uso di un dominio più ampio, contenuto nel precedente.

Avendo _PL ottimo del rilassamento e più ottimo del problema originale, se _PL è intera, allora sarà ottima anche per il problema iniziale intero.

c^Tx^f_PL = _PL ≤ _PL perchè avendo un insieme più ampio, si hanno migliorpossibilità di ottimizzazione.

x^f intera → x^f ∈ X ∩ Z segue che_PL = c^Tx^f_PL = _PL

TEOREMA: dato s ∈ Rⁿ insieme di punti, indicando con conv(S) l'involucro convesso di S(=l'insieme più piccolo di punti che contiene S), allora conv(X) è un politopo Pi cui vertici sono tutti interi.

L' ciò comporta un ritorno di qualità del metodo al simposoper la risoluzione dei problemi.Prima non era applicabile nemmeno "arrotondando" le soluzionifrazionate all'intero più vicino.

rilassamento lagrangiano

min c^Tx { Ax > bC x > dx > 0, int

— → min c^Tx - λ^T (Ax-b){C x > dx > 0, intλ∈ R⁺

- Il fattore λ è un moltiplicatore lagrangiano postiuo se vincolo 0 comporta un abbassamento della funzione obiettivo = L'OTTIMO ESISTE.-b + Ax < 0 il valore dell'obiettivo si alza quindi = L'OTTIMO NON ESISTE.

TEOREMA: 1) La regione ammissibile risulta più ampia          2) La funzione obiettivo lagrangiana è un lower bound:            λ > 0 fissato, la soluzione ottima L(λ) risulta L(λ) ≤ _PL

branch and bound

CLASSICO

Algoritmo enumerativo che ottimizza la fase di enumerazione evitando di generare soluzioni a prescindere non ottime. Viene generato un albero decisionale con il rilassamento alla radice.

• Alla radice risolvo il rilassamento lineare. Se ho il vettore CT con una componente frazionaria faccio Branching generando un figlio destro (valore arrotondato per eccesso) ed un figlio sinistro (valore arrotondato per difetto).
• I vincoli di arrotondamento diventano vincoli del problema che contribuiranno a ridurre il P ammissibile.
• Ripeto il passo precedente finché smetto di fare branching (cioè avanso si ottiene una soluzione intera).

CRITERI DI FATHOMING: per la chiusura dei nodi (interruzione del branching).

1. Ottimalità: se la soluzione a quel nodo e' intera, non genero più figli.
2. Inammissibilità: il nodo va chiuso se è associato ad un poliedro vuoto.
3. Bounding: in un problema di minimizzazione, il nodo va chiuso se già si conosce un ottimo di valore minore. Questo perché continuare ad esplorare l'albero in profondità comporta un peggioramento dell'ottimo nel sottoalbero in questione.

Scheduling dei job per l'ottimizzazione combinatoria

• Ad ogni generico livello dell'albero di enumerazione, i nodi fratelli costituiscono una partizione delle soluzioni del nodo padre, ma per ogni coppia di fratelli non vi sono intersezioni! (anche se non e' condizione necessaria al funzionamento)
• Lateness Li:=ci-di. completamento ci: due date di < 0 anticipo > 0 ritardo
• METODO Earliest Due Date (EDD) : i job vengono ordinati per urgenza decrescente. Può comportare idle (inattività) in mancanza di dati sul rilascio.
• METODO PEDD Pre Emptive Due Date : per B&B 1[rj|Lmax. ogni figlio e' un modo diverso di iniziare una schedula.

IL VINCOLO RILASSATO E' LA NON INTERROMPIBILITA' DEI JOB IN CORSO! Per ogni istante t viene eseguito il job con urgenza maggiore tra quelli già rilasciati.

complessita' esponenziale unica tecnica che permette START BOUNDING CONVERGE SEMPRE!

matrici unimodulari

• Una matrice A di interi A di dimensioni mxn [m≤n] è detta unimodulare se ∀ sottomatrice B di dimensioni mxm quadrata, vale che det(B) ∈ {0, ±1}.
• La base B di A contiene k colonne e A, m-k colonne e [-I].

■Teorema: Sia A unimodulare, allora dato un vettore b di interi qualsiasi, il poliedro in forma standard

P = {x ≥ 0 | Ax > b} ha vertici interi.

Dimostro: sia x* vertice di P poliedro, allora ∃ base B ∈ A tc

x = [ B^-1b, 0 ] con B sottomatrice non singolare.

Questo implica che B^-1 intera → B^-1 b intero → x* intero.

unimodularità totale

• Una matrice A di termini interi di dimensioni mxn [m≤n] è detta TUM se ∀ matrice B contenuta in A di dimensioni kxk [k>1] vale che det(B) ∈ {0, ±1}.

■Teorema: Sia A matrice totalmente unimodulare, allora dato un vettore b intero qualsiasi, allora il poliedro P in forma canonica

P = {x ≥ 0 | Ax > b } ha vertici interi.

∃ vertice (x*, s*) [ s*=Ax*-b ] ∈ P con s variabili slack.

Se per assurdo non fosse così allora ∃ punti [x¹, s¹ ], [x², s² ] tali che

(x*, s*) = λ(x¹, s¹)+(1-λ)(x², s²) con λ < uλ > 0

Esisterebbe una combinazione convessa stretta che implicherebbe x* a non essere vertice.

Per ipotesi, A è TUM → A^-1 = [A_J, -I ] lo è altrettanto, ed (x*, s*) ∈ P.

Dal teorema segue che P ha vertici interi, tra cui anche (x*, s*).

TEOREMA DI VERIFICA DI UNIMODULARITA' TOTALE

Sia A matrice con A_ij∈{0,+-1} ∀i,j, e' TUM se si verifcano

1. ∃ riga/colonna A_i contendo ≤ 2 elementi ≠0;
2. ∃ partizione [I₁, I₂] delle righedi A tali che ogni colonna con 2 elementi non nulli, l' una su rigne ed insieme diversi se sono concordi nel segno.

Dimostro:

• Supponendo un minore di ordine k > 1 con det(A_k) ∈ {0, +-1} si verifcano

  1. ∃ A una colonna al teri
  2. ∃ A una colonna con elemento ≠0 A MENO DI PERMUTAZIONI si ha

  Ak = _{[... * ...: ...]} per induzione suilla rigne I₁ ∩ Q

  [... * ...:] det(A) = det(A_k) * det(A) = det(A_k)∈ {0, +-1}

• Sia I(A_k) l'insieme delle righe di A_k, ogni colonna ha esattamente 2 element + 0.

  ... dalla #2 si puo' dedurre che

  Q = A-[...] I₁∩Q ∑ rigne ∑I₁ - ∑ rigne I₂ = 0

quindi si dimostra una dipendenza lineare.

DIMOSTRARE CHE LA MATRICE DI UN GRAFO BIPARTITO E' TUM:

cutting planes

Piano vincolo

• TAGLIO: dato x^e∈P, si dice taglio una disequazione del tipo a^Tx ≤ a₀ tale che soddisfi tutte le soluzioni intere e che a^Tx^o sia violata perchè non soddisfa l'ottimo frazionario.

Il problema di separazione è il problema di individuare il taglio del tipo a^Tx ≤ a₀ che separi il punto x* da tutti gli alti punti x∈X.

ALGORITMO CUTTING PLANES

L₀ risolvo il rissamento lineare. Sia x^o* l'ottimo di base trovato.

L_i while x^o* frazionario do

1. begin

2. L₀ risolvo il problema di separazione a^Tx ≤ a₀ trovando un taglio

3. L₀ aggiungo il vincolo a^Tx+ x_n+1-a₀al rilassamento

4. L₁ risolvo il rissamento nuovo.

end

BRANCH AND CUT: qualora i tagli vengono individuati bene, il metodo dei cutting planes può essere unito all'algoritmo branch and bound classico.

Scritto su un po' di vincoli per tenente traccia. Per ogni nodo:

• risolvo il rilassamento lineare

• aggiungo un branching su x^nl e risolvo

Chvatal

La clusura n-esima di Chvatal rappresenta la formulazione ideale per il problema considerato.

utile avevano disponibile |M| = |V|/2

TEOREMA: Max Flow-Min Cut

Dato G(V,E) orientato e capacitato e dati 2 nodi

source e toll ε V, devo trovare il massimo flusso con il taglio minimo.

cio' e' garantito dall'algoritmo di Ford-Fulkerson.

VERTEX COVER:

Insieme dei nodi C tale che ogni arco del grafo abbia almeno un estremo

nel cover C = { (u,v) ∈ E | u ∈ C v ∉ C }

TEOREMA DI KÖNIG

dato un grafo bipartito G=(U,V,E)=(V₁,V₂,E) si ha

max |M| = min |C| dove M e' matching e C e' cover.

• dimostro ①: costruisco un al re il flusso dal grafo iniziale Allora su G esiste un |M| = 2
• Ponendo da 1 il flusso su ogni arco al M, si verifica essere un flusso ammissibile (V nodo accoppiato esce il flusso che entra)
• dimostro ②: su G vertex cover C allora 3 taglio capacitao |C| Considerando un flusso di valore 2 intero, e gli archi su V₂. Per come sono definite le capacita' non esistono 2 archi con nodi in comune.
• Segue che gli archi originali attraversati da flusso sono |M| = 2.
• dimostro ②b: Suppongo taglio di capacita' 2 auto a. Segue che gli archi e OA devono essere Quelli artificiali perché gli altri hanno capacita' 0. Costruendo il vertex cover da O noto che ogni arco originale definisce un certo cammino S_B i –→ w i –→ t. Ma (S_B i) v (w i, t) e a quindi per definizione di vertex cover C e' cover |C | = 2.

TEOREMA:

Sia M matching sul grafo G e sia P un cammino aumentante, allora la differenza

simmetrica tra P e M e' ancora matching ma aura' cardinalita' |M| + 1.

• dimostro 1: mostro che M e' ancora matching
• V nodo c’e’ l’arco che incide quel nodo? · nodi non toccati da P : invariati · nodi intermeali a P : indicano nuovamente un arco · nodi estremi: ora dopo P sono accoppiati
• linotre: P ha lunghezza (2k+1) con k archi di M e k+1 archi ∉ M.
• → : |M| + 1 – |k + 1