Definizione: Un vettore y∈ℜ

Parte IV:

Rafforzamento di formulazioni e

algoritmo dei piani di taglio

Nozioni di geometria

Definizione: Un vettore y∈ℜ

è combinazione conica dei vettori {x

,…,x

} se esistono k coefficienti reali λ

, …,λ

tali che y = Σ ^λ

x

, con λ

> 0, per ogni i = 1,…,k.

k i = 1

Definizione: Un vettore y∈ℜ

è combinazione affine dei vettori {x

,…,x

} se esistono k coefficienti reali λ

, …,λ

tali che y = Σ ^λ

x

, con Σ ^λ

_{= 1.}

k

i = 1 k

i = 1

Definizione: Un vettore y∈ℜ

è combinazione convessa dei vettori {x

,…,x

} se esistono k coefficienti reali λ

, …,λ

tali che y = Σ ^λ

_x

_,

con Σ ^λ

= 1 e λ

> 0, per ogni i = 1,…,k.

k

i = 1 k

i = 1

Nozioni di geometria

Definizione: Dato un insieme S ⊆ ℜ

, l’involucro convesso di S, conv(S), è l’insieme di tutti i vettori ottenibili come combinazione convessa di sottoinsiemi finiti di vettori di S.

Definizione: Dato un insieme convesso S, un vettore y∈S si dice estremo se e solo se esso non è ottenibile come combinazione convessa di altri vettori in S.

Definizione: Un poliedro P = {x∈ℜ

: Ax < b} è un insieme convesso

con un numero finito di punti estremi detti vertici di P.

Nozioni di geometria

Definizione: Una disequazione a

x < α è valida per il poliedro P = {x∈ℜ

: Ax < b} se e solo se P ⊆ {x∈ℜ

: a

x < α}, ovvero se e solo se la disequazione è soddisfatta da tutte le soluzioni ammissibili del sistema Ax < b (diremo che a

x < α è implicata dal sistema Ax < b).

Definizione: Una disequazione valida a

x < α definisce una faccia F = P ∩ {x∈ℜ

: a

x = α}. L’insieme {x∈ℜ

: a

x = α} è detto iperpiano di supporto di F.

Ogni faccia di un poliedro è essa stessa un poliedro.

Definizione: La dimensione di un poliedro P, dim(P), è data dal massimo numero di vettori affinemente indipendenti appartenenti a P meno uno.

Data una faccia F di P, risulta sempre dim(F) < dim (P).

Se dim(F) = dim(P), F è detta faccia impropria di P.

Se dim(F) = dim(P) – 1, F è detta faccia massimale di P.

Se dim(F) = 0, F coincide con un vertice di P.

Nozioni di geometria

La rappresentazione Ax < b di un poliedro P non è univocamente determinata. Infatti, è sempre possibile aggiungere alla rappresentazione nuove disuguaglianze valide per P, ottenute come combinazione conica delle disequazioni del sistema Ax < b, senza modificare la regione ammissibile.

Definizione: Una rappresentazione Ax < b è minimale se, rimuovendo una qualsiasi disequazione dal sistema si ottiene un nuovo sistema A’x < b’ tale che P ⊂ {x∈ℜ

: A’x < b’}.

Definizione: Se P ⊆ ℜ

è tale che dim(P) = n, una rappresentazione Ax < b

è minimale se e solo se ogni disequazione del sistema definisce una faccia

massimale di P.

Formulazioni di problemi di PL 0-1

Ricordiamo che, date due diverse formulazioni lineari P ₁ e P ₂ di un problema di programmazione lineare 0-1 della forma (1), diremo che P ₁ è migliore di P ₂ se e solo se P ₁ ⊂ P ₂ .

La formulazione ottima di un problema di programmazione lineare 0-1 della forma

è costituita dal poliedro contenuto in tutti i poliedri contenenti S, ovvero dall’involucro convesso conv(S). Indichiamo con P

la formulazione ottima.

(1) max c

x

x∈S (S ⊆ {0,1}

)

Formulazioni di problemi di PL 0-1

Ricordiamo ancora che, dato un problema di programmazione lineare 0-1

max c

x (1)

x∈S (S ⊆ {0,1}

)

un poliedro P = {x∈ℜ

: Ax < b} è una formulazione lineare del problema se e solo se S = P ∩ {0,1}

.

Teorema: Un problema di programmazione lineare 0-1 della forma

(1) ammette sempre una formulazione lineare conv(S) con la

proprietà che x∈S se e solo se x è un vertice di conv(S).

Formulazioni di problemi di PL 0-1

Dal teorema precedente, possiamo riscrivere il problema (1) nella forma

max c

x (2)

x∈P

Infatti, poiché i vertici di P

coincidono con i vettori in S, risolvere il problema (1) è equivalente ad individuare un vertice di P

che massimizzi c

x, ovvero ad individuare un vertice ottimo per il problema (2).

Pertanto, ogni problema di programmazione lineare 0-1 può essere

espresso come problema di programmazione lineare.

Il fatto che si possa passare da un problema di programmazione lineare 0-1 a un problema di programmazione lineare suggerisce importanti conseguenze riguardanti la complessità computazionale:

infatti, è noto che un problema di programmazione lineare può essere risolto in tempo e spazio polinomiali ricorrendo a opportuni algoritmi.

ATTENZIONE! E’ sbagliato pensare che algoritmi polinomiali per problemi di programmazione lineare possano essere utilizzati per risolvere qualsiasi problema di programmazione lineare 0-1.

Formulazioni di problemi di PL 0-1

Alcuni metodi per la programmazione lineare richiedono una rappresentazione esplicita della formulazione P

. Tale rappresentazione è teoricamente ottenibile per qualsiasi problema di programmazione lineare 0-1 ma è spesso algoritmicamente impraticabile.

Invece altri metodi,come il Metodo dell’Ellissoide, si accontentano di una rappresentazione implicita della formulazione P

fornita dal cosiddetto Oracolo di Separazione.

Tale oracolo è realizzato da un algoritmo che, dato un vettore x’∈ℜ

, o genera un iperpiano che separa x’ da P

oppure conclude che x’∈P

.

L’oracolo di separazione descrive P

in modo algoritmico e rende i metodi che lo utilizzano indipendenti dal numero di disequazioni della rappresentazione esplicita.

Formulazioni di problemi di PL 0-1

Rafforzamento di formulazioni

Il problema di knapsack max 5x ₁ + 2x ₂

3x ₁ + 4x ₂ < 6

x ∈ {0,1} ² ha come rilassamento lineare max 5x ₁ + 2x ₂

3x ₁ + 4x ₂ < 6 x ₁ > 0

x ₂ > 0 x ₁ < 1 x ₂ < 1

Sia x ^* _LP la soluzione ottima del rilassamento.

Oracolo di Separazione

Dato il vettore x ^* _LP , l’oracolo di separazione consente

– di individuare una disequazione soddisfatta da tutti i vettori in P

(valida per P

), e non soddisfatta dal vettore x

OPPURE – di concludere che x

∈ P

.

Dal punto di vista geometrico, l’oracolo costruisce, se esiste, un iperpiano che separa x ^* _LP da P

. Se tale iperpiano non esiste allora il punto x ^* _LP appartiene a P

.

L’iperpiano individuato è detto iperpiano di separazione o

piano di taglio.

Oracolo di Separazione

x

x

x

LP

L’oracolo viene generalmente realizzato tramite un algoritmo

detto Algoritmo di Separazione.

Disuguaglianze valide per il Knapsack 0-1

Consideriamo l’insieme

X = {x ∈ {0,1}

: Σ a

x

< b}.

Definizione: Un insieme C ⊆ N è un cover se e solo se Σ a

> b.

Un cover è minimale se, comunque preso j ∈C, l’insieme C \ { j } NON è un cover.

Osservazione: Un insieme C è un cover se e solo se il suo vettore caratteristico x

non è ammissibile per X.

n

j = 1

j ∈ C

Teorema: Se C ⊆ N è un cover per X, la disequazione

Σ x

< |C| – 1 (*) è valida per X.

Dimostrazione: Dimostriamo che se un generico vettore x

non soddisfa il vincolo (*) allora x

∉ X.

Se x

è tale che Σ x

> |C| – 1, allora |R ∩ C|= |C| e quindi C ⊆ R.

Pertanto:

Σ a

x

= Σ a

> Σ a

> b ovvero x

∉ X.

Disuguaglianze valide per il Knapsack 0-1

j ∈C

j ∈C

j =1 n

j ∈R j ∈C

Consideriamo il problema di knapsack

max 15 x ₁ + 9 x ₂ + 8 x ₃ + 6 x ₄ + 5 x ₅ + 4 x ₆ + x ₇

11 x ₁ + 6 x ₂ + 6 x ₃ + 5 x ₄ + 5 x ₅ + 4 x ₆ + x ₇ < 19 x ∈ {0,1} ⁷

La soluzione associata al suo rilassamento lineare è (x ^* ) _LP = (1, 1, 1/3, 0, 0, 0, 0).

Una disequazione cover violata da (x

)

è la disequazione x ₁ + x ₂ + x ₃ < 2.

Qual è il problema di separazione che consente di individuare una disequazione di tipo cover violata da (x ^* ) _LP ?

Esempio

Oracolo di separazione

Riscriviamo la disequazione Σ x

< |C| – 1 nella forma 1 + Σ x

- |C| < 0 ⇔ 1 + Σ (x

– 1) < 0

La disequazione è violata da (x

)

se e solo se:

1 + Σ ((x

)

– 1) > 0

Quindi, possiamo massimizzare la violazione definendo SEP = max { Σ ((x

)

– 1) : Σ a

> b}

Un algoritmo per SEP è un oracolo di separazione.

j ∈C

j ∈C j ∈C

j ∈C

j ∈C j ∈C

C ⊆ N

Siano

– y

la soluzione ottima del problema SEP, e

– z

il corrispondente valore della funzione obiettivo.

Se 1 + z ^* _SEP > 0, allora esiste una disuguaglianza cover violata da y ^* _SEP .

Se 1 + z ^* _SEP < 0, allora non esiste una disuguaglianza cover violata da y ^* _SEP .

A questo punto non resta che formulare come programmazione lineare 0-1 il problema di separazione.

Oracolo di separazione

Formulazione del problema di separazione

Il problema di separazione può essere formulato come un problema di programmazione lineare 0-1 in cui la variabile y

= 1 se j∈C e y

= 0 altrimenti.

Funzione Obiettivo max Σ ((x

)

– 1)y

Vincoli Σ a

y

> b + 1

y ∈ {0,1}

Osservazione: I coefficienti in funzione obiettivo sono < 0 e quindi il problema non ammette una soluzione banale.

j ∈N

j ∈N

Trasformazione

Ponendo w

= 1 – y

, il problema di separazione diventa

Poiché Σ ((x

)

– 1) è una costante possiamo non tenerne conto nella funzione obiettivo.

Funzione Obiettivo max Σ _((x

₎

_{– 1) –} Σ _((x

₎

_{– 1)w}

Vincoli – Σ a

w

> – Σ a

+ b + 1 w ∈ {0,1}

j ∈N

j ∈N j ∈N

j ∈N

j ∈N

…un problema di knapsack

Funzione Obiettivo max Σ _{(1 – (x} ^* _{j ) LP )w j}

Vincoli Σ _{a j w j <} Σ _{a j – b – 1}

w ∈ {0,1} ⁿ

j ∈N j ∈N

j ∈N

Esempio

max 15 x

+ 9 x

+ 8 x

+ 6 x

+ 5 x

+ 4 x

+ x

11 x

+ 6 x

+ 6 x

+ 5 x

+ 5 x

+ 4 x

+ x

< 19 x ∈ {0,1}

x

= (1, 1, 1/3, 0, 0, 0, 0)

Problema di separazione

max (1 – 1) w

+ (1 – 1) w

+ (1 - 1/3) w

+ w

+ w

+ w

+ w

11 w

+ 6 w

+ 6 w

+ 5 w

+ 5 w

+ 4 w

+ w

< 38 – 19 – 1 = 18

w ∈ {0,1}

Separazione

Problema di separazione

max 2/3 w ₃ + w ₄ + w ₅ + w ₆ + w ₇

11 w ₁ + 6 w ₂ + 6 w ₃ + 5 w ₄ + 5 w ₅ + 4 w ₆ + w ₇ < 18 w ∈ {0,1} ⁷

Soluzione ottima

w* = (0, 0, 0, 1, 1, 1, 1) di valore 4

Riportiamola nello spazio delle y:

y* = (1, 1, 1, 0, 0, 0, 0) di valore z ^* _SEP = –2/3.

Pertanto, 1 + z ^* _SEP = 1/3 > 0

Separazione

1. Il valore di 1 + z

è > 0, ovvero esiste una disequazione cover violata.

2. Il cover associato alla violazione è formato dagli indici che hanno valore 1 in y

, ovvero

y* = (1, 1, 1, 0, 0, 0, 0) corrisponde al cover C = {1, 2, 3}.

3. La disequazione è scritta in corrispondenza degli indici in C, ossia

C = {1, 2, 3} corrisponde a x

+ x

+ x

< |C| – 1 = 2

Algoritmo dei piani di taglio

Dato il rilassamento lineare di un problema di knapsack 1. Calcola la soluzione ottima x ^* _LP .

2. Se x ^* _LP ∈ {0, 1}

STOP, altrimenti vai al passo 3.

3. Definisci il problema di separazione.

4. Risolvi il problema di separazione.

5. Se esiste una disequazione cover violata aggiungila

alla formulazione corrente e torna al punto 1, altrimenti

STOP.

Pianificazione degli investimenti

Dati

– I = {1, 2, …, n} = insieme di investimenti attivabili su un orizzonte temporale T = {1, 2, …, t} di t periodi

– Ad ogni investimento i è associato un indice di redditività c

– Ogni investimento i genera un flusso di cassa a

= (a

, a

, …, a

) (> 0 introiti, < 0 esborsi) per ogni periodo j ∈T

– Per ogni periodo j∈T esiste un budget b

che limita gli esborsi (flussi di cassa negativi).

Problema

Determinare un insieme di investimenti I

⊆ I che massimizza la

redditività e che rispetta il vincolo per cui la somma dei flussi di

cassa degli investimenti attivati in ogni periodo j∈T non superi il

budget b

.

Esempio

Investimento 1

Investimento 2

Investimento 3

Periodo 1 b

= –4

Periodo 2 b

= –5

Periodo 3 b

= –1 a

=2

a

=3

a

=–6

a

=–10

a

=–3

a

=2

a

=–2

a

=5

a

=–3

Esempio

Formulazione

Variabili decisionali

x

= 1 se il progetto i è attivato x

= 0 altrimenti

Nell’esempio precedente, se vengono attivati tutti e tre gli investimenti il vincolo di budget nel periodo 2 NON è rispettato.

max Σ c

x

Σ _a

_x

_{> b}

^∀ j∈T x∈{0,1}

i∈I i∈I

max c

x

Ax > b

x∈{0,1}

Per migliorare la formulazione precedente, consideriamo un singolo vincolo di budget del sistema Ax > b e il problema di Knapsack continuo ad esso associato:

Rilassamento lineare

(KP

) max c

x

a

x > b

0 < x < 1

max c

x

– a

x < –b

0 < x < 1

cambiamo

segno nel

vincolo

Rafforzamento

L’insieme delle soluzioni del problema di pianificazione originario è costituito dall’intersezione degli insiemi delle soluzioni dei singoli problemi di knapsack (KP

).

Pertanto, è possibile rafforzare ciascun problema KP

, ad

esempio con disequazioni cover, per ottenere un

rafforzamento della formulazione di pianificazione.

Esempio

Consideriamo la seguente istanza di un problema di pianificazione:

– I = {1, 2, 3, 4, 5}

– T = {1, 2, 3}

– c = (3, 7, 3, 5, 7) = Redditività – b = (-2, 0, -5) = Budget

– a

= (-4, 1, -2) = Flusso di Cassa I

– a

= (2, -4, 1) = Flusso di Cassa I

– a

= (1, 3, -5) = Flusso di Cassa I

– a

= (1, -3, -2) = Flusso di Cassa I

– a

= (-3, 4, 1) = Flusso di Cassa I

Esempio

1 0

5 2

5 2

0 4

3 3

4

2 3

2 4

7 5

3 7

3 max

5 4

3 2

1

5 4

3 2

1

5 4

3 2

1

5 4

3 2

1

≤

≤

≤

− +

+

−

≤

− +

− +

−

≤ +

−

−

−

+ +

+ +

x

x x

x x

x

x x

x x

x

x x

x x

x

x x

x x

x

La soluzione ottima di (PL) è:

x* _PL = [0.67; 1; 0.74; 0.96; 1] di valore z* = 23.09

(PL)

Il rilassamento lineare si scrive (considerando il

cambiamento di segno sul vincolo di budget)

Esempio

Consideriamo a questo punto il primo vincolo di budget e il problema di knapsack continuo ad esso associato:

1 0

2 3

2 4

7 5

3 7

3 max

5 4

3 2

1

5 4

3 2

1

≤

≤

≤ +

−

−

−

+ +

+ +

x

x x

x x

x

x x

x x

x

(KP ₁ )

Effettuiamo un cambio di variabili per ottenere tutti coefficienti positivi nel vincolo di knapsack:

J(–) = {2, 3, 4} ⇒ y

= 1 – x

per ogni i ∈ J(–).

Si ottiene:

6 3

2

4 x 1 + y 2 + y 3 + y 4 + x 5 ≤

Esempio

Dobbiamo vedere se esiste una cover violata rispetto alla soluzione:

Risolvendo il problema di separazione si individua la cover violata x

+ x

< 1, che si può aggiungere direttamente alla formulazione, essendo già nelle variabili x.

Osservazione: Se la cover contiene variabili y, bisogna effettuare il cambio di variabile y

= 1–x

prima di aggiungere la disequazione alla formulazione

La nuova soluzione ottima del RL (peraltro intera) è

x* _PL = [0.67; 1–1 = 0 ; 1–0.74 = 0.26; 1–0.96 = 0.04; 1]

x* = [0; 1; 1; 1; 1] di valore z* = 22.