A Programmazione Lineare Intera

Ricerca Operativa e Logistica
Dott. F.Carrabs e Dott.ssa M.Gentili
Lezione 8:
Introduzione alla Programmazione
Lineare Intera
Problemi di Programmazione
Lineare Intera (PLI)
min z = c x
T
Ax ≤ b (1)
x≥0
x ∈Z
(2)
n
dove Z rappresenta l’insieme degli interi
Indichiamo con ௔ = { ∈ ௡ : ≤ , ≥ 0}
Programmazione Lineare Intera (Mista)
(3)
(2)
X
(1)
1
6
A
-2
-3
B
I Problemi di PLI sono in generale più difficili da risolvere
rispetto ai problemi di PL. Nell’analisi dei problemi di PLI
cercheremo di chiarire:
- Proprietà fondamentali della PL che non valgono per
la PLI
- Quando possiamo risolvere un problema di PLI con le
tecniche della PL
Insieme convesso
Def: Un insieme S è convesso se e solo se dati due punti, x,y ∈S
ogni punto z generato come loro combinazione convessa:
λ ∈ [0,1]
z = λx + (1 − λ ) y
è tale che z∈ S
z
x
x
y
z
y
Funzione convessa
Ottimi globali ed ottimi locali
min ݂(‫)ݔ‬
‫ܴ ⊆ ܵ ∈ ݔ‬௡
Ottimo globale di :
punto ∗ ∈ ∶ ∗ ≤ ∀ ∈ Ottimo locale di :
punto ∗ ∈ ∶ ∗ ≤ ∀ ∈ (; )
- Ogni ottimo globale è anche ottimo locale, in
generale non è vero il vice versa
- Ci sono però casi particolari in cui tutti gli ottimi
locali sono anche ottimi globali
Teorema 1
Sia : → una funzione convessa, e sia S un insieme
convesso ogni ottimo locale di f(x) è anche ottimo
globale
Dim.
Ottimi globali e locali nella PL
min z = c x
T
Ax ≤ b (1)
x≥0
(2)
= ் è una funzione convessa
l’insieme P= {x: Ax≤b, x≥0}, è un insieme convesso
Quindi vale il Teorema 1 per problemi di PL
Altri due risultati importanti per la PL…
Teorema 2.
Se un problema di PL ammette ottimo finito allora
ammette una soluzione basica ottima
Teorema 3.
Corrispondenza tra soluzioni basiche ammissibili e
vertici del poliedro di ammissibilità.
Il simplesso valuta se una soluzione basica è un
ottimo locale e quindi per il teorema 1 trova
anche un ottimo globale
Per la PLI:
L’insieme di ammissibilità di un problema di PLI
non è convesso quindi non è possibile applicare il
teorema 1 e fermarsi pertanto ad un ottimo
locale
E’ possibile in qualche modo continuare a sfruttare
le proprietà della PL?
Se rilassiamo il vincolo di interezza….
Restituiamo convessità alla regione di ammissibilità,
però applicando il simplesso potremmo trovare una
soluzione non intera ( cioè non ammissibile per il
problema originario) che però ci fornisce informazioni
sulla soluzione ottima del problema di PLI.
In generale valgono i seguenti risultati…
Sia ௉௅ூ il valore ottimo del problema di PLI:
௉௅ூ = {min ் : ≤ , ≥ 0, ∈ ௡ }
Sia ௉௅ il valore ottimo del problema di PL ottenuto da
PLI rilassando il vincolo di interezza:
௉௅ = {min ் : ≤ , ≥ 0, ∈ ௡ }
௉௅ ≤ ௉௅ூ
Se la soluzione ottima ௉௅ è ammissibile per PLI allora è
anche soluzione ottima per PLI.
Dim.
௉௅ ≤ ௉௅ூ
௉௅ è ammissibile per PLI ௉௅ூ ≤ ் ௉௅ = ௉௅
Possibile algoritmo (ingenuo)
per problemi di PLI
Possiamo fare di meglio?
Formulazione ideale
- Dato un problema di PLI, è possibile definire
diverse formulazioni equivalenti
- I corrispondenti rilassamenti continui non sono
però equivalenti
Esiste una formulazione ideale per il problema
di PLI in esame?
Consideriamo il seguente esempio
max ‫ݔ‬ଵ + ‫ݔ‬ଶ
max ‫ݔ‬ଵ + ‫ݔ‬ଶ
1
7
ଵ + ଶ ≤
2
4
1
7
ଵ + ଶ ≤
2
4
1
7
ଵ + ଶ ≤
2
4
7
1
ଵ + ଶ ≤
4
2
ଵ , ଶ ≥ 0 interi
ଵ , ଶ ≥ 0
Programmazione Lineare Intera (Mista)
max ଵ + ଶ
1
7
ଵ + ଶ ≤
2
4
1
7
ଵ + ଶ ≤
2
4
ଵ , ଶ ≥ 0
max ଵ + ଶ
1
7
ଵ + ଶ ≤
2
4
1
7
ଵ + ଶ ≤
2
4
ଵ , ଶ ≥ 0 interi
A
௔ = { 0,0 , 0,1 , 1,0 , (1,1)}
Programmazione Lineare Intera (Mista)
max ଵ + ଶ
ଵ ≤ 1
ଶ ≤1
max ଵ + ଶ
ଵ ≤ 1
ଶ ≤1
ଵ , ଶ ≥ 0 interi
ଵ , ଶ ≥ 0 interi
Programmazione Lineare Intera (Mista)
max ଵ + ଶ
ଵ ≤ 1
ଶ ≤1
max ଵ + ଶ
ଵ ≤ 1
ଶ ≤1
ଵ , ଶ ≥ 0 interi
ଵ , ଶ ≥ 0 interi
Programmazione Lineare Intera (Mista)
-
-
-
Abbiamo considerato una nuova formulazione del problema
che ci ha permesso di descrivere lo stesso insieme di punti
ammissibili per il problema di PLI
Se analizziamo il rilassamento continuo del problema di PLI
considerando le due diverse regioni di ammissibilità,
otteniamo dei diversi lower bound alla soluzione ottima del
problema di PLI
La seconda formulazione ci permette di ottenere un bound
migliore
In particolare, la nuova descrizione dell’insieme di
ammissibilità è tale che i vertici del poliedro dei vincoli
hanno coordinate intere
In termini generali: abbiamo definito una descrizione
dell’involucro convesso (o chiusura convessa) dell’insieme di
ammissibilità del problema di PLI
Chiusura convessa
Dato un insieme T, la chiusura convessa di T,
indicata con conv(T), è il più piccolo insieme
convesso contenente T.
Programmazione Lineare Intera (Mista)
Programmazione Lineare Intera (Mista)
Si consideri il seguente problema di PLI:
் : ∈ ௔
dove: ௔ = { ∈ ௡ : ≤ , ≥ 0}
È possibile dimostrare che:
- è sempre possibile trovare una matrice A’ ed un vettore b’ tali
che: ௔ = ∈ ௡ : ᇱ ≤ ᇱ , ≥ 0
- Il problema ் : ∈ ௔ ammette soluzione se e solo se il
problema ் : ∈ (௔ ) ammette soluzione
- Ogni soluzione ottima di ் : ∈ ௔ è soluzione ottima di
் : ∈ (௔ ) - Esiste almeno una soluzione ottima (di base) di
் : ∈ (௔ ) che è anche soluzione ottima di
் : ∈ ௔
Programmazione Lineare Intera (Mista)
݉ܽ‫ݔ ் ܿ ݔ‬: ‫ܼ ∈ ݔ‬௔
݉ܽ‫ݔ ் ܿ ݔ‬: ‫ܼ(ݒ݊݋ܿ ∈ ݔ‬௔ )
Entrambi i problemi hanno soluzione in questo caso
Programmazione Lineare Intera (Mista)
݉ܽ‫ݔ ் ܿ ݔ‬: ‫ܼ ∈ ݔ‬௔
݉ܽ‫ݔ ் ܿ ݔ‬: ‫ܼ(ݒ݊݋ܿ ∈ ݔ‬௔ )
Se la funzione obiettivo è max ‫ݔ‬ଵ + ‫ݔ‬ଶ entrambi i problemi
hanno soluzione ottima (1,1)
Programmazione Lineare Intera (Mista)
݉ܽ‫ݔ ் ܿ ݔ‬: ‫ܼ ∈ ݔ‬௔
݉ܽ‫ݔ ் ܿ ݔ‬: ‫ܼ(ݒ݊݋ܿ ∈ ݔ‬௔ )
Se la funzione obiettivo è max ‫ݔ‬ଵ
Ottimo in (1,0) e (1,1)
Ottimo è l’intero segmento tra (1,0) e
(1,1). Esiste comunque una soluzione
ottima basica che è ottima che per il
problema PLI iniziale.
se conoscessimo la matrice ′ ed il vettore ′ potremmo
risolvere il problema di PLI con regione di ammissibilità
௔ , risolvendo il problema sull’insieme di ammissibilità
(௔ )
In molti casi tuttavia (௔ ) non è noto
In altri casi (௔ ) è noto ma è formato da un
numero esponenziale di vincoli, il che può rendere
inefficiente la risoluzione del problema su (௔ )
In altri casi (௔ )coincide con il rilassamento
lineare di ௔
Quando (ࢇ )coincide con il rilassamento
lineare di ࢇ ?
௔
Quando (ࢇ )coincide con il rilassamento
lineare di ࢇ ?
௔ (rilassamento lineare)
Quando (ࢇ )coincide con il rilassamento
lineare di ࢇ ?
(௔ )
Quando (ࢇ )coincide con il rilassamento
lineare di ࢇ ?
Quando (௔ ) ≡ ௔ ?
I problemi di PLI per cui si verifica questa condizione sono importanti
poiché sono molto più semplici da risolvere rispetto agli altri problemi
di PLI, infatti basta risolvere il loro rilassamento lineare.
Matrici totalmente unimodulari
Proprietà
Come riconoscere se una matrice e TU?
Esempio
Corollario
Esempio
Altro corollario
Teorema
… in particolare…
Esempio
Poiché ଷ è TU e ଷ è un vettore di
interi, il problema di PLI può essere
risolto semplicemente risolvendone il
rilassamento lineare
Il problema dell’assegnamento
Data una matrice quadrata ௜௝ di dimensione n si vuole
determinare un assegnamento di righe a colonne in modo tale
che il costo dell’assegnamento sia minimizzato.
Esempio: Assegnamento di lavori (righe) a macchine (colonne),
l’elemento ௜௝ della matrice corrisponde al costo che si paga per
assegnare il lavoro i alla macchina j
Il problema dell’assegnamento:
Formulazione
Il problema dell’assegnamento:
Formulazione
La matrice A dei vincoli è TU, quindi il problema può essere risolto
utilizzando il rilassamento continuo.
Il problema del matching
Il problema dell’assegnamento è un caso particolare di un
problema generale definito su grafi, noto come il problema di
matching:
Dato un grafo G=(V,E) non orientato, e pesato sugli archi.
Selezionare un sottoinsieme M di archi tali che:
- ogni nodo del grafo ha al più un arco incidente
- la somma dei pesi degli archi selezionati sia massima
Esempio
Un matching di cardinalità massima
2
2
4
4
1
1
5
5
3
3
2
Un possibile matching
4
1
5
3
Matching perfetto
Dato un grafo G=(V,E) non orientato, e pesato sugli archi.
Selezionare un sottoinsieme M di archi tali che:
- ogni nodo del grafo ha ESATTAMENTE un arco incidente
- la somma dei pesi degli archi selezionati sia massima (o
minima)
G=(V,E) è un grafo bipartito con ଵ e ଶ di uguale cardinalità
Matching perfetto = assegnamento
Esempio: Assegnamento di lavori (righe) a macchine (colonne),
l’elemento ௜௝ della matrice corrisponde al costo che si paga per
assegnare il lavoro i alla macchina j
lavori
macchine
1
1
1
1
2
2
2
2
3
3
3
3
Il problema del matching perfetto
La matrice A dei vincoli è la matrice di incidenza del grafo
bipartito non orientato che è TU, quindi il problema può essere
risolto utilizzando il rilassamento continuo.
Matching su grafi bipartiti
1
1
(௜,௝)
2
2
௜௝ ≤ 1∀ ∈ 3
3
max ௜௝ ௜௝
௝∈ி(௜)
௜௝ ∈ {0,1}
4
max ௜௝ ௜௝
(௜,௝)
௜௝ ≤ 1∀ ∈ ௝∈ி(௜)
0 ≤ ௜௝ ≤ 1
Se il grafo contiene cicli dispari….
2
3
1
maxଵଵ ଵଵ +ଵଶ ଵଶ + ଶଷ ଶଷ
ଵଶ + ଵଷ ≤ 1
ଵଶ + ଶଷ ≤ 1
ଵଷ + ଶଷ ≤ 1
0 ≤ ଵଶ ≤ 1
0 ≤ ଵଷ ≤ 1
0 ≤ ଶଷ ≤ 1
Se il grafo non è bipartito,
la matrice non è TU e
quindi ௔ ≠ ௔
1
ଵଶ =
2
1
ଵଷ =
2
1
ଶଷ =
2
Se il grafo contiene cicli dispari….
bisogna aggiungere delle disequazioni
௜,௝ ∈ா(௎)
−1
௜௝ ≤
∀ ⊆ : = 2 + 1, = 1,2, …
2
maxଵଶ ଵଶ +ଵଷ ଵଷ + ଶଷ ଶଷ
ଵଶ + ଵଷ ≤ 1
ଵଶ + ଶଷ ≤ 1
ଵଷ + ଶଷ ≤ 1
0 ≤ ଵଶ ≤ 1
0 ≤ ଵଷ ≤ 1
0 ≤ ଶଷ ≤ 1
ଵଶ + ଵଷ + ଶଷ
3−1
≤
=1
2
2
3
1
1
ଵଶ =
2
1
ଵଷ =
2
1
ଶଷ =
2
2
3
1
4
maxଵଶ ଵଶ +ଵଷ ଵଷ + ଵସ ଵସ + ଶଷ ଶଷ + ଷସ ଷସ
ଵଶ + ଵଷ + ଵସ ≤ 1 nodo 1
ଵଶ + ଶଷ ≤ 1
nodo 2
ଵଷ + ଶଷ + ଷସ ≤ 1 nodo 3
ଵସ + ଷସ ≤ 1
nodo 4
ଵଶ + ଵଷ + ଶଷ ≤ 1 U={1,2,3}
ଵଶ + ଵସ ≤ 1
U={1,2,4}
ଶଷ + ଷସ ≤ 1
U={2,3,4}
ଵଷ + ଵସ + ଷସ ≤ 1 U={1,3,4}
0 ≤ ௜௝ ≤ 1∀ , ∈ Formulazione generale
max ௜௝ ௜௝
(௜,௝)
௜௝ ≤ 1∀ ∈ Degree-constraints
௝∈ி(௜)
௜,௝ ∈ா(௎)
−1
௜௝ ≤
∀ ⊆ : = 2 + 1, = 1,2, …
2
0 ≤ ௜௝ ≤ 1
Odd-set constraints
Non- negativity constraints
L’involucro convesso del politopo dei matching su un qualunque grafo G è
descritto da questo insieme di disequazioni
Altre classi di problemi di PLI
particolari:
-
Problemi di flusso si grafi (min cost flow, max
flow, cammini minimi)
Minimum Spanning Tree
Traveling Salesman Problem (TSP)
Vehicle Routing Problems
L’albero di copertura di costo
minimo
Subtour elimination formulation
Cutset formulation
Quale delle due formulazioni è migliore?
Abbiamo visto:
Talvolta l’involucro convesso è descritto da
un numero finito di vincoli possiamo
applicare il simplesso per risolvere il
problema di PLI
Talvolta l’involucro convesso è descritto da
un numero esponenziale di vincoli algoritmi ad hoc oppure metodi risolutivi per
problemi di PL a grandi dimensioni
Altrimenti…
Possiamo studiare altri rilassamenti della
formulazione di PLI per ottenere dei bound alla
soluzione ottima
Applicare algoritmi esatti (Branch&Bound,
Branch&Cut, Branch&Prize, Programmazione
Dinamica)
Applicare algoritmi ad approssimazione garantita
Applicare algoritmi euristici e/o metaeuristici per
ottenere una buona soluzione ammissibile