1

Capitolo 2: Semplificazione, Capitolo 2: Semplificazione, Ottimizzazione e ImplicazioneOttimizzazione e Implicazione

2

Semplificazione, Semplificazione, Ottimizzazione e ImplicazioneOttimizzazione e Implicazione

Semplificazione di vincoli Proiezione Semplificatori di vincoli Ottimizzazione Implicazione ed equivalenza

3

Semplificazione di vincoliSemplificazione di vincoli

Due vincoli equivalenti rappresentano la stessa informazione, ma …

Uno puo’ essere piu’ semplice dell’altroX X Y X

X Y X

X X Y

X Y X

X Y Y

X Y Y

1 3 2

3 2

3 2

2 3

2 3 2

2 1

Rimuovere vincoli ridondanti, riscrivere un vincolo primitivo, cambiare l’ordine, sostituire usando una equazione, tutti preservano l’equivalenza

4

Vincoli ridondantiVincoli ridondanti

Un vincolo C1 implica un altro vincolo C2 se le soluzioni di C1 sono un sottoinsieme di quelle di C2

C2 e’ detto ridondante rispetto a C1 Scriviamo: C C1 2

nilZnilZconsXXcons

XYXY

XX

),(),(

142

13

5

Vincoli ridondantiVincoli ridondanti

Possiamo rimuovere un vincolo primitivo che e’ ridondante rispetto al resto dei vincoli

X X X

Y X X Y Y X Y

cons X X cons Z nil Z nil cons X X cons Z nil

1 3 3

2 1 4 2 4

( , ) ( , ) ( , ) ( , )

Cosi’ otteniamo un vincolo piu’ semplice

6

Risolutori a forma risoltaRisolutori a forma risolta

Un risolutore a forma risolta crea vincoli equivalenti puo’ essere visto come un semplificatore

cons X X cons Z nil Y succ X succ Z Y Z nil

X nil Z nil Y succ nil

( , ) ( , ) ( ) ( )

( )

Per esempio usando il risolutore per equazioni di termini

O usando il risolutore di Gauss-JordanX Y Y X T Z X Y Z T

X Y Z T

2 2 4 5

3 1 5

7

ProiezioneProiezione

Diventa anche piu’ importante semplificare quando siamo solo interessati ad alcune variabili nel vincolo

II1

I2

V

+

--3_--

+

--

V1V2

--

V I R

V I R

V V

V V

V V

I I I

I I I

R

R

1 1 1

2 2 2

1 0

2 0

1 2 0

1 2 0

1 2 0

1 5

2 10

Semplificato rispetto a V e I:V I

10

3

8

ProiezioneProiezione

La proiezione di un vincolo C sulle variabili V e’ un vincolo C1 tale che C1 ha solo le variabili in V Ogni soluzione di C e’ una soluzione di C1 Una soluzione di C1 puo’ essere estesa per

ottenere una soluzione di CX Y Y Z Z

X Y Z

X Y Z

0

0 0 0

4 3 1

{ , , }

{ , , }

X

X

X

0

0

4

{ }

{ }

9

Algoritmo di FourierAlgoritmo di Fourier

Elimina una variabile y da disequazioni lineari C

Scrive ogni diseq con y su un lato:

Per ogni coppia produce una nuova diseq

Il risultato e’ un insieme di nuove diseq e quelle diseq in C che non riguardano y

t y y t1 2 t y y t1 2

2121 tttyyt

10

EsempioEsempio

Proiettiamo fuori Y:

X

Y

+1

+1-1

-1

X-1 +1

X Y

X Y

Y X

Y X

1

1

1

1

X Y Y X X

X Y Y X

X Y Y X

X Y Y X X

1 1 1

1 1 0 2

1 1 0 2

1 1 1

Il risultato contiene solo X:

X X 1 1

11

Proiettare i vincoli sugli alberiProiettare i vincoli sugli alberi

Possiamo proiettare vincoli sui termini

Proiettato su {X,Z} e’ Ma cosa e’ X = cons(Y,Z) proiettato su X? Risposta: non c’e un tale vincolo!

cons Y Y cons X Z succ Z succ T( , ) ( , ) ( ) ( )

X Z

12

Semplificatori di vincoliSemplificatori di vincoli

vincoli C1 and C2 sono equivalenti rispetto alle variabili in V se Prendendo una soluzione di uno dei due, e

restringendola alle variabili in V, questa soluzione ristretta puo’ essere estesa ad una soluzione dell’altro

Example X=succ(Y) and X=succ(Z) wrt {X}X succ Y X X succ Z

X succ a Y a X succ a X succ a Z a

X succ nil Y nil X succ nil X succ nil Z nil

( ) { } ( )

{ ( ), } { ( )} { ( ), }

{ ( ), } { ( )} { ( ), }

13

Definizione di semplificatoreDefinizione di semplificatore

Un semplificatore di vincoli e’ una funzione simpl che prende un vincolo C e un insieme di variabili V e ritorna un vincolo C1 che e’ equivalente a C rispetto a V

Possiamo creare un semplificatore per disequazioni lineari usando l’algoritmo di Fourier

14

Semplificatore per vincoli Semplificatore per vincoli sugli alberisugli alberi

Applicare il risolutore per equazioni di termini a C e ottenere C1

se C1 e’ false allora return false Per ogni equazione x=t in C1

se x e’ in V allora se t e’ una variabile non in V

sostituire x per t in C1 e nel risultato altrimenti aggiungere x=t al risultato

return risultato

15

Esempio di semplificazione Esempio di semplificazione sugli alberisugli alberi

Vincolo sugli alberi da semplificare rispetto a {Y,T}:

))(),,(),),((())(,),,(( UgXXfXTgfhTgZYXfh

Vincolo equivalente dal risolutore sugli alberi:

Z f g U g U X g U Y g U T U ( ( ), ( )) ( ) ( )

Eliminare le prime due equazioni, tenere la terza e usare l’ultima per sostituire T con U:

Y g T ( )

16

Proprieta’ dei semplificatoriProprieta’ dei semplificatori

Proprieta’ desiderabili di un semplificatore: proiettante: Debolmente proiettante: per tutti I vincoli C2 che

sono equivalenti a C1 rispetto a V

Un risolutore debolmente proiettante non usa mai piu’ variabili di quelle necessarie

Entrambe le proprieta’ permettono ad un semplificatore di essere usato come un risolutore

vars simpl C V V( ( , ))

| ( ( , )) | | ( ) |vars simpl C V V vars C V1 2

17

OttimizzazioneOttimizzazione

Spesso dato un problema modellato con vincoli, non vogliamo una qualsiasi soluzione, ma una soluzione ottima

Quindi si ha un problema di ottimizzazione Abbiamo bisogno di una funzione obbiettivo in

modo da poter paragonare soluzioni, cioe’ un mapping da soluzioni a valori reali

18

Problema di ottimizzazioneProblema di ottimizzazione

Un probleema di ottimizzazione (C,f) consiste di un vincolo C e una funzione obbiettivo f

Una valutazione v1 e’ preferita alla valutazione v2 se f(v1) < f(v2)

Una soluzione ottima e’ una soluzione di C tale che non esiste nessun’altra soluzione di C che e’ preferita a lei.

19

Esempio di ottimizzazioneEsempio di ottimizzazione

0 1 2 3 4

1

2

3

4

Y

X

X+Y=4

Un problema di ottimizzazione:

( , )C X Y f X Y 4 2 2

Trovare il punto piu’ vicino all’origine che soddisfi C. Alune soluzioni e il valore di f :

{ , }

{ , }

{ , }

X Y

X Y

X Y

0 4 16

3 3 18

2 2 8Soluzione ottima:

{ , }X Y 2 2

20

OttimizzazioneOttimizzazione

Alcuni problemi di ottimizzazione non hanno soluzioni Il vincolo non ha soluzioni:

Il problema non ha ottimo:

Per ogni soluzione, c’e’ n’e’ sempre un’altra migliore

( , )X X X 2 0 2

( , )X X0

21

Algoritmo del simplessoAlgoritmo del simplesso

L’algoritmo piu’ usato per l’ottimizzazione Ottimizza un funzione lineare rispetto a dei

vincoli lineari Collegato all’eliminazione di Gauss-Jordan

22

Algoritmo del simplessoAlgoritmo del simplesso

Un problema di ottimizzazione (C, f) e’ in forma simplesso se: C e’ la congiunzione di CE e CI CE e’ una congiunzione di equazioni lineari CI vincola tutte le variabili in C ad essere non

negative f e’ una espressione lineare sulle variabili in C

23

Esempio del simplessoEsempio del simplesso

minimize subject to3 2 1

3

3 2 1

0 0 0 0

X+ Y-Z+

X Y

X Y Z T

X Y Z T

Un problema di ottimizzazione in forma simplesso

• Un problema arbitrario puo’ essere messo in forma simplesso:

• rimpiazzando ogni variabile non vincolata X con nuove variabili •Rimpiazzando ogni disequazione con una nuova variabile s e

XX

re e s r

24

Simplex Solved FormSimplex Solved Form

A simplex optimization problem is in basic feasible solved (bfs) form if: The equations are in solved form Each constant on the right hand side is non-negative Only parameters occur in the objective

A basic feasible solution is obtained by setting each parameter to 0 and each non-parameter to the constant in its equation

25

Simplex ExampleSimplex Example

minimize subject to10

3

4 2 2

0 0 0 0

Y Z

X Y

T Y Z

X Y Z T

An equivalent problem to that before in bfs form

We can read off a solution and its objective value{ , , , }X T Y Z

f

3 4 0 0

10

26

Simplex AlgorithmSimplex Algorithm

starting from a problem in bfs form

repeat

Choose a variable y with negative coefficient in the obj. func.

Find the equation x = b + cy + ... where c<0 and -b/c is minimal

Rewrite this equation with y the subject y = -b/c + 1/c x + ...

Substitute -b/c + 1/c x + ... for y in all other eqns and obj. func.

until no such variable y exists or no such equation exists

if no such y exists optimum is found

else there is no optimum solution

27

Simplex ExampleSimplex Exampleminimize subject to10

3

4 2 2

0 0 0 0

Y Z

X Y

T Y Z

X Y Z T

Choose variable Y, the first eqn is only one with neg. coeff Y X 3

minimize subject to7

3

10 2 2

0 0 0 0

X Z

Y X

T X Z

X Y Z T

Choose variable Z, the 2nd eqn is only one with neg. coeff Z X T 5 05.

minimize subject to2 2 05

3

5 05

0 0 0 0

X T

Y X

Z X T

X Y Z T

.

.

No variable can be chosen, optimal value 2 is found

28

Another exampleAnother example

0 1 2 3 4

1

2

3

4

Y

X

-2 -1 0

1

2

preferredsolutions

minimize subject toX Y

Y

X

X

Y X

0

1

3

2 3

An equivalent simplex form is:

00000

32

3

1

321

1

3

2

SSSYX

SYX

SX

SX

An optimization problem showing contours of the objective function

29

Another exampleAnother example

0 1 2 3 4

1

2

3

4

Y

X

-2 -1 0

1

2

Basic feasible solution form: circleminimize subject to0 05 05

3 05 05

2

3

1 3

1 3

2 3

3

. .

. .

S S

Y S S

S S

X S

Choose S3, replace using 2nd eq

2

23

21

21

1

2

5.05.02

subject to 5.05.01 minimize

SX

SS

SSY

SS

Optimal solution: box

30

The Missing PartThe Missing Part

How do we get the initial basic feasible solution?

Solve a different simplex problem Add artificial variables to make equations in

basic feasible solved form Minimize the sum of the artificial variables If the sum is zero we can construct a bfs for the

original problem

31

The Missing Part ExampleThe Missing Part Example

X S

X S

X Y S

2

3

1

1

3

2 3

Original simplex form equations

A X S

A X S

A X Y S

1 2

2 3

3 1

1

3

3 2

With artificial vars in bfs form:

Objective function: minimizeA A A

X Y S S S1 2 3

1 2 37 2

32

Missing Part Example IIMissing Part Example II

minimize subject toA A A

Y S S A A

S S A A

X S A

1 2 3

1 3 2 3

2 3 1 2

3 2

3 05 05 05 05

2

3

. . . .

Problem after minimization of objective function

Removing the artificial variables, the original problem

Y S S

S S

X S

3 0 5 0 5

2

3

1 3

2 3

3

. .

33

Implicazione ed EquivalenzaImplicazione ed Equivalenza

Altre importanti operazioni sui vincoli: implicazione: controlla se C1 implica C2

impl(C1, C2) risponde true, false o unknown equivalenza: controlla se C1 e C2 sono

equivalenti equiv(C1, C2) risponde true, false o unknown

34

Esempio di implicazioneEsempio di implicazioneB u ild in g a H ou se

D oors2 d ays

S tag e B

In te rio r W a lls4 d ays

C h im n ey3 d ays

S tag e D

S tag e E

Tiles3 d ays

R oof2 d ays

W in d ows3 d ays

S tag e C

E xte rio r W alls3 d ays

S tag e A

F ou n d ation s7 d ays

S tag e S

Per I vincoli della casa CH, lo stadio B sara’ raggiunto dopo lo stadio C?

CH T TB C

Per questa domanda la risposta e’ false, ma se richiediamo che la casa sia finita in 15 giorni la risposta e’ true

CH T T TE B C 15

35

Implicazione ed EquivalenzaImplicazione ed Equivalenza

Possiamo usare impl per definire equiv e viceversa:

Possiamo usare un risolutore per testare impl:

Es.:

impl C C equiv C C C( , ) ( , )1 2 1 1 2

equiv C C impl C C impl C C( , ) ( , ) ( , )1 2 1 2 2 1

impl C C solv C C( , ) ( )1 2 1 2

impl CH T T solv CH T TB C B C( , ) ( )

36

Sommario su semplificazione, Sommario su semplificazione, ottimizzazione e implicazioneottimizzazione e implicazione

Vincoli equivalenti possono essere scritti in varie forme, quindi serve la semplificazione

Soprattutto se siamo solo interessati all’interazione tra alcune delle variabili

Molti problemi necessitano di soluzioni ottime, ci sono algoritmi (es.: simplesso) per trovarle

Posssiamo anche voler fare domande che riguardano l’implicazione