Capitolo 2: Semplificazione, Ottimizzazione e Implicazione 1 Semplificazione, Ottimizzazione e Implicazione Semplificazione di vincoli Proiezione Semplificatori di vincoli Ottimizzazione Implicazione ed equivalenza 2 Semplificazione di vincoli Due vincoli equivalenti rappresentano la stessa informazione, ma … Uno puo’ essere piu’ semplice dell’altro X 1 X 3 2 Y X X 3 2 Y X 3 X X 2Y X 2Y 3 X X 2Y 3 2Y X 2 Y Y 1 Rimuovere vincoli ridondanti, riscrivere un vincolo primitivo, cambiare l’ordine, sostituire usando una equazione, tutti preservano l’equivalenza 3 Vincoli 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: C1 C2 X 3 X 1 Y X 2 Y 4 X 1 cons ( X , X ) cons ( Z , nil ) Z nil 4 Vincoli ridondanti Possiamo rimuovere un vincolo primitivo che e’ ridondante rispetto al resto dei vincoli X 1 X 3 X 3 Y X 2 X 1 Y 4 Y X 2 Y 4 cons( X , X ) cons( Z , nil ) Z nil cons( X , X ) cons( Z , nil ) Cosi’ otteniamo un vincolo piu’ semplice 5 Risolutori a forma risolta Un risolutore a forma risolta crea vincoli equivalenti puo’ essere visto come un semplificatore Per esempio usando il risolutore per equazioni di termini cons( X , X ) cons( Z , nil ) Y succ( X ) succ( Z ) Y Z nil X nil Z nil Y succ(nil ) O usando il risolutore di Gauss-Jordan X 2 Y 2Y X T Z X Y 4 Z T 5 X 3 Y 1 Z 5 T 6 Proiezione Diventa anche piu’ importante semplificare quando siamo solo interessati ad alcune variabili nel vincolo V 1 I 1 R1 + V 2 I 2 R2 V V V1 0 V V 2 0 V1V 2 0 I I1 I 2 0 I I1 I 2 0 R1 5 R 2 10 + V2 V1 I1 I -3_ -- I2 --- 10 I Semplificato rispetto a V e I: V 3 7 Proiezione 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 C X Y Y Z Z 0 X 0 { X 0, Y 0, Z 0} { X 0} { X 4, Y 3, Z 1} { X 4} 8 Algoritmo di Fourier Elimina una variabile y da disequazioni lineari C Scrive ogni diseq con y su un lato: t1 y y t2 Per ogni coppia t1 y y t2 produce una nuova diseq t1 y y t2 t1 t2 Il risultato e’ un insieme di nuove diseq e quelle diseq in C che non riguardano y 9 Esempio Y Proiettiamo fuori Y: X 1 Y 1 X Y Y 1 X Y 1 X X 1 Y Y 1 X X 1 Y Y 1 X 1 X Y Y 1 X 1 X Y Y 1 X +1 -1 +1 X +1 X -1 -1 X 1 02 Il risultato contiene solo X: 02 X 1 1 X 1 X 10 Proiettare i vincoli sugli alberi Possiamo proiettare vincoli sui termini cons(Y , Y ) cons( X , Z ) succ( Z ) succ(T ) Proiettato su {X,Z} e’ X Z Ma cosa e’ X = cons(Y,Z) proiettato su X? Risposta: non c’e un tale vincolo! 11 Semplificatori 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} 12 Definizione 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 13 Semplificatore per vincoli sugli 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 14 Esempio di semplificazione sugli alberi Vincolo sugli alberi da semplificare rispetto a {Y,T}: h( f ( X , Y ), Z , g (T )) h( f ( g (T ), X ), f ( X , X ), g (U )) 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 ) 15 Proprieta’ dei semplificatori Proprieta’ desiderabili di un semplificatore: proiettante: vars( simpl (C,V )) V Debolmente proiettante: per tutti I vincoli C2 che sono equivalenti a C1 rispetto a V | vars( simpl (C1,V )) V | | vars(C2) 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 16 Ottimizzazione 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 17 Problema 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. 18 Esempio di ottimizzazione Y Un problema di ottimizzazione: 4 (C X Y 4, f X 2 Y2) Trovare il punto piu’ vicino all’origine che soddisfi C. Alune soluzioni e il valore di f : { X 0, Y 4} 16 { X 3, Y 3} { X 2, Y 2} 18 8 3 X+Y=4 2 1 X 0 1 2 3 4 Soluzione ottima: { X 2, Y 2} 19 Ottimizzazione Alcuni problemi di ottimizzazione non hanno soluzioni Il vincolo non ha soluzioni: ( X 2 X 0, X ) 2 Il problema non ha ottimo: ( X 0, X ) Per ogni soluzione, c’e’ n’e’ sempre un’altra migliore 20 Algoritmo del simplesso L’algoritmo piu’ usato per l’ottimizzazione Ottimizza un funzione lineare rispetto a dei vincoli lineari Collegato all’eliminazione di Gauss-Jordan 21 Algoritmo del simplesso Un problema di ottimizzazione (C, f) e’ in forma simplesso se: 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 C 22 Esempio del simplesso Un problema di ottimizzazione in forma simplesso minimize 3 X+2Y-Z+1 subject to X Y 3 X 3Y 2 Z T 1 X 0Y 0 Z 0T 0 • Un problema arbitrario puo’ essere messo in forma simplesso: • rimpiazzando ogni variabile non vincolata X con nuove variabili X X •Rimpiazzando ogni disequazione e r con una nuova variabile s e e s r 23 Simplex 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 nonnegative Only parameters occur in the objective A basic feasible solution is obtained by setting each parameter to 0 and each nonparameter to the constant in its equation 24 Simplex Example An equivalent problem to that before in bfs form minimize 10 Y Z subject to X 3 Y T 4 2Y 2 Z X 0Y 0 Z 0T 0 We can read off a solution and its objective value { X 3, T 4, Y 0, Z 0} f 10 25 Simplex 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 26 Simplex Example minimize 10 Y Z subject to X 3 Y T 4 2Y 2 Z X 0Y 0 Z 0T 0 Choose variable Y, the first eqn is only one with neg. coeff Y 3 X minimize 7 X Z subject to Y 3 X T 10 2 X 2 Z X 0Y 0 Z 0T 0 Choose variable Z, the 2nd eqn is only one with neg. .T coeff Z 5 X 05 minimize 2 2 X 0.5T subject to Y 3 X Z 5 X 0.5T X 0Y 0 Z 0T 0 No variable can be chosen, optimal value 2 is found 27 Another example Y minimize X Y subject to Y 0 X 1 X 3 4 -2 -1 0 preferred solutions 3 1 2 2Y X 3 2 1 X An equivalent simplex form is: S2 X S3 X X 1 2Y S1 0 1 2 3 4 3 3 X 0 Y 0 S1 0 S 2 0 S3 0 An optimization problem showing contours of the 28 objective function Another example Y Basic feasible solution form: circle minimize 0 0.5S1 0.5S3 subject to Y 3 0.5S1 0.5S3 S2 2 S3 X 3 S3 Choose S3, replace using 2nd eq minimize 1 0.5S1 0.5S 2 subject to Y 2 0.5S1 0.5S 2 S3 2 S2 X 1 S2 4 -2 -1 0 3 1 2 2 1 X 0 1 2 3 4 Optimal solution: box 29 The 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 30 The Missing Part Example Original simplex form equations S2 X X X 1 S3 2Y S1 3 3 With artificial vars in bfs form: A1 1 X A2 3 X A3 3 X S2 S3 2Y S1 Objective function: minimize A1 A2 A3 7 X 2Y S1 S2 S3 31 Missing Part Example II Problem after minimization of objective function Y minimize A1 A2 A3 subject to 3 0.5S1 0.5S3 0.5 A2 0.5 A3 S2 X 2 3 S3 S3 A1 A2 A2 Removing the artificial variables, the original problem Y 3 0.5S1 S2 2 X 3 0.5S3 S3 S3 32 Implicazione 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 33 Esempio di implicazione Building a House Stage S Per I vincoli della casa CH, lo stadio B sara’ raggiunto dopo lo stadio C? CH TB TC Per questa domanda la risposta e’ false, ma se richiediamo che la casa sia finita in 15 giorni la risposta e’ true CH TE 15 TB TC Foundations 7 days Stage A Interior Walls 4 days Stage B Doors 2 days Chimney 3 days Exterior Walls 3 days Stage C Roof 2 days Windows 3 days Stage D Tiles 3 days Stage E 34 Implicazione ed Equivalenza Possiamo usare impl per definire equiv e viceversa: impl (C1, C2) equiv(C1, C1 C2) equiv(C1, C2) impl (C1, C2) impl (C2, C1) Possiamo usare un risolutore per testare impl: impl (C1, C2) solv(C1 C2) Es.: impl (CH , TB TC ) solv(CH TB TC ) 35 Sommario su semplificazione, ottimizzazione 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 36