Ottimizzazione vincoli

Finora, dato un insieme di vincoli si cercava una soluzione

Se non esiste, ha senso considerare una valutazione che soddisfa più vincoli possibili

Peso dei vincoli

In generale, i vincoli possono avere importanza diversa:

• vincoli hard: quelli da soddisfare per forza
• vincoli soft: quelli da soddisfare se possibile, il maggior numero possibile

Anche tra i vincoli soft alcuni vincoli possono essere più importanti di altri

Per questo, si assegnano pesi ai vincoli

Costo di una valutazione

Data una soluzione ai vincoli hard, il suo costo è la somma dei pesi dei vincoli violati da essa

Si tratta quindi di trovare una soluzione a costo minimo

Backtracking

Si può usare il backtracking per trovare la soluzione ottima

Si mantiene il la soluzione migliore trovata finora e il suo costo

Quando si trova una soluzione, non ci si ferma ma:

• si memorizza il suo costo se minore di quello memorizzato in precedenza
• si prosegue nel backtracking alla ricerca di altre soluzioni

Branch and bound

Simile alla variante di backtracking vista prima, ma con una aggiunta che riduce la ricerca

Data una valutazione parziale, si può valutare un limite inferiore al costo di ogni valutazione totale che la estende

Infatti, se la valutazione parziale viola dei vincoli, questi sono violati anche da tutte le valutazioni totali che la estendono

Riduzione ricerca:

• quando si trova una soluzione parziale il cui costo è maggiore della soluzione migliore trovata finora, non si va avanti; si fa backtracking

Algoritmo complessivo

Rispetto al backtracking, le varianti sono

• si memorizza la soluzione migliore trovata finora e il suo costo
• si aggiornano questi dati ogni volta che si trova una nuova soluzione
• ogni volta che si valuta una variabile ad un valore:
  • si vede se il peso dalla valutazione parziale supera quello della soluzione migliore
  • se lo supera, si fa backtracking invece di andare avanti

Alla fine, la soluzione memorizzata è una di quelle ottime

Miglioramenti

Invece di usare il costo di una soluzione parziale, posso usare una limite inferiore al costo delle soluzioni che la estendono

Questo limite funziona se:

• tutte le soluzioni che estendono quella parziale effettivamente hanno peso maggiore o uguale al limite
• più il limite è alto, più è facile che superi il costo della soluzione migliore, e quindi permetta di tagliare l'albero di ricerca

La prima condizione deve essere rispettata per forza, altrimenti il metodo non funziona

Rispettando la prima condizione, va scelto un limite che sia il puù alto possibile

Prima scelta

Fornisce un limite al costo delle valutazioni parziali che può essere più alto di quello visto prima

Guarda anche i vincoli che hanno variabili non assegnate

Il sistema precedente "assumeva" che i vincoli non valutabili si potevano soddisfare

Il sistema della prima scelta va a vedere se questi vincoli presi uno per volta, sono in effetti soddisfabili

Prima scelta: esempio

Vincoli x<y e y<z con peso uno, domini tutti uguali ad {0,1}, valutazione x=0,z=0,

Con il metodo di prima, il costo era zero, dato che la valutazione non viola nessun vincolo

Con questo metodo

• il vincolo x<y si può soddisfare con x=0: basta scegliere y=1
• il vincolo y<z non si può soddisfare per z=0

La valutazione parziale ha quindi peso uno invece di zero

Nota sui valori

Si va a guardare un vincolo per volta

I valori delle variabili non valutate potrebbero quindi essere diversi per i vari vincoli

Esempio: x<y, y<z con valutazione x=0,y=1

• il primo vincolo si può soddisfare con y=1
• il secondo vincolo si può soddisfare con y=0

Non importa se questi valori di y sono diversi: nel valutare il peso si fa come se i due vincoli fossero soddisfatti

Motivo: cercare valori uguali per i vincoli è come risolvere il problema, mentre qui voglio una stima rapida da poter effettuare in ogni nodo dell'albero

Bambole russe

È un meccanismo ancora più complicato

Si fa backtracking in ordine fisso

Sia x₁,...,x_n questo ordine

Si risolvono nell'ordine i sottoproblemi su variabili x_i,...,x_n per i che va da n ad 1

In altre parole: ogni sottoproblema si ottiene eliminando le variabili x₁,...,x_i-1 e tutti i vincoli che le contengono

Soluzione di ogni sottoproblema

Per risolvere un qualsiasi sottoproblema sulle variabili x_i,...,x_n, serve un limite per le valutazioni sulle variabili x_i,...,x_j

Come limite si usa la somma di:

• il peso dei vincoli violati dalla valutazione di x_i,...,x_j
• il costo della soluzione ottima del sottoproblema sulle variabili x_j+1,...,x_n

Rispetto all'algoritmo base, qui si migliora la soluzione usando l'ottimo del sottoproblema, che è stato già trovato in precedenza

Notare che il sottoproblema non include le variabili x_i,...,x_j

Comunque serve una approssimazione