Appunti su domande di esame per Modelli e software per l'ottimizzazione discreta

Dato un programma lineare intero (misto) con regione ammissibile Ω, una disequazione è un

p x ≤ β

piano di taglio (a volte semplicemente taglio) se è valida per Ω (e dunque per conv(Ω)) ma è violata da

almeno un punto frazionario del rilassamento lineare del problema.

 disuguaglianza valida

 incumbent:

In B&B è un upper bound sul costo della soluzione ottima (supponendo problema di minimizzazione)

 problema di separazione:

dato un punto frazionario e una famiglia di taglio esiste un taglio che separa il punto dalle soluzioni che

mi interessano?

Risolverlo significa:

--c’è, lo ritorno

--non c’è, dimostro che non è possibile trovarlo

5. Dato un problema di programmazione lineare con ottimo finito, cosa si può dire dell’insieme delle

soluzioni ottime?

6. Enunciare i teoremi di dualità forte e debole.

Dualità forte: Se il primale/duale ammette ottimo finito, di conseguenza anche il duale/primale lo

ammette. T T

E vale c x = b y

opt opt

con y soluzione ottima del duale e x soluzione ottima del primale.

opt opt

Dualità Debole: Una qualsiasi soluzione ammissibile del duale è bound sulla funzione obiettivo di una

qualsiasi soluzione del primale (lower bound se problema di minimo, e viceversa).

7. Quali sono i criteri di fathoming/pruning in un algoritmo B&B (o B&C)?

 Infeasibility (infattibilità - inaccettabilità)

 Optimality (ottimalità)

8. Dato un problema di programmazione con vincoli, dare le definizioni dei seguenti termini: dominio ·

vincolo · propagazione · vincolo globale

 dominio:

 vincolo:

 propagazione:

tecnica di inferenza che consiste nel rimuovere esplicitamente dal dominio delle variabili valori

(o combinazioni di valori) che non possono essere completati ad una soluzione ammissibile, in

quanto alcuni vincoli ne risulterebbero necessariamente violati.

 vincolo globale:

Un vincolo globale (global constraint) è un vincolo che descrive una relazione che coinvolge un

numero non-fisso di variabili.

9. Quali sono i vantaggi dell’uso dei vincoli globali in programmazione con vincoli?

il fatto di poter descrivere dei pattern di vincoli di particolare interesse pratico in modo chiaro e

compatto semplifica notevolmente la fase di modellazione.

Ancora più importante (e meno ovvio) è il fatto che molti vincoli globali forniscono al risolutore una

visione più accurata della struttura del problema e possono migliorarne drasticamente l’efficienza,

in quanto possono essere in grado di effettuare propagazioni che non sono possibili altrimenti.

10. Definire i seguenti vincoli globali: element · all-different · gcc

11. Dato un problema di soddisfacibilità booleana, definire i seguenti termini: clausola · literal ·

clausola Horn · risolvente · algoritmo di risoluzione · clausola unitaria · unit resolution

 clausola:

proposizione formata da una disgiunzione (or) di literals

 literal:

proposizione atomica o una sua negazione

 clausola Horn:

clausola con al più un literal non negato

 risolvente:

 algoritmo di risoluzione:

metodo di inferenza puro per risoluzione di un problema di soddifacibilità booleana che si basa sul

ripetere l’applicazione della regola di risoluzione fino a che non è possibile derivare più niente.

La formula di partenza è soddisfacibile se e solo se durante il processo di risoluzione non viene

derivata la clausola vuota.

 clausola unitaria:

clausola formata da un solo literal

 unit resolution:

algoritmo di risoluzione applicato ad un problema di soddisfacibilità booleana avente almeno una

clausola generatrice unitaria

12. Quali sono gli algoritmi esatti per un problema di soddisfacibilità booleana?

 RESOLUTION

 DPLL

13. Quali sono i vantaggi di un linguaggio di modellazione algebrico?

 è compatto

 è leggibile

 permette di usare lo stesso modello con dati diversi

 permette di usare diversi risolutori

 è autodocumentante

14. Dare una formulazione dei seguenti problemi noti: trasporto · dieta · knapsack binario · vertex

coloring · set covering · facility location