Per un problema di ottimizzazione con valore ottimo $z(I)$, sia $\mathscr{A}(I)$ il valore trovato da un'euristica e $gap(I)$ il gap relativo fra $\mathscr{A}(I)$ e il miglior bound duale noto. Quale affermazione è corretta?
L'errore relativo di $\mathscr{A}$ su $I$ è sempre uguale a $gap(I)$
L'errore relativo di $\mathscr{A}$ su $I$ è al più $gap(I)$
$gap(I)$ è un lower bound sul rapporto di prestazione di $\mathscr{A}$
L'errore relativo di $\mathscr{A}$ su $I$ è almeno $gap(I)$
Spiegazione. Il gap si misura rispetto a un bound duale, che non è migliore di $z(I)$: non è mai più piccolo dell'errore relativo, e coincide con esso solo quando il bound duale vale $z(I)$.
Per un problema di minimo con valori positivi, siano $\mathscr{A}(I)$ il valore di un'euristica, $z(I)$ il valore ottimo e $\mathrm{LB}(I)$ un bound. Quali fatti servono per dimostrare che l'errore relativo $\frac{\mathscr{A}(I)-z(I)}{z(I)}$ non supera $gap(I)=\frac{\mathscr{A}(I)-\mathrm{LB}(I)}{\mathrm{LB}(I)}$?
$\mathrm{LB}(I)\le z(I)$, quindi $\frac{\mathscr{A}(I)}{z(I)}\le\frac{\mathscr{A}(I)}{\mathrm{LB}(I)}$
$z(I)\le\mathrm{LB}(I)$, quindi $\frac{\mathscr{A}(I)}{\mathrm{LB}(I)}\le\frac{\mathscr{A}(I)}{z(I)}$
$\mathscr{A}(I)\le 2\,z(I)$, perché $\mathscr{A}$ è una $2$-approssimazione
$\mathscr{A}(I)=z(I)$, perché l'intorno usato da $\mathscr{A}$ è esatto
Spiegazione. Basta che $\mathrm{LB}(I)$ sia un bound duale: dividere $\mathscr{A}(I)$ per un numero più piccolo dà un rapporto più grande, e si sottrae $1$ da entrambi i lati.
Un'euristica per un problema di massimo trova $\mathscr{A}(I)=16$ e si conosce il bound duale $\mathrm{UB}(I)=17$. Il gap relativo è la differenza fra i due bound divisa per il lower bound. Quanto vale?
$5{,}88\%$
$1$
$94{,}1\%$
$6{,}25\%$
Spiegazione. Il gap divide sempre per il lower bound, qui il valore euristico: $\frac{\mathrm{UB}(I)-\mathscr{A}(I)}{\mathscr{A}(I)}=\frac{1}{16}=6{,}25\%$. Dividere per $17$ è l'errore tipico del denominatore.
Nella ricerca locale, un intorno $N$ associa a ogni soluzione ammissibile $S$ un insieme $N(S)$ di soluzioni vicine. Quando l'intorno $N$ si dice esatto?
Quando ogni soluzione di $N(S)$ ha valore migliore di quello di $S$
Quando ogni ottimo globale è un ottimo locale rispetto a $N$
Quando ogni ottimo locale rispetto a $N$ è un ottimo globale
Quando la ricerca locale con $N$ termina dopo un numero finito di mosse
Spiegazione. Un intorno è esatto se non ha ottimi locali che non siano globali; gli intorni piccoli usati in pratica in genere non lo sono.
Un algoritmo euristico $\mathscr{A}$ calcola, per ogni istanza $I$, una soluzione ammissibile di valore $\mathscr{A}(I)$, senza garantire che sia ottima ($z(I)$ = valore ottimo). Per un problema di massimo, quale relazione vale sempre?
$\mathscr{A}(I)\ge z(I)/2$
$\mathscr{A}(I)\le z(I)$
$\mathscr{A}(I)\ge z(I)$
$\mathscr{A}(I)=z(I)$ sulle istanze piccole
Spiegazione. Una soluzione ammissibile non può superare il massimo. $\mathscr{A}(I)\ge z(I)$ vale per i problemi di minimo; un fattore $\frac12$ sarebbe una garanzia di approssimazione, che un'euristica generica non ha.
Gli algoritmi di approssimazione sono un caso particolare di algoritmi euristici. Che cosa hanno in più rispetto alla maggior parte delle euristiche usate in pratica?
Una garanzia dimostrata sul rapporto fra $\mathscr{A}(I)$ e $z(I)$
La soluzione ottima su tutte le istanze piccole
L'uso di scelte casuali per uscire dagli ottimi locali
Un tempo di calcolo polinomiale nella dimensione dell'istanza
Spiegazione. Anche un'euristica qualunque è di solito polinomiale; la differenza è la garanzia sul rapporto, valida per tutte le istanze. La qualità delle altre euristiche si valuta sulle istanze da risolvere.
Istanza di $P\,||\,C_{\max}$ (lavori su $m$ macchine identiche, si minimizza il makespan, cioè il carico massimo): $m=3$ e tempi $t=(5,5,4,4,3,3,3)$. Quale lower bound sul makespan si ricava, e quale soluzione lo raggiunge?
$10$, raggiunto da $\{1,5,6\},\{2,3\},\{4,7\}$
$5=\max_jt_j$, raggiunto da $\{1,5\},\{2,6\},\{3,4,7\}$
$9=\lceil27/3\rceil$, raggiunto da $\{1,2\},\{3,4\},\{5,6,7\}$
$9=\lceil27/3\rceil$, raggiunto da $\{1,3\},\{2,4\},\{5,6,7\}$
Spiegazione. Il lower bound è $\max\{\max_jt_j,\lceil\sum_jt_j/m\rceil\}=\max\{5,9\}=9$, e i carichi $(9,9,9)$ lo raggiungono: $z(I)=9$. $\{1,2\}$ ha carico $10$.
Le note sugli algoritmi euristici usano quattro istanze di riferimento (zaino, bin packing, TSP, $P\,||\,C_{\max}$) di cui è noto il valore ottimo $z(I)$. A che cosa serve conoscerlo?
A sostituire il bound duale nel calcolo del gap
A scegliere le istanze più difficili per ogni euristica
A misurare esattamente l'errore di ogni soluzione euristica
A rendere esatte le euristiche su quelle istanze
Spiegazione. Con $z(I)$ noto si calcola l'errore relativo, non solo il gap. Nella pratica $z(I)$ è ignoto e serve un bound duale.
Gli algoritmi euristici si classificano in euristiche costruttive, ricerca locale, metaeuristiche ed euristiche basate sulla PLI. Che cosa caratterizza un'euristica costruttiva?
Accetta soluzioni peggiori per lasciare un ottimo locale
Estende una soluzione parziale e non rivede mai una scelta
Parte da una soluzione completa e la migliora con piccole modifiche
Usa un solver MIP per esplorare grandi insiemi di soluzioni
Spiegazione. Le altre tre opzioni descrivono, nell'ordine, la ricerca locale, le euristiche basate sulla PLI e le metaeuristiche.
Che cosa usano le euristiche basate sulla programmazione lineare intera (PLI), una delle quattro classi di algoritmi euristici?
Una formulazione MIP, il suo rilassamento e un solver MIP
Una popolazione di soluzioni che si ricombinano
Solo mosse elementari su una soluzione completa
Solo un ordinamento degli elementi secondo un criterio
Spiegazione. Usano il modello per guidare la ricerca o per esplorare grandi insiemi di soluzioni, e possono partire dalla soluzione di un'altra euristica.
Per i quattro problemi delle note sulle euristiche le soluzioni si rappresentano con: un vettore binario $x$ (zaino), un vettore $bin$ (bin packing), una permutazione $\sigma$ (TSP), un vettore $mach$ ($P\,||\,C_{\max}$). Quali rappresentazioni descrivono sempre soluzioni ammissibili?
Tutte e quattro le rappresentazioni
Il vettore $x$ dello zaino e il vettore $bin$ del bin packing
Solo il vettore $x$ dello zaino
La permutazione del TSP e il vettore $mach$
Spiegazione. Ogni permutazione è un giro e ogni assegnamento dei lavori è uno schedule. Un vettore $x$ può superare la capacità e un vettore $bin$ può riempire troppo un contenitore.
Nel bin packing con $n$ oggetti una soluzione si rappresenta con il vettore $bin$, dove $bin_j$ è il contenitore dell'oggetto $j$. Quanto è grande al più lo spazio di ricerca, e ogni vettore è una soluzione ammissibile?
$n!$; sì, ogni vettore è ammissibile
Al più $n^n$; sì, ogni vettore è una partizione ammissibile
Al più $n^n$; no, un contenitore può superare la capacità
$2^n$; sì, ogni vettore è ammissibile
Spiegazione. Ogni oggetto ha al più $n$ contenitori possibili: $n^n$ vettori. Un vettore è sempre una partizione, ma non sempre rispetta la capacità.
Zaino con $c=9$, profitti $p=(10,7,6,4)$, pesi $w=(5,4,3,3)$ e soluzione $x=(1,0,1,0)$ (oggetti $1,3$, profitto $16$). L'intorno flip aggiunge o toglie un oggetto; l'intorno swap toglie un oggetto scelto e ne aggiunge uno non scelto. $x$ è un ottimo locale?
No per entrambi gli intorni
Sì per flip, no per swap
No per flip, sì per swap
Sì per entrambi gli intorni
Spiegazione. Flip: aggiungere $2$ o $4$ supera $9$, togliere un oggetto peggiora. Swap: togliere $3$ e aggiungere $2$ dà peso $9$ e profitto $17$. Essere un ottimo locale dipende dall'intorno.
Un intorno è esatto se ogni suo ottimo locale è un ottimo globale. Quale dei seguenti intorni è esatto?
Arco entrante e arco uscente, per l'albero ricoprente minimo
Il flip (aggiungere o togliere un oggetto), per lo zaino
Lo spostamento di un oggetto, per il bin packing
Il $2$-opt (sostituzione di due archi), per il TSP
Spiegazione. Gli intorni esatti esistono per problemi polinomiali (albero ricoprente minimo, vertici adiacenti del simplesso). Per i problemi NP-hard gli intorni piccoli non sono esatti.
I valori delle soluzioni, visti come funzione sullo spazio di ricerca, formano il paesaggio esplorato da un'euristica. Per un problema di minimo, che cosa sono gli ottimi locali e l'ottimo globale?
I bordi dello spazio di ricerca; il globale è il più lontano
Le cime dei rilievi; il globale è la cima più alta
I punti di passaggio fra due valli; il globale è il più basso
I fondi delle valli; il globale è il fondo della valle più profonda
Spiegazione. Per un minimo un ottimo locale non ha vicini migliori, cioè più bassi: è un fondo di valle.
Fra intensificazione (cercare meglio dove ci sono già buone soluzioni) e diversificazione (spostarsi in regioni non ancora esplorate), dove si colloca la ricerca locale pura?
Bilancia le due grazie alle mosse peggioranti
Non fa né l'una né l'altra: sceglie a caso
È pura intensificazione: si ferma al primo ottimo locale
È pura diversificazione: esplora tutte le valli
Spiegazione. La ricerca locale scende nella valle corrente finché un vicino migliora; uscire dalla valle è il compito delle metaeuristiche.
Un algoritmo euristico si può valutare con l'analisi del caso peggiore o con l'analisi sperimentale. Che cosa dà l'analisi sperimentale?
Un bound duale migliore per il calcolo del gap
Il comportamento tipico su istanze di benchmark
Una garanzia valida per tutte le istanze del problema
Il valore ottimo di ogni istanza di benchmark
Spiegazione. Misura gap e tempi su un insieme di istanze abbastanza grande e vario. Il caso peggiore dà garanzie per tutte le istanze, spesso lontane dal comportamento tipico.
Per un problema di ottimizzazione con valore ottimo $z(I)$ sull'istanza $I$, che cosa distingue un algoritmo euristico da un algoritmo esatto?
Può restituire soluzioni non ammissibili, purché di buon valore
Restituisce sempre una soluzione ottima, ma senza dimostrarlo
Restituisce un bound duale invece di una soluzione
Restituisce una soluzione ammissibile, di solito in poco tempo, senza garantire che sia ottima
Spiegazione. Un'euristica scambia qualità con tempo: calcola rapidamente una soluzione ammissibile il cui valore si spera vicino a $z(I)$, ma in generale non sa quanto ne dista.
Perché si usano algoritmi euristici per problemi NP-difficili come lo zaino, il bin packing, il TSP e $P\,||\,C_{\max}$, anche se esistono algoritmi esatti?
Perché le euristiche trovano sempre l'ottimo sulle istanze grandi
Perché le euristiche danno anche un bound duale gratis
Gli algoritmi esatti possono richiedere tempo esponenziale, mentre spesso serve una buona soluzione in poco tempo
Perché gli algoritmi esatti non esistono per questi problemi
Spiegazione. Per i problemi NP-difficili non si conoscono algoritmi esatti polinomiali; un'euristica dà in fretta una soluzione ammissibile, cioè un bound primale, da usare da sola o come punto di partenza.
Nelle note sulle euristiche, ogni istanza dello zaino (KP: pesi $w_j$, capacità $c$) soddisfa $w_j\le c$ per ogni oggetto e $\sum_j w_j>c$. Perché si esclude il caso $\sum_j w_j\le c$?
Perché l'oggetto critico sarebbe il primo
È banale: tutti gli oggetti entrano, e prenderli tutti è ottimo
Perché l'istanza non ha soluzioni ammissibili
Perché il rilassamento lineare diventerebbe illimitato
Spiegazione. Se tutti gli oggetti stanno insieme nello zaino, con profitti positivi la soluzione ottima li prende tutti, e non serve nessuna euristica. $w_j\le c$ esclude invece gli oggetti che non entrano mai.
Nelle note sulle euristiche, ogni istanza di $P\,||\,C_{\max}$ ($n$ lavori, $m$ macchine identiche) soddisfa $n>m$. Che cosa succederebbe con $n\le m$?
Un lavoro per macchina sarebbe ottimo, con makespan $\max_j t_j$
Il makespan ottimo sarebbe $\sum_j t_j/m$
Servirebbe la programmazione dinamica per risolverlo
Il problema non avrebbe soluzioni ammissibili
Spiegazione. Con almeno tante macchine quanti lavori, ogni lavoro va su una macchina diversa e il makespan è il lavoro più lungo, che è anche un lower bound: l'istanza è banale.
Per un problema di minimo, un'euristica trova una soluzione di valore $\mathscr{A}(I)=25$ e un bound duale vale $\mathrm{LB}(I)=20$, quindi $20\le z(I)\le 25$. Il gap relativo è $\frac{\mathscr{A}(I)-\mathrm{LB}(I)}{\mathrm{LB}(I)}$. Quanto vale, e che cosa garantisce?
$5$: la soluzione dista esattamente $5$ dall'ottimo
$20\%$: l'errore relativo della soluzione è esattamente $20\%$
$25\%$: l'errore relativo della soluzione è almeno $25\%$
$25\%$: l'errore relativo della soluzione è al più $25\%$
Spiegazione. $(25-20)/20=25\%$. Poiché $\mathrm{LB}(I)\le z(I)$, l'errore relativo $\frac{\mathscr{A}(I)-z(I)}{z(I)}$ non supera il gap; il valore ottimo resta ignoto fra $20$ e $25$.
Gli algoritmi euristici si dividono in quattro classi: euristiche costruttive, ricerca locale, metaeuristiche ed euristiche basate sulla programmazione lineare intera (MIP). Quale affermazione sulle classi è corretta?
Le euristiche costruttive migliorano una soluzione completa, la ricerca locale la costruisce
Le euristiche MIP non usano mai soluzioni trovate da altre euristiche
Non sono alternative: una ricerca locale parte di solito da una soluzione costruttiva, e una metaeuristica contiene ricerche locali
Sono alternative: un algoritmo appartiene a una sola classe e non usa le altre
Spiegazione. Le classi si combinano: costruire, migliorare con una ricerca locale, uscire dagli ottimi locali con una metaeuristica; un'euristica MIP può partire da una soluzione nota e migliorarla.
A quale classe di algoritmi euristici appartiene un metodo che, partendo da una soluzione completa, la sostituisce ripetutamente con una soluzione vicina migliore finché ne esiste una?
Euristica basata sulla programmazione lineare intera
Ricerca locale
Euristica costruttiva
Metaeuristica
Spiegazione. Una ricerca locale migliora una soluzione completa con mosse in un intorno e si ferma in un ottimo locale; una costruttiva parte invece dalla soluzione vuota, e una metaeuristica accetta anche mosse peggioranti per uscire dagli ottimi locali.
Per lo zaino 0-1 con $n$ oggetti una soluzione si rappresenta con un vettore binario di lunghezza $n$. Lo spazio di ricerca contiene anche vettori che superano la capacità. Che cosa deve fare un'euristica con questi oggetti?
Limitarsi ai vettori ammissibili, oppure accettare quelli inammissibili penalizzandoli
Restituirli come soluzione, se hanno profitto maggiore
Trasformarli in ammissibili aumentando la capacità
Ignorarli: un vettore inammissibile non può mai essere generato
Spiegazione. Quando la rappresentazione descrive anche oggetti inammissibili, l'euristica li evita oppure li ammette con una penalità nell'obiettivo, per esempio sul peso in eccesso.
Per $P\,||\,C_{\max}$ una soluzione si rappresenta con il vettore che dà la macchina di ogni lavoro. Quanti vettori contiene lo spazio di ricerca con $n=6$ lavori e $m=3$ macchine?
$18$
$216$
$90$
$729$
Spiegazione. Ogni lavoro sceglie una delle $3$ macchine: $3^6=729$. Molti vettori descrivono lo stesso schedule, perché le macchine sono identiche; $6^3=216$ scambia i ruoli di $n$ e $m$.
In un problema di minimo con funzione obiettivo $f$, una soluzione $S$ è un ottimo locale rispetto all'intorno $N$ se $f(S)\le f(S')$ per ogni $S'\in N(S)$. Quale affermazione è corretta?
Un ottimo globale può non essere un ottimo locale, se l'intorno è grande
Un ottimo locale non esiste se l'intorno non è esatto
Un ottimo globale è un ottimo locale per ogni intorno; un ottimo locale può non essere globale
Un ottimo locale è un ottimo globale per ogni intorno
Spiegazione. Nessuna soluzione è migliore di un ottimo globale, quindi nemmeno i suoi vicini. Il contrario vale solo per gli intorni esatti.
Nelle euristiche si parla di intensificazione e diversificazione dell'esplorazione dello spazio di ricerca. Che cosa significano?
Sono sinonimi: entrambe indicano l'uso di numeri casuali
Intensificare è cercare meglio vicino alle buone soluzioni trovate; diversificare è spostarsi in regioni non ancora esplorate
Intensificare è aumentare il numero di iterazioni; diversificare è usare più processori
Intensificare è accettare mosse peggioranti; diversificare è accettare solo mosse miglioranti
Spiegazione. L'intensificazione scende verso il fondo della valle corrente; la diversificazione la abbandona, anche attraverso soluzioni peggiori, per raggiungerne un'altra.
Come si valuta in modo corretto un'euristica che fa scelte casuali (per esempio con un generatore di numeri pseudo-casuali)?
Non si può valutare: i risultati casuali non sono confrontabili
Si esegue una sola volta, con il seme che dà il risultato migliore
Si confronta il suo risultato migliore con il risultato peggiore delle altre euristiche
Si risolve ogni istanza più volte con semi diversi e si riportano media e dispersione dei risultati
Spiegazione. I risultati dipendono dai numeri casuali: un solo seme non dice nulla. Le euristiche si confrontano sulle stesse istanze e con lo stesso tempo di calcolo.
Su un'istanza del TSP, la stessa regola costruttiva applicata da città di partenza diverse dà giri lunghi fra $18$ e $25$. Che cosa insegna questo fatto sulla valutazione delle euristiche?
Basta riportare il valore migliore, $18$, come qualità dell'euristica
La lunghezza ottima è la media, $21{,}5$
Una sola istanza o una sola esecuzione non dimostra nulla: servono molte istanze e confronti a parità di tempo
La regola è sbagliata, perché un'euristica deve dare sempre lo stesso valore
Spiegazione. Il risultato di un'euristica varia con le istanze e con le scelte iniziali; l'analisi sperimentale misura gap e tempi su molte istanze, l'analisi nel caso peggiore dà garanzie valide sempre.
Per il TSP, siano $a_i$ e $b_i$ le due distanze minime dalla città $i$ alle altre. Il bound $z(I)\ge\lceil\frac12\sum_i(a_i+b_i)\rceil$ si dimostra così: in ogni giro ogni città è estremo di due lati lunghi almeno $a_i$ e $b_i$. Perché compare il fattore $\frac12$?
Per tenere conto delle distanze asimmetriche
Sommando sulle città ogni lato del giro è contato due volte, una per ciascun estremo
Perché si usa solo una delle due distanze minime
Perché il giro ha $n/2$ lati
Spiegazione. $2L(\sigma)=\sum_i$(lunghezze dei due lati in $i$)$\ge\sum_i(a_i+b_i)$; l'arrotondamento per eccesso vale perché le distanze sono intere.
Un'istanza del TSP con $4$ città ha distanze $d_{12}=2$, $d_{13}=4$, $d_{14}=3$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$. Con $a_i,b_i$ le due distanze minime dalla città $i$, quanto vale il bound $\lceil\frac12\sum_i(a_i+b_i)\rceil$?
$10$
$19$
$11$
$9$
Spiegazione. Città $1$: $2+3$; città $2$: $2+3$; città $3$: $2+3$; città $4$: $2+3$. Somma $20$, metà $10$. Il giro $1,2,3,4$ vale $2+3+2+3=10$, quindi il bound è esatto qui.
Un intorno $N$ è esatto: ogni ottimo locale rispetto a $N$ è un ottimo globale. Una ricerca locale con l'intorno $N$ si ferma nella soluzione $S$. Che cosa si può concludere?
$S$ è una soluzione ottima
$S$ è ottima solo con best improvement
$S$ ha gap nullo solo se c'è un bound duale
Nulla: l'esattezza riguarda la grandezza dell'intorno
Spiegazione. La ricerca locale si ferma in un ottimo locale rispetto a $N$ e, per definizione di intorno esatto, ogni ottimo locale è globale. La regola di scelta del vicino non conta.
Problema di minimo, valori positivi: un'euristica trova $\mathscr{A}(I)=12$ e un bound duale vale $\mathrm{LB}(I)=10$. Che cosa garantisce la proposizione sul gap per l'errore relativo $\frac{\mathscr{A}(I)-z(I)}{z(I)}$?
È al più $16{,}7\%$
È esattamente $20\%$
È almeno $20\%$
È al più $20\%$
Spiegazione. $gap(I)=\frac{12-10}{10}=20\%$ e l'errore relativo è al più il gap, perché $10\le z(I)\le 12$. $16{,}7\%$ divide per il bound maggiore; l'errore è $20\%$ solo se $z(I)=10$.
TSP con $5$ città e distanze intere: le somme $a_i+b_i$ delle due distanze più piccole da ogni città valgono $6,7,7,8,9$. Che cosa dà il bound delle due distanze minime?
$z(I)\ge 18$
$z(I)\le 19$
$z(I)\ge 19$
$z(I)\ge 37$
Spiegazione. $z(I)\ge\lceil\frac12(6+7+7+8+9)\rceil=\lceil 18{,}5\rceil=19$: ogni città ha due lati del giro, e ogni lato è contato da due città. È un bound inferiore, non superiore.
Quale affermazione vale per ogni intorno $N$ di un problema di ottimizzazione?
Un ottimo locale rispetto a $N$ non ha vicini
Ogni soluzione ottima è un ottimo locale rispetto a $N$
Ogni ottimo locale rispetto a $N$ è una soluzione ottima
Due ottimi locali rispetto a $N$ hanno lo stesso valore
Spiegazione. Nessuna soluzione è migliore di un ottimo globale, quindi nemmeno i suoi vicini: è un ottimo locale per ogni intorno. Il viceversa vale solo per gli intorni esatti.
Problema di massimo: un'euristica trova $\mathscr{A}(I)=40$ e un bound duale vale $\mathrm{UB}(I)=50$. Quanto vale il gap e che cosa garantisce?
$25\%$: l'errore relativo di $40$ è al più $25\%$
$20\%$: l'errore relativo è almeno $20\%$
$25\%$: quindi $z(I)=50$
$20\%$: il gap si divide per $\mathrm{UB}(I)$
Spiegazione. Il gap divide per il bound minore, qui il valore euristico: $\frac{50-40}{40}=25\%$, e l'errore relativo è al più il gap. Il valore ottimo sta fra $40$ e $50$, non è per forza $50$.
La proposizione «l'errore relativo di $\mathscr{A}$ su $I$ è al più $gap(I)$», con $gap(I)=\frac{\mathrm{UB}-\mathrm{LB}}{\mathrm{LB}}$, quale ipotesi sui valori richiede?
L'euristica è una ricerca locale con un intorno esatto
Il problema è di massimo e non di minimo
I dati dell'istanza sono tutti interi
Il bound minore $\mathrm{LB}(I)$ è positivo
Spiegazione. Il gap divide per il bound minore: serve $\mathrm{LB}(I)>0$ (valori positivi). Vale per ogni euristica, per problemi di minimo e di massimo, con dati qualsiasi.
Nel bound $z(I)\ge\lceil\frac12\sum_i(a_i+b_i)\rceil$ del TSP, perché si può arrotondare per eccesso?
Il numero di città è pari
Il giro parte sempre dalla città $1$
Le distanze sono intere, quindi lo è $z(I)$
Le distanze rispettano la disuguaglianza triangolare
Spiegazione. Con distanze intere la lunghezza di ogni giro è intera, e un intero non minore di $18{,}5$ è almeno $19$. La disuguaglianza triangolare non serve, e la città di partenza non conta.
Che cosa richiede la definizione di algoritmo euristico per un problema di ottimizzazione $\mathscr{P}$?
Un tempo di calcolo lineare nella dimensione
Una soluzione ammissibile per ogni istanza
Una soluzione ottima almeno sulle istanze piccole
Una garanzia sul rapporto con l'ottimo
Spiegazione. Un'euristica calcola una soluzione ammissibile di ogni istanza, senza garantire che sia ottima. La garanzia sul caso peggiore è propria degli algoritmi di approssimazione.
Un intorno associa a ogni soluzione ammissibile $S$ un insieme $N(S)$ di vicini. Che cosa si richiede ai vicini?
Che siano soluzioni ammissibili
Che siano migliori di $S$
Che differiscano da $S$ in una variabile
Che siano ottimi locali
Spiegazione. $N(S)\subseteq\mathscr{F}(I)$: i vicini sono soluzioni ammissibili. Non devono essere migliori, e la mossa che li produce dipende dall'intorno scelto.
Problema di massimo con funzione obiettivo $f$. Quando $S$ è un ottimo locale rispetto all'intorno $N$?
Se $f(S)>f(S')$ per ogni $S'\in N(S)$
Se $f(S)\ge f(S')$ per almeno un $S'\in N(S)$
Se $f(S)\le f(S')$ per ogni $S'\in N(S)$
Se $f(S)\ge f(S')$ per ogni $S'\in N(S)$
Spiegazione. Nessun vicino è migliore: $f(S)\ge f(S')$ per tutti i vicini. La disuguaglianza non deve essere stretta (vicini di pari valore sono ammessi); $\le$ è la condizione per i problemi di minimo.
Problema di minimo: il valore euristico $\mathscr{A}(I)$ è uguale a un bound duale $\mathrm{LB}(I)$. Che cosa si conclude, e su che cosa si basa?
Nulla: il gap è nullo ma l'errore no
$\mathscr{A}(I)=z(I)$ solo con dati interi
$\mathscr{A}(I)$ è ottimo, perché $\mathrm{LB}(I)\le z(I)$
$\mathscr{A}(I)$ è ottimo solo se l'euristica è esatta
Spiegazione. $\mathrm{LB}(I)\le z(I)\le\mathscr{A}(I)=\mathrm{LB}(I)$: la soluzione è ottima e lo certifica il bound duale. Non servono altre ipotesi sull'euristica o sui dati.
Per un problema con un numero finito di soluzioni ammissibili, quale intorno è esatto qualunque sia l'istanza?
L'intorno 2-opt del TSP
L'intorno move di $P\,||\,C_{\max}$
Quello con ogni soluzione vicina delle altre
L'intorno flip del problema dello zaino 0/1
Spiegazione. Con $N(S)=\mathscr{F}(I)$ un ottimo locale non ha soluzioni migliori: è globale. Flip, 2-opt e move hanno ottimi locali non globali (esempi del capitolo e della ricerca locale).
TSP: un giro lungo $25$, un bound duale $\mathrm{LB}(I)=17$ e il valore ottimo $z(I)=18$. Quanto valgono il gap e l'errore relativo $\frac{\mathscr{A}(I)-z(I)}{z(I)}$?
Gap ed errore $\approx47{,}1\%$
Gap $\approx47{,}1\%$, errore $\approx38{,}9\%$
Gap $\approx32\%$, errore $\approx28\%$
Gap $\approx38{,}9\%$, errore $\approx47{,}1\%$
Spiegazione. $gap=\frac{25-17}{17}\approx47{,}1\%$ ed errore $=\frac{25-18}{18}\approx38{,}9\%$: l'errore è al più il gap. $32\%$ e $28\%$ dividono per $25$, il valore maggiore.
Quale classe di euristiche costruisce una sola soluzione, un elemento alla volta, senza mai rivedere una scelta?
La ricerca locale da una soluzione
Le metaeuristiche, a partire da un ottimo
Le euristiche basate sulla PLI
Le euristiche costruttive
Spiegazione. È la definizione delle euristiche costruttive. La ricerca locale modifica una soluzione completa, le metaeuristiche guidano la ricerca locale, le euristiche MIP usano un modello e un solver.
Spiegazione. La rappresentazione è la struttura dati delle soluzioni; lo spazio di ricerca è l'insieme di tutti gli oggetti che può descrivere, che può contenere anche oggetti non ammissibili.
Che cosa si intende per intensificazione in un algoritmo euristico?
Cercare vicino alle soluzioni buone trovate
Spostarsi in regioni dello spazio non ancora esplorate
Calcolare un bound duale più forte
Aumentare il numero delle istanze di prova
Spiegazione. Intensificare è scendere verso il fondo della valle corrente; la diversificazione porta in regioni nuove. La ricerca locale è pura intensificazione.
Un'euristica diversifica troppo e intensifica poco. Che cosa succede?
Resta intrappolata nella prima valle
Trova sempre l'ottimo globale
Si ferma subito in un ottimo locale
Vaga senza scendere in fondo a una valle
Spiegazione. Troppa diversificazione fa vagare la ricerca senza mai arrivare al fondo di una valle; troppa intensificazione la intrappola nella prima. Ogni metaeuristica bilancia le due.
Con che cosa si misura la qualità di un'euristica su un'istanza di cui non si conosce il valore ottimo?
Con il numero di iterazioni eseguite
Con il tempo di calcolo e basta
Con il gap rispetto al miglior bound duale
Con l'errore relativo rispetto all'ottimo
Spiegazione. Senza il valore ottimo l'errore relativo non si calcola: si usa il gap rispetto al miglior bound duale disponibile, che è un limite superiore dell'errore.
Perché l'analisi sperimentale di un'euristica deve usare un insieme di istanze grande e vario?
Per ottenere una garanzia sul caso peggiore
Per non trarre conclusioni valide solo su poche istanze
Perché su istanze piccole non termina
Perché il gap si calcola solo su molte istanze
Spiegazione. Un'euristica può andare bene su alcune istanze e male su altre: poche istanze danno conclusioni non generali. Le garanzie sul caso peggiore vengono dall'analisi teorica, non dagli esperimenti.
Nello scheduling $P\,||\,C_{\max}$ ($m$ macchine identiche, makespan ottimo $z(I)$), $LIST$ assegna i lavori nell'ordine di una lista alla macchina meno carica, e $LPT$ fa lo stesso con la lista ordinata per durata non crescente. Quali garanzie valgono?
$LIST(I)\le\left(2-\frac1m\right)z(I)$ e $LPT(I)\le\left(\frac43-\frac1{3m}\right)z(I)$
$LIST(I)\le\left(2-\frac1m\right)z(I)$ e $LPT(I)\le\left(\frac54-\frac1{4m}\right)z(I)$
$LIST(I)\le\frac32\,z(I)$ e $LPT(I)\le\frac{17}{10}\,z(I)$
$LIST(I)\le\left(\frac43-\frac1{3m}\right)z(I)$ e $LPT(I)\le\left(2-\frac1m\right)z(I)$
Spiegazione. Graham: la lista qualsiasi garantisce $2-\frac1m$; ordinarla per tempo non crescente abbassa la garanzia a $\frac43-\frac1{3m}$.
La colorazione greedy $GC$ scorre i vertici di $G$ nell'ordine di una lista e dà a ciascuno il colore più piccolo non usato dai vicini già colorati; $\Delta(G)$ è il grado massimo e $\chi(G)$ il numero cromatico. Quale affermazione è corretta?
$GC(I)\le\Delta(G)+1$ per ogni lista, e su grafi bipartiti dà sempre $2$ colori
$GC(I)\le\Delta(G)$ per ogni grafo connesso e per ogni lista dei vertici
$GC(I)\le\chi(G)+1$ per ogni lista, quindi $GC$ sbaglia al più di un colore
$GC(I)\le\Delta(G)+1$ per ogni lista, ma su grafi bipartiti una lista può dare $n/2$ colori
Spiegazione. Un vertice ha al più $\Delta(G)$ vicini già colorati, quindi trova un colore fra i primi $\Delta(G)+1$. I grafi corona hanno $\chi=2$ ma, con una lista sfavorevole, $GC=n/2$.
Nel bin packing, First Fit (FF) mette ogni oggetto, nell'ordine dato, nel primo contenitore in cui entra; First Fit Decreasing (FFD) fa lo stesso dopo aver ordinato gli oggetti per peso non crescente. Quale affermazione è corretta?
FFD usa sempre il numero ottimo di contenitori
FF e FFD usano sempre lo stesso numero di contenitori
Esistono istanze su cui FFD usa più contenitori di FF
FFD usa sempre al più tanti contenitori quanti FF
Spiegazione. Ordinare gli oggetti aiuta in media e nel caso peggiore, ma non istanza per istanza: le dispense mostrano un'istanza su cui FFD usa un contenitore in più di FF.
In un'euristica di inserimento per il TSP simmetrico (distanze $d_{ij}$), il sottogiro corrente contiene il lato $(i,j)$ con $d_{ij}=7$; la città $k$ ha $d_{ik}=4$ e $d_{kj}=5$. Di quanto aumenta la lunghezza del sottogiro se si inserisce $k$ fra $i$ e $j$?
$-2$
$2$
$9$
$16$
Spiegazione. $\Delta(i,k,j)=d_{ik}+d_{kj}-d_{ij}=4+5-7=2$: il lato $(i,j)$ è sostituito dai lati $(i,k)$ e $(k,j)$.
Per il problema dello zaino (KP), il greedy esamina gli oggetti in un ordine e prende ogni oggetto che entra: per profitto non crescente ($GR_p$), per peso non decrescente ($GR_w$) o per efficienza $p_j/w_j$ non crescente ($GR$). Quale affermazione è corretta?
Ognuno dei tre ordini può dare soluzioni arbitrariamente cattive
$GR$ per efficienza dà sempre il valore ottimo
$GR_w$ dà sempre il valore ottimo, perché sceglie più oggetti
$GR_p$ dà sempre almeno metà del valore ottimo
Spiegazione. Per ciascun ordine esiste una famiglia di istanze su cui il rapporto con l'ottimo cresce senza limite (per $GR$: un oggetto piccolo efficientissimo che blocca uno grande); garanzie costanti richiedono algoritmi come $GR^e$.
Un'euristica costruttiva parte dalla soluzione parziale vuota e la estende con un elemento alla volta. Per $P\,||\,C_{\max}$ ($n$ lavori su $m$ macchine identiche), quali sono gli elementi?
I carichi delle macchine, uno alla volta
Gli scambi di due lavori fra due macchine
Le macchine, aperte una alla volta
Gli assegnamenti di un lavoro a una macchina
Spiegazione. Ogni passo assegna un lavoro a una macchina. Gli scambi sono mosse di ricerca locale, che modificano una soluzione completa.
Da che cosa dipende soprattutto la qualità della soluzione di un'euristica costruttiva (che estende la soluzione parziale vuota un elemento alla volta)?
Dalla soluzione completa da cui parte la ricerca
Dal numero di iterazioni di miglioramento eseguite
Da come si sceglie, a ogni passo, l'elemento da aggiungere
Dal bound duale usato come criterio di arresto
Spiegazione. Parte sempre dalla soluzione vuota e si ferma quando la soluzione è completa: tutto sta nel criterio di scelta.
In $P\,||\,C_{\max}$, $mach_j$ è la macchina del lavoro $j$ e $L_h$ il carico (somma dei tempi) della macchina $h$. Con $m=3$, tempi $t=(5,5,4,4,3,3,3)$ e $mach=(1,2,3,3,1,2,1)$, quali sono i carichi e il makespan?
$(11,8,8)$, makespan $11$
$(11,8,8)$, makespan $8$
$(9,9,9)$, makespan $9$
$(13,8,6)$, makespan $13$
Spiegazione. Macchina $1$: lavori $1,5,7$, $5+3+3=11$; macchina $2$: lavori $2,6$, $8$; macchina $3$: lavori $3,4$, $8$. Il makespan è il carico massimo, non il minimo.
Bin packing con $c=7$ e pesi $w=(4,4,5,3,2,3)$. Una soluzione ha $bin=(2,3,1,2,1,3)$ ($bin_j$ = contenitore dell'oggetto $j$). Quali sono le capacità residue dei contenitori $1,2,3$?
$(0,1,2)$: un solo contenitore è pieno
$(7,7,7)$: i contenitori sono vuoti
$(2,3,3)$: restano spazi in tutti i contenitori
$(0,0,0)$: tre contenitori pieni, soluzione ottima
Spiegazione. Contenitore $1$: oggetti $3,5$, $5+2=7$; contenitore $2$: oggetti $1,4$, $7$; contenitore $3$: oggetti $2,6$, $7$. Il peso totale è $21=3c$, quindi $3$ contenitori sono ottimi.
Nelle euristiche costruttive, il test di ammissibilità controlla se la soluzione parziale estesa si può ancora completare. Per quali dei problemi zaino, bin packing, TSP e $P\,||\,C_{\max}$ questo test è sempre superato?
Lo zaino e il bin packing
Solo il TSP, non gli altri
TSP e $P\,||\,C_{\max}$
Nessuno dei quattro problemi
Spiegazione. Ogni sequenza di città si chiude in un giro e ogni assegnamento di lavori è uno schedule. Nello zaino un oggetto può non entrare, nel bin packing un oggetto può non entrare in un contenitore.
In un algoritmo greedy un criterio di selezione è statico se il valore di un elemento non dipende dalla soluzione parziale, dinamico se cambia mentre la soluzione cresce. Quale criterio è dinamico?
Il tempo di esecuzione dei lavori di $P\,||\,C_{\max}$
La distanza dall'ultima città di un giro parziale
L'efficienza $p_j/w_j$ degli oggetti dello zaino
Il peso degli oggetti del bin packing
Spiegazione. L'ultima città cambia a ogni passo, quindi le distanze vanno ricalcolate. Gli altri criteri permettono di ordinare gli elementi una sola volta, in $O(n\log n)$.
Zaino con $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$ (ottimo $17$). Il greedy prende ogni oggetto che entra, esaminandoli per profitto ($GR_p=17$), per peso ($GR_w=10$) o per efficienza $p_j/w_j$ ($GR=16$). Che cosa mostra l'esempio?
Qui vince il profitto, ma nessun ordine è il migliore su ogni istanza
L'ordine per efficienza è il migliore su ogni istanza
L'ordine per peso trova sempre l'ottimo
Il greedy per profitto è un algoritmo esatto per lo zaino
Spiegazione. Su questa istanza $GR_p$ riempie esattamente lo zaino con $\{1,2\}$; ma ciascuno dei tre ordini può essere arbitrariamente cattivo su altre istanze.
Zaino con $c=10$ e due oggetti $(p_1,w_1)=(2,1)$, $(p_2,w_2)=(10,10)$. Il greedy prende ogni oggetto che entra, esaminandoli per profitto non crescente ($GR_p$), per peso non decrescente ($GR_w$) o per efficienza $p_j/w_j$ non crescente ($GR$). Quanto valgono?
$GR_p=2$, $GR_w=2$, $GR=2$
$GR_p=10$, $GR_w=10$, $GR=2$
$GR_p=10$, $GR_w=2$, $GR=10$
$GR_p=10$, $GR_w=2$, $GR=2$
Spiegazione. L'oggetto $1$ ha efficienza $2$ e peso $1$: $GR_w$ e $GR$ lo prendono per primo, e poi l'oggetto $2$ non entra. $GR_p$ prende l'oggetto $2$, che è l'ottimo. Con $c$ grande il rapporto $z/GR=c/2$ cresce senza limite.
Nel bin packing con capacità $c$, le euristiche «prima ordinare, poi riempire» inseriscono prima gli oggetti più pesanti. Perché?
Perché gli oggetti grandi valgono di più nella funzione obiettivo
Perché con l'ordinamento First Fit diventa un algoritmo esatto
Gli oggetti grandi entrano solo in contenitori quasi vuoti; i piccoli riempiono i vuoti
Perché gli oggetti piccoli, se arrivano tardi, non entrano più
Spiegazione. Due oggetti più grandi di $c/2$ non stanno mai insieme; se i piccoli arrivano prima occupano lo spazio che servirà ai grandi. L'ordinamento migliora la garanzia ma non rende esatto l'algoritmo.
Bin packing con $c=7$ e pesi $w=(4,4,5,3,2,3)$ (ottimo $3$). First Fit (ogni oggetto, nell'ordine dato, nel primo contenitore in cui entra) usa $4$ contenitori; First Fit Decreasing (stesso, dopo l'ordinamento per peso non crescente) ne usa $3$. Che cosa spiega la differenza?
FFD apre tutti i contenitori già all'inizio
In FF l'oggetto da $2$ occupa lo spazio che serviva a quello da $3$
FFD usa la capacità residua minima invece del primo contenitore
FF tiene aperto un solo contenitore alla volta
Spiegazione. In FF l'oggetto $5$ (peso $2$) va nel contenitore $2$ e l'oggetto $6$ (peso $3$) non entra più da nessuna parte; in FFD l'oggetto da $2$ arriva per ultimo e riempie il vuoto del contenitore $1$.
First Fit Decreasing per il bin packing ordina gli $n$ oggetti per peso non crescente e poi li inserisce con First Fit, scandendo i contenitori aperti. Quanto tempo richiede?
$O(n^2)$, come First Fit
$O(n\log n)$, il tempo dell'ordinamento
$O(n)$, una passata sugli oggetti
$O(2^n)$, perché prova tutti gli ordini
Spiegazione. L'ordinamento costa $O(n\log n)$, ma la scansione dei contenitori per ogni oggetto costa $O(n^2)$ in tutto, come in First Fit.
Best Fit Decreasing per il bin packing ordina gli oggetti per peso non crescente e mette ciascuno nel contenitore con capacità residua minima fra quelli in cui entra (pareggi: il primo aperto). Con $c=7$, dopo tre oggetti i residui sono $(2,3,3)$ e arriva un oggetto di peso $3$. Dove va?
Nel contenitore $3$
In un nuovo contenitore
Nel contenitore $1$
Nel contenitore $2$
Spiegazione. Entra nei contenitori $2$ e $3$, entrambi con residuo $3$: il pareggio va al primo aperto. Il contenitore $1$ ha il residuo minimo ma l'oggetto non vi entra.
Per First Fit Decreasing nel bin packing vale $FFD(I)\le\frac{11}9z(I)+\frac69$ per ogni istanza, e il bound è stretto ($z(I)$ = numero ottimo di contenitori). Se $z(I)=9$, quanti contenitori può usare al più FFD?
$18$
$11$
$12$
$15$
Spiegazione. $\frac{11}9\cdot9+\frac69\approx11.67$, e il numero di contenitori è intero: al più $11$. $15$ viene dal fattore $\frac{17}{10}$ di First Fit, $18$ da $2z(I)$.
Sei oggetti di peso $2,2,3,2,2,3$ (in quest'ordine) e contenitori di capacità $7$: si confrontano First Fit (FF), che rispetta l'ordine dato, e First Fit Decreasing (FFD), che prima riordina i pesi dal più grande (pareggi per indice); entrambi usano il primo contenitore che può accogliere l'oggetto. Risultato?
FF $2$ contenitori, FFD $3$
FF $3$ contenitori, FFD $2$
$2$ contenitori per entrambi
$3$ contenitori per entrambi
Spiegazione. FF: $2+2+3=7$ e di nuovo $2+2+3=7$. FFD mette insieme i due oggetti da $3$ (residuo $1$), poi tre oggetti da $2$ (residuo $1$), e l'ultimo apre un terzo contenitore. Una garanzia migliore non vuol dire una soluzione migliore su ogni istanza.
In $P\,||\,C_{\max}$ (lavori su $m$ macchine identiche, si minimizza il makespan) una regola greedy assegna ogni lavoro alla macchina meno carica. Quali sono le due scelte indipendenti di un'euristica di questo tipo?
La macchina da chiudere e quella da aprire
Il lower bound e il criterio di arresto
Il numero di macchine e la durata dei lavori
La macchina a cui assegnare e l'ordine dei lavori
Spiegazione. Come nel bin packing, la regola sceglie la macchina; l'ordine in cui si esaminano i lavori è una seconda scelta ($LIST$ con la lista data, $LPT$ per durata non crescente).
Perché, in $P\,||\,C_{\max}$, le euristiche greedy assegnano ogni lavoro alla macchina che in quel momento è la meno carica?
Per usare il minor numero possibile di macchine
Perché così si ottiene sempre il makespan ottimo
Per far crescere i carichi nel modo più uniforme possibile
Per ridurre il tempo di calcolo dell'euristica
Spiegazione. Il makespan è il carico massimo: tenere i carichi bilanciati lo contiene. La regola non garantisce l'ottimo (sull'istanza di riferimento $LPT$ dà $11$ contro $9$).
In $P\,||\,C_{\max}$, $LIST$ assegna i lavori nell'ordine di una lista alla macchina meno carica. Con $m=3$, $t=(5,5,4,4,3,3,3)$ e la lista inversa $(7,6,5,4,3,2,1)$ dà makespan $12$, mentre il lower bound è $9$. Che cosa mostra l'esempio?
Il lower bound $9$ è sbagliato su questa istanza
Un lavoro lungo in fondo alla lista fa salire il makespan
$LIST$ supera la sua garanzia $(2-\frac1m)z(I)$
La lista inversa è sempre la peggiore possibile
Spiegazione. L'ultimo lavoro ($t_1=5$) arriva quando la macchina meno carica ha già carico $7$: makespan $12\le\frac53\cdot9=15$, quindi la garanzia vale. $z(I)=9$ è raggiunto.
In $P\,||\,C_{\max}$, $LPT$ assegna i lavori per durata non crescente alla macchina meno carica, e $LPT(I)\le(\frac43-\frac1{3m})z(I)$. La famiglia di Graham ha $2m+1$ lavori di durata $2m-1,2m-1,2m-2,2m-2,\dots,m+1,m+1,m,m,m$. Con $m=4$, quanto valgono $LPT$ e $z$?
$LPT=15$, $z=12$
$LPT=12$, $z=12$
$LPT=16$, $z=12$
$LPT=15$, $z=14$
Spiegazione. Durate $7,7,6,6,5,5,4,4,4$: dopo otto lavori i carichi sono $(11,11,11,11)$ e l'ultimo $4$ porta a $15=4m-1$; l'ottimo $\{7,5\},\{7,5\},\{6,6\},\{4,4,4\}$ vale $12=3m$. Il rapporto $\frac{15}{12}=\frac43-\frac1{12}$ raggiunge il bound.
Le euristiche costruttive per il TSP si dividono in due famiglie, «accodare» e «inserire». Che cosa le distingue?
Il numero di città di partenza: una sola o tutte
Il test di ammissibilità: presente solo quando si inserisce
Quale città si sceglie: la più vicina o la più lontana
Dove va la città: in fondo a un cammino o dentro un sottogiro
Spiegazione. Accodare estende un cammino dalla sua fine (nearest neighbour); inserire mette la città fra due consecutive di un sottogiro chiuso, dove costa meno. Il test di ammissibilità è banale in entrambe.
Nel TSP ogni giro costruito dal nearest neighbour (accodare alla fine di un cammino) si potrebbe costruire anche con un'euristica di inserimento, ma non viceversa. Quale vantaggio ha l'inserimento?
Non richiede di calcolare le distanze fra le città
Garantisce sempre il giro ottimo sulle istanze metriche
Il sottogiro resta chiuso: l'arco di chiusura si paga da subito
Richiede meno tempo di calcolo del nearest neighbour
Spiegazione. Nel nearest neighbour l'arco di ritorno alla città di partenza è forzato alla fine; nell'inserimento il sottogiro è sempre chiuso.
Partendo dalla città $4$, la regola «vai sempre alla città più vicina non ancora visitata» (a parità, quella di indice minore; alla fine si rientra in $4$) costruisce un giro su quattro città con $d_{12}=2$, $d_{13}=3$, $d_{14}=4$, $d_{23}=3$, $d_{24}=5$, $d_{34}=2$. Quale?
$(4,3,1,2)$, lungo $10$
$(4,3,1,2)$, lungo $12$
$(4,3,2,1)$, lungo $11$
$(4,1,2,3)$, lungo $11$
Spiegazione. Da $4$: $d_{43}=2$, città $3$; da $3$: $d_{31}=d_{32}=3$, pareggio vinto da $1$; da $1$: città $2$; ritorno $d_{24}=5$. Totale $2+3+2+5=12$; il giro $(4,3,2,1)$, lungo $11$, richiederebbe l'altra regola dei pareggi.
Il nearest neighbour per il TSP con $n$ città va dall'ultima città visitata alla più vicina non visitata. Il suo criterio è statico o dinamico, e quanto tempo richiede?
Dinamico; $O(n^2)$
Statico; $O(n\log n)$
Dinamico; $O(n^3)$
Statico; $O(n^2)$
Spiegazione. L'ultima città cambia a ogni passo, quindi le distanze rilevanti cambiano: dinamico. Ogni passo esamina $O(n)$ città, per $n$ passi. $O(n^3)$ è il multi-start da tutte le città.
Sull'istanza di riferimento del TSP a $5$ città (ottimo $18$) il nearest neighbour dà, dalle città $1,\dots,5$, giri lunghi $25,18,18,19,18$. Il multi-start lo esegue da ogni città e tiene il giro più corto. Che cosa mostra l'esempio?
Il multi-start è sempre esatto sulle istanze metriche
La partenza dalla città $1$ è sempre la migliore
Il nearest neighbour trova l'ottimo da ogni città
Conta la partenza, e qui il multi-start trova l'ottimo
Spiegazione. Tre partenze danno il giro ottimo, percorso da città diverse; il multi-start restituisce $18=z(I)$. Su altre istanze non lo trova (sull'istanza a $6$ città resta a $24$ contro $19$).
Nel TSP, farthest insertion inserisce a ogni passo la città più lontana dal sottogiro, nell'arco di costo minimo. Sull'istanza di riferimento, partendo da $1$, sceglie prima la città $5$ ($d_{15}=9$), e poi inserisce $2$, $3$, $4$ a costo $0$, trovando l'ottimo $18$. Che cosa mostra?
I costi di inserimento sono sempre nulli sulle istanze metriche
Si costruisce prima il contorno; le città «di strada» costano poco
La città più lontana va sempre messa per ultima
Farthest insertion trova l'ottimo su ogni istanza
Spiegazione. Le città lontane fissano il contorno del giro; le altre stanno su percorsi già pagati ($d_{12}+d_{25}=d_{15}$, ecc.) e si inseriscono gratis. Sulle istanze metriche i costi sono $\ge0$, non nulli.
Su un'istanza del TSP con $6$ città nel piano (ottimo $19$), dalla città $1$ nearest insertion dà $23$, farthest insertion $19$ e cheapest insertion $20$, mentre il miglior giro del nearest neighbour multi-start è $24$. Che cosa mostra il confronto?
Su istanze più grandi le regole si separano: qui vince farthest insertion
Le euristiche di inserimento danno sempre lo stesso giro
Il nearest neighbour multi-start è la regola migliore
Cheapest insertion è sempre migliore di nearest insertion
Spiegazione. Sull'istanza a $5$ città tutte trovavano l'ottimo; qui farthest insertion lo trova, e il multi-start resta il $26\%$ sopra. Una sola istanza non stabilisce una regola generale.
Nella colorazione dei vertici, l'euristica greedy $GC$ assegna i colori uno alla volta: ogni vertice riceve il più piccolo intero che nessun suo vicino già colorato possiede. Perché il risultato è sempre una colorazione ammissibile?
Perché esamina i vertici per grado non crescente
Perché alla fine corregge i conflitti rimasti
Perché usa sempre al più $\chi(G)$ colori
Le classi di colore sono insiemi stabili per costruzione
Spiegazione. Un vertice non riceve mai il colore di un vicino già colorato, quindi due vertici adiacenti hanno colori diversi. Il numero di colori può superare $\chi(G)$.
Quanto tempo richiede la colorazione greedy $GC$ (vertici nell'ordine di una lista, a ciascuno il colore minimo non usato dai vicini già colorati) su un grafo con $n$ vertici e $|E|$ archi?
$O(n^2\log n)$
$O(n\,|E|)$
$O(n+|E|)$
$O(2^n)$
Spiegazione. Per ogni vertice si guardano i colori dei suoi vicini: in tutto si esamina ogni arco un numero costante di volte.
Sul grafo di Petersen ($\chi=3$) la colorazione greedy (a ogni vertice, nell'ordine della lista, il colore minimo libero) usa $3$ colori con la lista $(1,2,\dots,10)$ e $4$ colori con la lista $(1,2,3,4,5,7,8,6,9,10)$. Che cosa mostra l'esempio?
La colorazione greedy usa sempre $\Delta+1$ colori
L'ordine della lista può cambiare il numero di colori
Il grafo di Petersen ha numero cromatico $4$
La colorazione greedy non è ammissibile con la seconda lista
Spiegazione. Con la seconda lista il vertice $8$ prende il colore $2$ e i vertici $9$ e $10$ vedono tutti e tre i colori fra i vicini. Il $5$-ciclo esterno impone $\chi=3$.
Grafo con archi $\{1,2\},\{1,3\},\{2,3\},\{3,4\},\{4,5\}$. La colorazione greedy esamina i vertici nell'ordine $(5,4,1,2,3)$ e dà a ciascuno il colore minimo non usato dai vicini già colorati. Quali colori hanno i vertici $1,2,3,4,5$?
$(1,2,3,2,1)$: $3$ colori
$(1,2,3,1,2)$: $3$ colori
$(1,2,1,2,1)$: $2$ colori
$(1,2,3,4,1)$: $4$ colori
Spiegazione. $5\to1$, $4\to2$ (vicino $5$), $1\to1$, $2\to2$ (vicino $1$), $3\to3$ (vicini $1,2,4$ con colori $1,2,2$). Il triangolo $1,2,3$ richiede $3$ colori, quindi è ottima.
$DSATUR$ colora a ogni passo il vertice non colorato con grado di saturazione massimo (numero di colori diversi fra i vicini), a parità quello con più vicini non colorati, poi l'indice minimo. Tre vertici hanno (saturazione, vicini non colorati) $=a:(2,1)$, $b:(1,2)$, $c:(2,0)$. Quale sceglie?
$c$
Il vertice di indice minimo fra i tre
$b$
$a$
Spiegazione. Saturazione massima $2$ per $a$ e $c$; il pareggio va a chi ha più vicini non colorati, $a$. $b$ ha più vicini non colorati ma saturazione minore.
La colorazione greedy (vertici nell'ordine di una lista, a ciascuno il colore minimo libero) può usare molti più colori di $\chi(G)$ con una cattiva lista. Esiste sempre una lista con cui usa $\chi(G)$ colori?
No: nessuna lista lo garantisce sui grafi generali
Sì: i vertici classe per classe di una colorazione ottima
Sì: i vertici per grado non crescente
Sì: i vertici in ordine di indice crescente
Spiegazione. Con prima i vertici di $Q_1$, poi quelli di $Q_2$, ecc., ogni vertice di $Q_c$ riceve un colore al più $c$. La difficoltà sta tutta nel trovare quella lista.
$DSATUR$ (a ogni passo il vertice con più colori diversi fra i vicini) non ha una garanzia di prestazione sui grafi generali. Perché è comunque molto usato?
Di solito usa pochi colori più di $\chi(G)$; guida B&B esatti
Perché trova sempre una colorazione ottima in tempo polinomiale
Perché non richiede di conoscere gli archi del grafo
Perché usa sempre esattamente $\Delta(G)+1$ colori
Spiegazione. Sulla maggior parte dei grafi usa pochi colori in più di $\chi(G)$, spesso nessuno; gli algoritmi esatti fanno branching sul vertice scelto dalla sua regola.
$DSATUR$ usa al più $2$ colori su ogni grafo bipartito (Brélaz, 1979). Perché non può avere una garanzia di prestazione costante sui grafi generali, se $P\neq NP$?
Perché sui grafi generali usa sempre $\Delta+1$ colori
Perché sui grafi bipartiti la garanzia fallisce
Perché il suo tempo di calcolo è esponenziale
Perché la colorazione dei vertici non è approssimabile
Spiegazione. Un algoritmo polinomiale con rapporto costante contraddirebbe l'inapprossimabilità della colorazione. $DSATUR$ è polinomiale, $O(n^2)$.
Nella costruzione randomizzata, un candidato si estrae da una lista ristretta $RCL$ di $|RCL|$ elementi, elencati per indice crescente, prendendo la posizione $\lfloor u\cdot|RCL|\rfloor+1$, con $u\in(0,1)$ casuale. Con $RCL=\{2,3,4\}$ e $u=0.7556$, quale città si sceglie?
La città $3$
La città $2$
La città $4$
La città $5$
Spiegazione. $\lfloor0.7556\cdot3\rfloor+1=2+1=3$: il terzo elemento, la città $4$. La città $3$ si otterrebbe dimenticando il $+1$.
Il nearest neighbour randomizzato per il TSP accoda a ogni passo una città estratta a caso da una lista ristretta di candidati, e si ripete più volte tenendo il giro migliore. Perché il seme del generatore NON si reinizializza fra due esecuzioni?
Perché la lista ristretta diventerebbe vuota
Altrimenti ogni esecuzione darebbe lo stesso giro
Perché reinizializzarlo renderebbe i risultati non riproducibili
Perché il generatore andrebbe in overflow
Spiegazione. Lo stesso seme dà la stessa successione di numeri, quindi le stesse scelte. La riproducibilità viene proprio dal seme iniziale fissato.
Per ridurre la miopia di un criterio greedy («quale scelta è la migliore adesso?») si usano il regret e il look-ahead. Quale domanda pone il regret?
Che cosa perdo se rimando questa scelta?
Dove porta questa scelta, completando la soluzione?
Quale scelta è la migliore adesso?
Quale scelta precedente conviene rivedere?
Spiegazione. Un elemento con una sola buona opzione va servito prima che la perda. «Dove porta» è il look-ahead; rivedere scelte precedenti non è ammesso in un'euristica costruttiva.
Regret e look-ahead migliorano un'euristica costruttiva greedy. Che cosa hanno in comune?
Trasformano l'euristica in un algoritmo esatto
Hanno lo stesso costo per passo del criterio greedy
Permettono di tornare indietro e rivedere una scelta
Costano più tempo per passo, e la scelta fatta resta definitiva
Spiegazione. Entrambi valutano di più prima di scegliere, ma conservano la caratteristica essenziale di un'euristica costruttiva: nessuna scelta si rivede.
Nel TSP, il regret di una città $q$ è $reg_q=\Delta^2_q-\Delta^1_q$, differenza fra i due costi di inserimento minimi nel sottogiro. Con costi $(2,2,7)$ per la città $2$, $(4,7,8)$ per la $4$ e $(6,5,6)$ per la $5$, quale città inseriscono cheapest insertion ($CI$, costo minimo) e $REG_2$ (regret massimo)?
$CI$ la città $4$, $REG_2$ la città $2$
Entrambe la città $2$
$CI$ la città $2$, $REG_2$ la città $4$
$CI$ la città $2$, $REG_2$ la città $5$
Spiegazione. Costi minimi $2,4,5$: $CI$ sceglie la città $2$. Regret $0,3,1$: $REG_2$ sceglie la $4$, che ha una sola buona posizione, mentre la $2$ ne ha due e può aspettare.
L'inserimento $REG_2$ per il TSP inserisce la città con regret massimo $reg_q=\Delta^2_q-\Delta^1_q$, a parità quella con costo minimo $\Delta^1_q$, poi l'indice minimo. Finché tutti i regret sono $0$, a quale euristica equivale?
Al nearest neighbour
A cheapest insertion
A nearest insertion
A farthest insertion
Spiegazione. Con tutti i regret nulli decide il pareggio: il costo di inserimento minimo, cioè la regola di cheapest insertion.
Il metodo pilota con nearest neighbour come pilota ($PILOT$-$NN$) prova ogni città successiva, completa il giro con $NN$ e sceglie la migliore. Sull'istanza di riferimento del TSP (ottimo $18$), dalla città $1$ va prima nella città più lontana e trova $22$, contro $25$ di $NN$. Che cosa mostra?
Il look-ahead sceglie diversamente dal greedy, ma vale quanto il pilota
Il metodo pilota trova sempre il giro ottimo dell'istanza
Il metodo pilota può essere peggiore del suo stesso pilota
Andare nella città più lontana è sempre la scelta giusta
Spiegazione. $22<25$ ma $22>18$: il look-ahead migliora $NN$ senza garantire l'ottimo. Il metodo pilota non è mai peggiore del pilota dalla stessa città.
Il metodo pilota per il TSP, con nearest neighbour ($O(n^2)$) come pilota, a ogni passo completa il giro con il pilota una volta per ogni città candidata. Quanto tempo richiede?
$O(n^3)$
$O(2^n)$
$O(n^2)$
$O(n^4)$
Spiegazione. $n$ passi, fino a $n$ candidati per passo, ciascuno con un completamento $O(n^2)$: $O(n^4)$. $O(n^3)$ è il multi-start del nearest neighbour.
Sull'istanza di riferimento del TSP le euristiche costruttive trovano un giro lungo $18$, che è ottimo, mentre il miglior bound duale disponibile è $17$ (gap $5.9\%$). Che cosa si può dire?
Il giro non è ottimo, perché il gap è positivo
Il gap dimostra che il giro dista il $5.9\%$ dall'ottimo
Il giro è ottimo, ma il bound $17$ non può dimostrarlo
L'euristica sa di aver trovato l'ottimo
Spiegazione. Il gap è solo un limite superiore all'errore: qui l'errore è $0$, ma servirebbe un bound duale $18$ per dimostrarlo. L'euristica non sa in quale situazione si trova.
In $P\,||\,C_{\max}$ con $m=3$ e $t=(5,5,4,4,3,3,3)$, $LPT$ (lavori per durata non crescente alla macchina meno carica) arriva all'ultimo lavoro con carichi $(8,8,8)$ e chiude con makespan $11$, mentre l'ottimo è $9$. Che cosa illustra?
L'ultimo lavoro andava lasciato senza macchina
Le scelte precedenti sono definitive: non si torna indietro
$LPT$ viola la propria garanzia di prestazione
Il lower bound $9$ non è raggiungibile su questa istanza
Spiegazione. Il makespan $11$ è fissato da scelte già fatte; una soluzione migliore sembra vicina, ma un'euristica costruttiva non ha un meccanismo per tornare indietro. $\frac{11}9$ è esattamente la garanzia di $LPT$ per $m=3$.
Un algoritmo greedy costruisce una soluzione scegliendo ogni volta, fra gli elementi candidati, il migliore secondo un criterio di selezione. Quale proprietà ha ogni sua decisione?
È presa una volta per tutte: una scelta fatta non viene mai rivista
Viene rivista alla fine con una ricerca locale incorporata
Viene annullata se la soluzione parziale diventa inammissibile
È presa a caso fra gli elementi di pari valore e poi ottimizzata
Spiegazione. Il greedy aggiunge un elemento alla volta e non torna indietro: per questo è veloce, e per questo una scelta miope iniziale può pesare su tutta la soluzione.
Nello schema greedy, che cosa succede a un elemento candidato che, aggiunto alla soluzione parziale, la renderebbe inammissibile (per esempio un oggetto che non entra nello zaino)?
L'algoritmo si ferma e restituisce la soluzione parziale
Viene aggiunto comunque e un altro elemento viene tolto
Viene rimesso in fondo alla lista e riesaminato più tardi
Viene scartato e l'algoritmo passa al candidato successivo
Spiegazione. Nel greedy per lo zaino con ordine $\rho$, un oggetto che non entra si salta e si continua: oggetti successivi più leggeri possono ancora entrare.
Zaino 0-1 con capacità $c=10$ e oggetti $(p_j,w_j)$: $(10,5)$, $(6,4)$, $(5,3)$, $(3,2)$. Il greedy esamina gli oggetti in un ordine e prende ogni oggetto che entra; a parità vince l'indice minore. Quanto vale il greedy per profitto non crescente ($GR_p$)?
$21$
$18$
$16$
$14$
Spiegazione. $GR_p$ prende gli oggetti $1$ e $2$ (peso $9$) e poi nessun altro entra: $16$. Per efficienza ($GR$) si prendono $1,3,4$: $18$; per peso non decrescente ($GR_w$) $4,3,2$: $14$.
Bin packing con capacità $c=10$ e oggetti di peso $2,3,4,5,6$ in quest'ordine. First Fit (FF) mette ogni oggetto, nell'ordine dato, nel primo contenitore in cui entra; First Fit Decreasing (FFD) fa lo stesso dopo aver ordinato i pesi in modo non crescente. Quanti contenitori usano?
FF $3$, FFD $3$
FF $3$, FFD $2$
FF $2$, FFD $3$
FF $2$, FFD $2$
Spiegazione. FF: $2,3,4$ nel primo ($9$), $5$ nel secondo, $6$ nel terzo. FFD: $6,4$ nel primo, $5,3,2$ nel secondo. Il bound $\lceil 20/10\rceil=2$ dimostra che FFD è ottimo qui.
Scheduling $P\,||\,C_{\max}$ con $m=2$ macchine e durate $t=(3,3,2,2,2)$. $LPT$ ordina i lavori per durata non crescente e assegna ciascuno alla macchina meno carica (a parità, quella di indice minore). Quanto valgono il makespan di $LPT$ e quello ottimo?
$7$ e $6$: il rapporto $\frac76$ raggiunge la garanzia $\frac43-\frac1{3m}$
$6$ e $6$: $LPT$ è ottimo su questa istanza
$7$ e $7$: nessuno schedule fa meglio di $7$
$8$ e $6$: il rapporto supera la garanzia
Spiegazione. $LPT$: $3\to M_1$, $3\to M_2$, $2\to M_1$, $2\to M_2$, $2\to M_1$: carichi $7$ e $5$. Lo schedule $\{3,3\},\{2,2,2\}$ ha makespan $6$. Con $m=2$ la garanzia è $\frac43-\frac16=\frac76$, raggiunta esattamente.
Nel TSP, il nearest neighbour multi-start esegue la regola del nearest neighbour ($NN$: dalla città corrente alla più vicina non visitata) da ogni città di partenza e restituisce il giro più corto. Quale affermazione è corretta?
Trova sempre il giro ottimo, perché prova tutte le partenze
Dà sempre lo stesso giro di $NN$, perché i giri sono ciclici
È peggiore di $NN$ su alcune istanze, perché sceglie a caso la partenza
Non è mai peggiore di $NN$ da una città fissata, ma richiede $n$ esecuzioni
Spiegazione. Il giro di $NN$ dalla città fissata è uno degli $n$ giri provati, quindi il migliore non è più lungo; ma le partenze sono solo $n$ e l'ottimo non è garantito.
In un'euristica di inserimento per il TSP simmetrico, la città $k$ si inserisce nel lato $(i,j)$ del sottogiro con costo minimo $\Delta(i,k,j)=d_{ik}+d_{kj}-d_{ij}$. Sottogiro $(1,2,3)$ con $d_{12}=4$, $d_{23}=5$, $d_{31}=6$; città $4$ con $d_{14}=3$, $d_{24}=2$, $d_{34}=7$. Quanto è lungo il sottogiro dopo l'inserimento?
$20$
$15$
$16$
$19$
Spiegazione. I costi sono $\Delta(1,4,2)=3+2-4=1$, $\Delta(2,4,3)=2+7-5=4$, $\Delta(3,4,1)=7+3-6=4$: si inserisce fra $1$ e $2$, e la lunghezza passa da $15$ a $16$.
In $DSATUR$ per la colorazione dei vertici, il grado di saturazione di un vertice non colorato è il numero di colori diversi già usati dai suoi vicini. Un vertice ha quattro vicini: due di colore $1$, uno di colore $2$ e uno non colorato. Qual è il suo grado di saturazione?
$4$
$2$
$1$
$3$
Spiegazione. Contano i colori distinti fra i vicini colorati: $\{1,2\}$, quindi $2$. Il grado del vertice è $4$, i vicini colorati sono $3$.
La colorazione greedy $GC$ esamina i vertici nell'ordine di una lista e dà a ciascuno il colore più piccolo (intero $1,2,\dots$) non usato dai vicini già colorati. Sul cammino $1-2-3-4$ (lati $\{1,2\},\{2,3\},\{3,4\}$) con la lista $(1,4,2,3)$, quanti colori usa?
$3$
$2$
$4$
$1$
Spiegazione. $1\to1$, $4\to1$, $2\to2$ (vicino $1$ ha colore $1$), $3\to3$ (vicini $2$ e $4$ hanno colori $2$ e $1$). Il cammino ha $\chi=2$: l'ordine della lista conta.
In una costruzione randomizzata per un criterio di minimo, la lista ristretta dei candidati è $RCL=\{q: g(q)\le g^{\min}+\alpha(g^{\max}-g^{\min})\}$. I candidati hanno valori $g=(10,12,15,18,30)$ e $\alpha=0{,}25$. Quanti candidati contiene la $RCL$?
$2$
$1$
$4$
$3$
Spiegazione. La soglia è $10+0{,}25\cdot 20=15$, quindi entrano i valori $10$, $12$ e $15$. Il candidato si estrae poi a caso dalla $RCL$.
Nella costruzione randomizzata con lista ristretta dei candidati $RCL=\{q: g(q)\le g^{\min}+\alpha(g^{\max}-g^{\min})\}$, che cosa si ottiene con $\alpha=0$ e con $\alpha=1$?
Con $\alpha=0$ la $RCL$ è vuota; con $\alpha=1$ contiene solo il migliore
Con $\alpha=0$ una scelta casuale; con $\alpha=1$ il greedy
Con $\alpha=0$ il greedy (con pareggi casuali); con $\alpha=1$ una scelta del tutto casuale
In entrambi i casi il greedy, perché la $RCL$ contiene sempre il migliore
Spiegazione. Con $\alpha=0$ restano solo i candidati di valore $g^{\min}$; con $\alpha=1$ la soglia è $g^{\max}$ e tutti i candidati sono ammessi. $\alpha$ bilancia qualità e varietà delle soluzioni.
Nell'inserimento con rimpianto $REG_2$ per il TSP, $\Delta^1_q\le\Delta^2_q$ sono i due costi di inserimento più piccoli della città $q$ nei lati del sottogiro, e il rimpianto è $reg_q=\Delta^2_q-\Delta^1_q$. La città $a$ ha $\Delta^1=3$, $\Delta^2=10$; la città $b$ ha $\Delta^1=2$, $\Delta^2=4$. Quale città inserisce $REG_2$?
La città $b$, con rimpianto $2$
La città $a$, con rimpianto $7$
La città $a$, con costo di inserimento $3$
La città $b$, con costo di inserimento $2$
Spiegazione. $REG_2$ inserisce la città con il rimpianto massimo: $reg_a=7>reg_b=2$. Rimandare $a$ rischia di farle perdere l'unico lato conveniente; l'inserimento economico sceglierebbe invece $b$.
Il metodo pilota trasforma un'euristica costruttiva $\mathscr{H}$ (il pilota): a ogni passo prova ogni candidato, completa la soluzione parziale con $\mathscr{H}$ e sceglie il candidato con il completamento migliore. Quale affermazione è corretta?
Non è mai peggiore del pilota, ma esegue il pilota una volta per candidato a ogni passo
Trova sempre la soluzione ottima, perché prova tutti i candidati
Può essere peggiore del pilota, perché cambia la prima scelta
Costa come il pilota, perché lo esegue una sola volta
Spiegazione. Al primo passo il candidato scelto dal pilota è fra quelli provati, e il suo completamento è la soluzione del pilota: il metodo trova almeno altrettanto, a un costo molto maggiore.
Un'euristica costruttiva restituisce una soluzione ammissibile. Che cosa serve, oltre al suo valore, per dire quanto la soluzione è lontana dall'ottimo?
Una seconda esecuzione della stessa euristica
L'ordine in cui sono stati scelti gli elementi
Niente: il valore di un'euristica costruttiva è sempre vicino all'ottimo
Un bound duale, per calcolare il gap
Spiegazione. Il valore è un bound primale e dà un solo lato dell'intervallo che contiene l'ottimo; con un bound duale (per esempio un rilassamento) si ottiene il gap.
Le euristiche costruttive si fermano appena la soluzione è completa, e ogni scelta fatta è definitiva. Come si usano di solito in un algoritmo euristico più ampio?
Non si combinano mai con altri metodi
Come algoritmo finale, dopo una ricerca locale
Come punto di partenza di una ricerca locale o di una metaeuristica, che migliorano la soluzione completa
Come bound duale per il branch-and-bound
Spiegazione. Sono veloci ma non rivedono le scelte: una ricerca locale parte dalla loro soluzione e corregge le decisioni sbagliate con mosse nell'intorno.
Un'euristica costruttiva parte dalla soluzione parziale vuota e la estende con un elemento alla volta. Quale caratteristica la distingue da una ricerca locale?
Parte sempre da una soluzione ammissibile completa
Ogni scelta è definitiva: un elemento aggiunto non viene più tolto
Garantisce una soluzione ottima
Esamina tutti i vicini della soluzione corrente
Spiegazione. La ricerca locale modifica una soluzione completa; l'euristica costruttiva costruisce la soluzione e non torna indietro. Anche look-ahead e regret mantengono le scelte definitive.
Un algoritmo greedy è un'euristica costruttiva che a ogni passo aggiunge l'elemento migliore secondo un criterio. Per lo zaino 0/1, quale criterio greedy porta al bound di Dantzig quando si ammette una frazione dell'oggetto critico?
Efficienza $p_j/w_j$ non crescente
Profitto $p_j$ non decrescente
Peso $w_j$ non crescente
Indice $j$ crescente
Spiegazione. Il greedy per efficienza si ferma all'oggetto critico; completare con la frazione $\mathit{rc}/w_s$ dà il rilassamento lineare, e il suo arrotondamento è il bound di Dantzig.
Nelle euristiche, $\mathscr{A}(I)$ è il valore della soluzione dell'euristica $\mathscr{A}$ sull'istanza $I$ e $z(I)$ il valore ottimo. Per un problema di minimo come il bin packing, quale relazione vale sempre?
$\mathscr{A}(I)\le z(I)$
$\mathscr{A}(I)=z(I)$
$\mathscr{A}(I)\ge 2z(I)$
$\mathscr{A}(I)\ge z(I)$
Spiegazione. La soluzione dell'euristica è ammissibile, quindi in un problema di minimo non può valere meno dell'ottimo: è un bound primale (upper bound).
Bin packing con $c=10$ e pesi, nell'ordine di input, $w=(2,2,2,8,8,8)$. Quanti contenitori usa First Fit (ogni oggetto, in ordine, nel primo contenitore in cui entra) e quanti First Fit Decreasing (prima ordinati per peso non crescente)?
FF: $6$, FFD: $3$
FF: $4$, FFD: $4$
FF: $4$, FFD: $3$
FF: $3$, FFD: $3$
Spiegazione. FF mette i tre $2$ nel primo contenitore (carico $6$) e poi ogni $8$ in un contenitore nuovo: $4$. FFD apre tre contenitori con gli $8$ e mette un $2$ in ciascuno: $3$, che è ottimo ($\lceil30/10\rceil=3$).
Nel bin packing con $c=10$ tre contenitori aperti hanno carichi $(4,7,6)$ e arriva un oggetto di peso $3$. In quale contenitore lo mettono First Fit (il primo in cui entra), Best Fit (quello con capacità residua minima fra quelli in cui entra) e Worst Fit (residua massima)?
FF: $1$, BF: $1$, WF: $2$
FF: $1$, BF: $2$, WF: $1$
FF: $2$, BF: $2$, WF: $3$
FF: $1$, BF: $3$, WF: $1$
Spiegazione. Le capacità residue sono $6,3,4$ e l'oggetto entra ovunque. FF prende il contenitore $1$; BF quello con residua $3$ (il $2$), che riempie esattamente; WF quello con residua $6$ (il $1$).
Per $P\,||\,C_{\max}$ (lavori di durata $t_j$ su $m$ macchine identiche, si minimizza il makespan) le euristiche costruttive assegnano un lavoro alla volta. Perché il test di ammissibilità è banale e tutto sta nell'ordine dei lavori?
Ogni assegnamento dei lavori alle macchine è ammissibile; la regola «macchina meno carica» dipende dall'ordine in cui arrivano i lavori
Perché il makespan non dipende dall'assegnamento
Perché ogni macchina ha una capacità da rispettare
Perché i lavori si possono dividere fra le macchine
Spiegazione. Non ci sono capacità: si sceglie solo dove mettere il lavoro. Con lo stesso criterio greedy, liste diverse danno makespan diversi.
$P\,||\,C_{\max}$ con $m=2$ macchine e lavori di durata $t=(3,3,2,2,4)$. $LIST$ assegna i lavori nell'ordine della lista alla macchina meno carica (a parità, indice minore); $LPT$ fa lo stesso dopo averli ordinati per durata non crescente. Quanto valgono $LIST(I)$ con la lista $(1,2,3,4,5)$ e $LPT(I)$?
$LIST(I)=8$, $LPT(I)=7$
$LIST(I)=9$, $LPT(I)=7$
$LIST(I)=7$, $LPT(I)=8$
$LIST(I)=9$, $LPT(I)=8$
Spiegazione. $LIST$: carichi $(3,3)\to(5,5)\to(9,5)$, makespan $9$: il lavoro lungo arriva per ultimo. $LPT$: $4,3,3,2,2$ dà $(4,0)\to(4,3)\to(4,6)\to(6,6)\to(8,6)$. L'ottimo è $7$ ($\{4,3\}$ e $\{3,2,2\}$).
Per $P\,||\,C_{\max}$ Graham (1966) ha dimostrato $LIST(I)\le(2-\frac1m)z(I)$ per ogni lista. Su un'istanza con $m=2$ macchine $LIST$ trova makespan $9$. Che cosa si deduce sul valore ottimo $z(I)$?
$z(I)\ge9$
$4.5\le z(I)\le9$
$6\le z(I)\le9$
$z(I)=6$
Spiegazione. La soluzione di $LIST$ è ammissibile: $z(I)\le9$. La garanzia dà $9\le\frac32z(I)$, cioè $z(I)\ge6$. Dividere per $2$ invece che per $2-\frac12$ dà il falso $4.5$.
Nell'euristica di inserimento per il TSP la soluzione parziale è il sottogiro $(1,2,3)$ con $d_{12}=4$, $d_{23}=5$, $d_{31}=6$; la città $4$ ha $d_{14}=3$, $d_{24}=2$, $d_{34}=6$. Inserendo $4$ fra due città consecutive $i,j$ l'aumento è $d_{i4}+d_{4j}-d_{ij}$. Dove conviene inserirla e con quale aumento?
Fra $2$ e $3$, aumento $3$
Fra $1$ e $2$, aumento $1$
Fra $3$ e $1$, aumento $3$
Fra $1$ e $2$, aumento $5$
Spiegazione. Aumenti: $3+2-4=1$ fra $1$ e $2$; $2+6-5=3$ fra $2$ e $3$; $6+3-6=3$ fra $3$ e $1$. Dimenticare di togliere $d_{ij}$ dà $5$.
TSP con $5$ città e distanze $d_{12}=5$, $d_{13}=2$, $d_{14}=2$, $d_{15}=9$, $d_{23}=4$, $d_{24}=3$, $d_{25}=4$, $d_{34}=4$, $d_{35}=7$, $d_{45}=7$ (valore ottimo $18$). Nearest neighbour parte da una città e va sempre alla città non visitata più vicina (pareggi: indice minore). Che lunghezza ha il giro trovato partendo dalla città $5$?
$18$
$22$
$25$
$20$
Spiegazione. $5\to2$ ($4$), $2\to4$ ($3$), $4\to1$ ($2$), $1\to3$ ($2$), chiusura $3\to5$ ($7$): $18$, l'ottimo. Dalla città $1$ invece il giro $(1,3,2,4,5)$ vale $25$: il risultato dipende dalla partenza.
Su un'istanza del TSP con $6$ città il nearest neighbour, da ogni città di partenza, trova al meglio un giro di lunghezza $24$ (ottimo $19$), e tutti i suoi giri contengono il lato più lungo dell'istanza, fra due città agli estremi opposti. Quale debolezza mostra?
Il nearest neighbour richiede tempo esponenziale
Il nearest neighbour non trova mai un giro ammissibile
Il nearest neighbour ignora la città di partenza
Le ultime città rimaste sono lontane fra loro, e il lato di chiusura non viene mai scelto per la sua lunghezza
Spiegazione. Il criterio guarda solo all'ultima città: alla fine restano città «scomode», e l'arco verso la partenza è forzato. Le euristiche di inserimento evitano in parte il problema.
La colorazione greedy $GC$ colora i vertici nell'ordine di una lista $\lambda$, dando a ogni vertice il colore più piccolo non usato dai vicini già colorati. Sul cammino $1-2-3-4$ (lati $\{1,2\},\{2,3\},\{3,4\}$) con la lista $\lambda=(1,4,2,3)$, quanti colori usa?
$4$
$1$
$3$
$2$
Spiegazione. $1\to1$, $4\to1$, $2\to2$ (vicino di $1$), $3$: i vicini $2$ e $4$ hanno colori $2$ e $1$, quindi $3$. Con la lista $(1,2,3,4)$ bastano $2$ colori: l'ordine conta.
Il grafo corona $G_k$ ha vertici $u_1,\dots,u_k,v_1,\dots,v_k$ e lati $\{u_i,v_j\}$ per $i\ne j$: è bipartito, quindi $\chi(G_k)=2$. Con la lista $(u_1,v_1,u_2,v_2,\dots)$ la colorazione greedy usa $k$ colori. Per $k=5$, che cosa mostra questo esempio?
Che $GC$ è sempre ottima sui grafi bipartiti
Una cattiva lista può far usare a $GC$ $n/2=5$ colori su un grafo $2$-colorabile: non c'è garanzia di prestazione
Che $\chi(G_5)=5$
Che $GC$ usa sempre $\Delta(G)+1$ colori
Spiegazione. $u_i$ e $v_i$ non sono adiacenti e ricevono lo stesso colore $i$: ogni coppia nuova vede tutti i colori precedenti. $DSATUR$ invece colora i grafi bipartiti con $2$ colori.
$DSATUR$ è la colorazione greedy che sceglie a ogni passo il vertice non colorato con più colori diversi fra i vicini. Che cosa vale per $DSATUR$ sui grafi bipartiti e sui grafi generali?
Sui bipartiti usa al più $2$ colori; sui grafi generali non ha garanzia di prestazione
Usa sempre $\omega(G)$ colori
Sui bipartiti può usare $n/2$ colori; sui generali è una $2$-approssimazione
È ottimo su tutti i grafi
Spiegazione. Brélaz (1979) mostrò che $DSATUR$ è esatto sui bipartiti; poiché il VCP non è approssimabile, nessuna euristica polinomiale ha una garanzia costante sui grafi generali.
Per ridurre la miopia del greedy si usano il regret e il look-ahead. Che cosa fa il look-ahead (metodo pilota)?
Serve prima l'elemento che perderebbe di più se rimandato
Annulla le scelte già fatte se peggiorano la soluzione
Sceglie un candidato a caso fra i migliori
Valuta ogni candidato completando la soluzione parziale con un'euristica veloce, e sceglie il candidato con il completamento migliore
Spiegazione. Il regret chiede che cosa si perde rimandando; il look-ahead dove porta la scelta. Entrambi costano di più per passo e mantengono le scelte definitive.
First Fit Decreasing per il bin packing ordina gli oggetti per peso non crescente prima di riempire i contenitori con First Fit. Quale ipotesi sull'istanza richiede, che First Fit non richiede?
Che i pesi siano tutti diversi
Che la capacità sia pari
Che tutti gli oggetti siano noti in anticipo (caso offline); First Fit funziona anche quando arrivano uno alla volta
Che ogni oggetto pesi più di metà della capacità
Spiegazione. Per ordinare serve conoscere tutta l'istanza. Quando è nota, conviene sistemare prima gli oggetti grandi: due oggetti più grandi di $c/2$ non stanno mai insieme.
Con $m=4$ macchine identiche, quale fattore garantisce il risultato di Graham per $LIST$ (qualunque lista), e quale quello per $LPT$?
$\frac74$ per tutti e due
$\frac54$ per $LIST$, $\frac74$ per $LPT$
$\frac74$ per $LIST$, $\frac54$ per $LPT$
$2$ per $LIST$, $\frac43$ per $LPT$
Spiegazione. $2-\frac1m=\frac74$ e $\frac43-\frac1{3m}=\frac43-\frac1{12}=\frac54$. I fattori $2$ e $\frac43$ sono i limiti per $m$ che cresce; ordinare i lavori migliora la garanzia.
Un grafo $G$ ha grado massimo $\Delta(G)=4$. Quanti colori usa al più la colorazione greedy $GC$, qualunque sia la lista dei vertici?
$2\Delta(G)$
$5$
$4$
$\chi(G)+1$
Spiegazione. $GC(I)\le\Delta(G)+1=5$ per ogni lista: quando un vertice si colora, al più $4$ vicini hanno già un colore. $\chi(G)+1$ non è garantito (grafo a corona).
Sul grafo a corona $G_k$ ($n=2k$ vertici, $\chi(G_k)=2$) la colorazione greedy, con una lista opportuna, usa $k=\frac n2$ colori. Che cosa mostra questo risultato?
Nessun bound $GC\le c\,\chi(G)$, $c$ costante, vale per ogni lista
$GC$ è ottima sui grafi bipartiti, con ogni lista
Anche $DSATUR$ usa $k$ colori sul grafo $G_k$
Il bound $\Delta(G)+1$ non vale sui grafi bipartiti
Spiegazione. Il rapporto $GC/\chi=\frac k2$ cresce con $k$: nessuna costante lo limita. Il bound $\Delta+1=k$ vale ed è raggiunto; $DSATUR$ colora i grafi bipartiti con $2$ colori.
La garanzia $LPT(I)\le(\frac43-\frac1{3m})z(I)$ è migliore di quella di $LIST$. Quale caratteristica di $LPT$ usa la dimostrazione?
Le macchine hanno velocità diverse
Le macchine sono almeno $3$
I tempi dei lavori sono tutti distinti
I lavori sono ordinati per tempo non crescente
Spiegazione. $LPT$ è $LIST$ con i lavori ordinati per tempo non crescente: l'ultimo lavoro assegnato è il più corto, e da qui viene il fattore migliore. Le macchine sono identiche e $m$ è qualsiasi.
Perché il bound $GC(I)\le\Delta(G)+1$ vale per ogni lista $\lambda$ dei vertici?
Il grafo da colorare è sempre bipartito
$GC$ ricolora i vertici già colorati quando serve
Al più $\Delta(G)$ vicini di un vertice hanno già un colore
$GC$ colora sempre i vertici per grado decrescente
Spiegazione. Il vertice prende il più piccolo colore non usato dai vicini già colorati, che sono al più $\Delta(G)$: uno fra i colori $1,\dots,\Delta(G)+1$ è libero. Non servono ordini o proprietà del grafo.
Per quale problema l'algoritmo greedy per efficienza $p_j/w_j$ non crescente dà sempre una soluzione ottima?
Lo zaino limitato, con più copie per oggetto
Lo zaino continuo, con oggetti frazionabili
Lo zaino 0/1 con profitti e pesi interi
Lo zaino 0/1 con capacità $c\ge\frac12\sum_jw_j$
Spiegazione. Il greedy per efficienza risolve il rilassamento continuo (Dantzig), dove l'oggetto critico entra in parte. Sullo zaino 0/1 e sulle sue varianti intere non garantisce l'ottimo.
Quale ingrediente serve a un algoritmo greedy costruttivo?
Una regola di scelta dell'elemento, mai rivista
Una soluzione ammissibile completa di partenza
Un intorno delle soluzioni ammissibili
Un bound duale del valore ottimo
Spiegazione. Il greedy parte dalla soluzione vuota e aggiunge un elemento alla volta scelto con una regola, senza tornare indietro. La soluzione di partenza e l'intorno servono alla ricerca locale.
Nearest neighbour dà sempre un giro ammissibile su un grafo completo. Perché può fallire su un grafo non completo?
Sui grafi non completi le distanze sono asimmetriche
Serve la disuguaglianza triangolare
Il numero di città deve essere pari
L'ultima città può non avere un lato verso la partenza
Spiegazione. Su un grafo completo ogni città non visitata è raggiungibile e il giro si chiude sempre. Su un grafo non completo il cammino può bloccarsi o non chiudersi verso la città di partenza.
First Fit Decreasing ordina gli oggetti per peso prima di riempire i contenitori. In quale situazione si può usare solo First Fit nell'ordine di arrivo?
Quando l'istanza ha molti oggetti
Quando gli oggetti arrivano uno alla volta (online)
Quando gli oggetti hanno tutti lo stesso peso
Quando i contenitori hanno capacità diverse
Spiegazione. L'ordinamento richiede di conoscere tutta l'istanza in anticipo. Con pesi uguali l'ordine non conta, e capacità diverse o istanze grandi non impediscono di ordinare.
$P\,||\,C_{\max}$ con $m=2$ macchine: $LPT$ trova makespan $14$. Che cosa si deduce dalla garanzia $LPT(I)\le(\frac43-\frac1{3m})z(I)$?
$z(I)\le 12$
$z(I)\ge 12$
$z(I)\ge 10{,}5$
$z(I)\ge 7$
Spiegazione. Con $m=2$ il fattore è $\frac43-\frac16=\frac76$: $z(I)\ge14\cdot\frac67=12$. $10{,}5$ usa il fattore $\frac43$, $7$ il fattore $2$; la garanzia dà un bound inferiore su $z(I)$.
$P\,||\,C_{\max}$ con $m=2$ e tempi $t=(1,1,2)$ nell'ordine della lista: $LIST$ assegna ogni lavoro alla macchina meno carica. Quanto vale $LIST(I)/z(I)$?
$\frac32=2-\frac1m$
$\frac43$, meno della garanzia
$2$, più della garanzia
$1$: $LIST$ è ottimo
Spiegazione. I due lavori corti vanno uno per macchina, poi il lavoro lungo dà makespan $3$; l'ottimo è $2$ ($\{1,1\}$ e $\{2\}$). Il rapporto $\frac32=2-\frac12$: la garanzia è raggiunta.
Sul grafo completo $K_6$ quanti colori usa la colorazione greedy $GC$, e come si confronta con il bound $\Delta(G)+1$?
$5$: un colore meno del bound
$6$: uno più del bound
$2$: il grafo è bipartito
$6$: il bound è raggiunto
Spiegazione. In $K_6$ tutti i vertici sono adiacenti: servono $6$ colori, e $\Delta(K_6)+1=5+1=6$. Il bound $\Delta+1$ non si può migliorare in generale.
Quanti colori usa $DSATUR$ su un grafo bipartito con almeno uno spigolo?
Dipende dalla lista iniziale
Esattamente $\frac n2$
Esattamente $2$
Al più $\Delta(G)+1$, non meno
Spiegazione. $DSATUR$ è esatto sui grafi bipartiti (Brélaz, 1979): usa $2$ colori, mentre il greedy con una lista cattiva può usarne $\frac n2$ (grafo a corona).
Per ogni grafo $G$ esiste una lista dei vertici con cui la colorazione greedy usa $\chi(G)$ colori. Perché?
Perché il grafo ha sempre $\chi(G)=2$
Basta seguire le classi di una colorazione ottima
Perché $GC$ usa sempre $\Delta(G)+1$ colori
Perché ogni lista dà lo stesso risultato
Spiegazione. Con i vertici in ordine di classe di una colorazione ottima, $GC$ non usa mai un colore oltre $\chi(G)$. Trovare quella lista è però difficile quanto colorare il grafo.
Zaino 0/1 con $c=100$, oggetto $1$ con $p_1=2$, $w_1=1$ e oggetto $2$ con $p_2=w_2=100$. Il greedy per efficienza prende l'oggetto $1$ e poi l'oggetto $2$ non entra. Che cosa mostra l'istanza?
Il greedy per efficienza non ha garanzia costante
Il greedy è ottimo quando i pesi sono diversi
Il rilassamento lineare vale $2$
Il greedy per profitto è sempre peggiore
Spiegazione. Il greedy vale $2$, l'ottimo $100$: allungando l'istanza ($p_2=w_2=c=M$) il rapporto cresce senza limite. Il rilassamento vale $2+\frac{99}{100}\cdot100=101$.
Per quali liste e quali macchine vale la garanzia di Graham $LIST(I)\le(2-\frac1m)z(I)$?
Solo per liste ordinate per tempo
Solo con due macchine
Anche con macchine di velocità diverse
Per ogni lista, con macchine identiche
Spiegazione. La dimostrazione vale per qualunque ordine dei lavori, su $m$ macchine identiche; ordinare per tempo non crescente ($LPT$) dà la garanzia migliore $\frac43-\frac1{3m}$.
$DSATUR$ colora per primo il vertice di saturazione massima. Che cos'è la saturazione di un vertice?
Il numero dei suoi vicini non colorati
Il più piccolo colore libero per lui
I colori diversi fra i suoi vicini
Il numero dei suoi vicini
Spiegazione. La saturazione conta i colori distinti già usati dai vicini; a parità si sceglie il vertice di grado massimo. Il numero di vicini è il grado.
Il nearest neighbour multi-start ripete il metodo da ogni città di partenza e tiene il giro migliore. Su che cosa si basa?
Serve per calcolare un bound duale
Il giro dipende dalla città di partenza
Il nearest neighbour è casuale
Ogni partenza dà lo stesso giro
Spiegazione. Il metodo è deterministico ma il giro cambia con la città iniziale: provarle tutte costa $n$ volte di più e non peggiora mai il risultato della partenza dalla città $1$.
Nelle euristiche di inserimento per il TSP, su che cosa si inserisce ogni nuova città?
Su un ciclo sulle città già inserite
Su un cammino che parte dalla città $1$
Su un albero ricoprente delle città
Su un accoppiamento delle città
Spiegazione. Si parte da un piccolo sottogiro e ogni città si inserisce fra due città consecutive del ciclo corrente, al costo $d_{ik}+d_{kj}-d_{ij}$; il nearest neighbour invece accoda a un cammino.
L'inserimento con regret sceglie la città con il regret massimo. Come si definisce il regret di una città $q$?
Il costo di inserimento più piccolo
La distanza dalla città più vicina
La somma dei costi di inserimento
Il secondo costo di inserimento meno il primo
Spiegazione. $reg_q=\Delta^2_q-\Delta^1_q$: quanto si perde se il posto migliore per $q$ viene occupato. Si inserisce prima la città che perderebbe di più aspettando.
Perché si rende casuale un'euristica costruttiva, scegliendo a caso fra i candidati migliori?
Per ridurre il tempo di una costruzione
Per avere un bound duale
Per avere soluzioni diverse
Per renderla esatta
Spiegazione. Una costruzione deterministica dà sempre la stessa soluzione; con la scelta casuale fra i migliori candidati ogni esecuzione dà una soluzione diversa, e si tiene la migliore (è la base di GRASP).
Una ricerca locale $LS$ per un problema di minimo con obiettivo $f$ a valori interi e valore ottimo $z(I)$ parte da $x^0$ e si sposta sempre su un vicino strettamente migliore. Quale affermazione è corretta?
Può non fermarsi mai, se l'intorno usato non è esatto
Si ferma in un ottimo globale dopo al più $f(x^0)-z(I)$ mosse
Si ferma in un ottimo locale dopo al più $f(x^0)-z(I)$ mosse
Si ferma in un ottimo locale dopo esattamente $f(x^0)-z(I)$ mosse
Spiegazione. Ogni mossa migliora $f$ di almeno $1$ e $f$ non scende sotto $z(I)$; quando nessun vicino è migliore, la soluzione è un ottimo locale, non necessariamente globale.
Una ricerca locale $LS$ per un problema di minimo (obiettivo $f$ intero, valore ottimo $z(I)$) parte da $x^0$ e si sposta su vicini strettamente migliori. Quali fatti servono per dimostrare che termina in un ottimo locale dopo al più $f(x^0)-z(I)$ mosse?
Il problema ha un'unica soluzione ottima; ogni mossa migliora strettamente $f$; $f$ è intera
Ogni mossa migliora strettamente $f$; le soluzioni sono finite; con $f$ intera ogni mossa migliora di almeno $1$ e $f\ge z(I)$
La regola è best improvement; le soluzioni sono finite; $f$ è convessa e $f\ge z(I)$
L'intorno è esatto; le soluzioni sono finite; con $f$ intera ogni mossa migliora di almeno $1$ e $f\ge z(I)$
Spiegazione. La terminazione segue dal miglioramento stretto su un insieme finito; il numero di mosse dalla diminuzione di almeno $1$ per mossa fino al più a $z(I)$. Non serve che l'intorno sia esatto.
Nel TSP simmetrico, una mossa 2-opt toglie due lati non adiacenti del giro e ricollega i due cammini nell'unico altro modo che dà un giro. Quante mosse ha l'intorno 2-opt di un giro con $n=10$ città?
$35$
$45$
$90$
$100$
Spiegazione. L'intorno 2-opt ha $\frac{n(n-3)}{2}=\frac{10\cdot 7}{2}=35$ mosse: le coppie di lati non adiacenti del giro. $45=\binom{10}{2}$ conta tutte le coppie di città.
Nello scheduling $P\,||\,C_{\max}$, l'intorno move sposta un lavoro su un'altra macchina e l'intorno swap scambia due lavori su macchine diverse. Una soluzione di $LPT$ è un ottimo locale per l'intorno move. Che cosa se ne può concludere?
È un ottimo globale, perché move esamina tutti i lavori
È un ottimo locale anche per l'intorno swap
È un ottimo locale per ogni intorno del problema
Nulla sull'ottimalità globale: una mossa swap può ancora migliorarla
Spiegazione. Un ottimo locale dipende dall'intorno: nelle dispense una soluzione di $LPT$ è un ottimo locale per move ma non per swap, che la migliora.
Nella ricerca locale per il bin packing (o per $P\,||\,C_{\max}$) si minimizza $SQ=\sum_b L_b^2$, dove $L_b$ è il carico (peso totale) del contenitore $b$. Una mossa sposta un oggetto di peso $\delta=2$ dal contenitore $a$, con $L_a=9$, al contenitore $b$, con $L_b=5$. Di quanto cambia $SQ$?
$0$
$8$
$-8$
$-16$
Spiegazione. Cambiano solo i due carichi: $(L_a-\delta)^2+(L_b+\delta)^2-L_a^2-L_b^2=2\delta(L_b-L_a+\delta)=2\cdot 2\cdot(5-9+2)=-8$; infatti $49+49-81-25=-8$.
Due ricerche locali partono dalla stessa soluzione ammissibile, ma usano intorni diversi $N_1$ e $N_2$ (e si spostano solo su vicini strettamente migliori). Arrivano alla stessa soluzione?
Non necessariamente: l'ottimo locale dipende dall'intorno
Sì: un ottimo locale è unico per ogni istanza
Sì, se entrambe usano first improvement
No: con intorni diversi la ricerca non termina
Spiegazione. Un ottimo locale per $N_1$ può avere vicini migliori in $N_2$ (la soluzione di $LPT$ è un ottimo locale per move ma non per swap). Entrambe terminano.
Una ricerca locale con intorno $N$ parte da una soluzione che è già un ottimo locale rispetto a $N$. Che cosa fa?
Riparte da una soluzione casuale
Dichiara che la soluzione è un ottimo globale
Si sposta comunque sul vicino migliore, anche se peggiore
Esamina l'intorno, non trova vicini migliori e la restituisce
Spiegazione. Accetta solo vicini strettamente migliori: si ferma subito. Non può dire nulla sull'ottimo globale, e spostarsi su vicini peggiori è un'idea delle metaeuristiche.
In $P\,||\,C_{\max}$ il carico $L_h$ di una macchina è la somma dei tempi dei suoi lavori, e una macchina è critica se il suo carico è uguale al makespan $C_{\max}=\max_hL_h$. Con carichi $(9,11,7)$, quali macchine sono critiche?
Le macchine $1$ e $2$
Solo la macchina $3$
Solo la macchina $2$
Tutte e tre
Spiegazione. $C_{\max}=11$ e solo la macchina $2$ ha carico $11$. La macchina $3$ è la meno carica, non la critica.
Per studiare una ricerca locale per il bin packing da molte soluzioni di partenza casuali, come si genera una soluzione casuale (sempre ammissibile)?
First Fit Decreasing con pareggi casuali
First Fit su un ordine casuale degli oggetti
Un contenitore casuale per ogni oggetto
Next Fit sull'ordine dato degli oggetti
Spiegazione. Un contenitore casuale per ogni oggetto può superare la capacità; First Fit su un ordine rimescolato (Fisher–Yates) dà sempre una soluzione ammissibile e varia con il seme.
Una ricerca locale per un problema di minimo con obiettivo a valori interi si sposta solo su vicini strettamente migliori. Parte da una soluzione di valore $40$, e il valore ottimo è $31$. Al più quante mosse esegue?
$40$
Nessun limite: può ciclare
$31$
$9$
Spiegazione. Ogni mossa migliora di almeno $1$ e il valore non scende sotto $31$: al più $40-31=9$ mosse. Non visita mai due volte la stessa soluzione, quindi non cicla.
Nella ricerca locale, per ogni intorno si fissa l'ordine in cui le mosse sono esaminate. Perché?
Garantisce che l'ottimo locale sia anche globale
Cambia l'insieme dei vicini della soluzione corrente
Decide il vicino accettato con first improvement, e i pareggi
Riduce la dimensione dell'intorno da esplorare
Spiegazione. I vicini sono gli stessi in qualunque ordine; ma first improvement accetta il primo migliorante, e best improvement risolve i pareggi a favore del primo esaminato.
Nella ricerca locale, che cosa determina la dimensione di un intorno (il numero di vicini di una soluzione)?
Il valore ottimo dell'istanza
Il costo di un'iterazione: i vicini da valutare
Il numero di iterazioni prima di fermarsi
La qualità della soluzione di partenza
Spiegazione. A ogni iterazione si valutano (al più) tutti i vicini: la dimensione dell'intorno moltiplicata per il costo di valutare una mossa dà il costo di un'iterazione.
Nella ricerca locale per lo zaino 0/1, l'intorno flip aggiunge o toglie un oggetto, e l'intorno swap toglie un oggetto selezionato e ne aggiunge uno non selezionato. Quale dei due può cambiare il numero di oggetti selezionati?
Solo il flip
Solo lo swap
Entrambi
Nessuno dei due
Spiegazione. Un flip aggiunge o toglie un oggetto, uno swap mantiene il numero di oggetti: i due intorni sono complementari, e flip+swap è la loro unione.
Zaino 0/1 con $n=4$ oggetti e oggetti selezionati $S=\{1,3\}$. Gli swap (un oggetto $j\in S$ fuori, un oggetto $k\notin S$ dentro) si esaminano per $j$ crescente e, per ogni $j$, per $k$ crescente. In quale ordine?
$(2,1),(4,1),(2,3),(4,3)$
$(1,3),(2,4),(1,4),(2,3)$
$(1,2),(3,2),(1,4),(3,4)$
$(1,2),(1,4),(3,2),(3,4)$
Spiegazione. La coppia $(j,k)$ indica $j$ fuori e $k$ dentro: prima $j=1$ con $k=2,4$, poi $j=3$ con $k=2,4$. In tutto $|S|(n-|S|)=4$ swap.
Ricerca locale per il bin packing con $c=10$. Lo swap scambia l'oggetto $j$ (peso $3$, nel contenitore $a$ di carico $8$) con l'oggetto $k$ (peso $5$, nel contenitore $b$ di carico $9$), se entrambi i contenitori restano entro la capacità. È ammesso, e con quali carichi?
No: il contenitore $a$ supera $10$
Sì: carichi $6$ e $11$
Sì: carichi $10$ e $7$
No: gli oggetti hanno peso diverso
Spiegazione. $L_a-3+5=10\le10$ e $L_b-5+3=7\le10$: ammesso. Gli swap con pesi uguali sono quelli esclusi, perché non cambiano nessun carico.
Nella ricerca locale per il bin packing, l'intorno move sposta un oggetto in un altro contenitore non vuoto in cui entra, e ha al più $n\,(nb-1)$ elementi ($n$ oggetti, $nb$ contenitori). Con $n=6$ e $nb=4$, quanti elementi al più?
$36$
$18$
$24$
$15$
Spiegazione. Ogni oggetto può andare in uno degli altri $nb-1=3$ contenitori: $6\cdot3=18$, prima del test di capacità. $15=\frac{6\cdot5}2$ è il bound dello swap.
Nel TSP la mossa 2-opt di posizioni $i<j$ toglie i lati $\{\sigma_i,\sigma_{i+1}\}$ e $\{\sigma_j,\sigma_{j+1}\}$ e inverte il cammino $\sigma_{i+1},\dots,\sigma_j$. Dal giro $(1,2,3,4,5,6)$, con $i=2$ e $j=5$, quale giro si ottiene?
$(1,2,5,4,3,6)$
$(1,2,4,3,5,6)$
$(1,5,4,3,2,6)$
$(1,2,3,5,4,6)$
Spiegazione. Si tolgono $\{2,3\}$ e $\{5,6\}$ e si inverte il cammino $3,4,5$: $(1,2,5,4,3,6)$, con i nuovi lati $\{2,5\}$ e $\{3,6\}$.
Nel TSP la mossa Or-opt sposta un segmento di $\ell\in\{1,2,3\}$ città consecutive fra due altre città consecutive, e l'intorno ha $\sum_{\ell=1}^3(n-\ell)(n-\ell-1)$ elementi. Quanti sono con $n=6$?
$20$
$216$
$9$
$38$
Spiegazione. $5\cdot4+4\cdot3+3\cdot2=20+12+6=38$. $9=\frac{n(n-3)}2$ è la dimensione del 2-opt, $20$ conta solo i segmenti di una città.
In $P\,||\,C_{\max}$, lo swap scambia due lavori $j<k$ su macchine diverse con durate diverse. Con durate $t=(5,4,4,3)$ e macchine $mach=(1,1,2,2)$, quanti swap si considerano?
$4$
$6$
$3$
$2$
Spiegazione. Coppie su macchine diverse: $(1,3)$, $(1,4)$, $(2,3)$, $(2,4)$; $(2,3)$ ha durate uguali ($4$ e $4$) e non cambierebbe nessun carico: restano $3$.
Nella ricerca locale per $P\,||\,C_{\max}$ l'intorno move sposta un lavoro su un'altra macchina. Perché, a differenza del bin packing, non serve alcun test di ammissibilità?
Perché le macchine hanno tutte lo stesso carico
Non c'è capacità: ogni assegnamento dei lavori è ammissibile
Perché una move non cambia mai il makespan
Perché si spostano solo i lavori più corti
Spiegazione. Le macchine non hanno un limite di carico: qualunque vettore $mach$ è uno schedule. Nel bin packing un contenitore non può superare $c$.
Una ricerca locale best improvement per un problema di minimo valuta quattro vicini di una soluzione da $20$ e ottiene, nell'ordine, $17$, $15$, $15$, $18$. A parità di valore vince il vicino valutato prima. Su quale si sposta?
Il secondo, di valore $15$
Il terzo, di valore $15$
Il primo, di valore $17$
Il quarto, di valore $18$
Spiegazione. Il valore minimo $15$ è in pareggio fra il secondo e il terzo vicino: vince il primo esaminato. First improvement avrebbe scelto il primo vicino ($17<20$).
Zaino con $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, soluzione $x=(0,0,1,1)$ (profitto $10$). Si esaminano, in quest'ordine, i flip $1,2,3,4$ (aggiungere/togliere l'oggetto) e poi gli swap «$3$ fuori, $1$ dentro», «$3$ fuori, $2$ dentro», «$4$ fuori, $1$ dentro», «$4$ fuori, $2$ dentro». Quale vicino accetta first improvement?
$(1,0,1,0)$, profitto $16$
$(0,0,1,0)$, profitto $6$
$(1,0,0,1)$, profitto $14$
$(1,1,0,0)$, profitto $17$
Spiegazione. I flip $1$ e $2$ superano $9$, i flip $3$ e $4$ tolgono un oggetto (profitto $4$ e $6$); il primo swap, «$3$ fuori, $1$ dentro», dà peso $8$ e profitto $14>10$. $(1,0,1,0)$ è la scelta di best improvement.
Nel TSP, il giro corrente è lungo $25$ e le sue $5$ mosse 2-opt, nell'ordine di esame, hanno variazioni di lunghezza $\Delta=+4,\,0,\,-3,\,-1,\,-6$. Quanto è lungo il giro dopo una mossa best improvement, e dopo una mossa first improvement?
Best $19$, first $22$
Best $22$, first $19$
Best $19$, first $25$
Best $21$, first $22$
Spiegazione. Best sceglie $\Delta=-6$: $25-6=19$. First accetta la prima mossa con $\Delta<0$, la terza: $25-3=22$. $\Delta=0$ non è migliorante.
La regola best improvement esegue la «discesa più ripida». Che cosa costa ogni sua iterazione?
La valutazione dei vicini fino al primo migliorante
Un'esplorazione dell'intero spazio di ricerca
La valutazione di un solo vicino
Un'esplorazione completa dell'intorno
Spiegazione. Esamina tutti i vicini e prende il migliore, così ogni mossa migliora il più possibile; fermarsi al primo migliorante è first improvement.
Sullo zaino con $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, da $x=(0,0,1,1)$ con l'intorno flip+swap, first improvement segue il percorso di profitti $10\to14\to17$ ($14$ vicini esaminati) e best improvement $10\to16\to17$ ($18$ vicini). Che cosa mostra l'esempio?
Best improvement esamina sempre meno vicini di first
First improvement non raggiunge mai la soluzione ottima
Percorsi diversi allo stesso ottimo; qui first esamina meno vicini
I due percorsi di ricerca sono sempre uguali
Spiegazione. Entrambe arrivano a $17$ con $2$ mosse, ma per strade diverse. Il solo intorno flip si sarebbe fermato subito a $10$.
In $P\,||\,C_{\max}$, la variazione del makespan per una move si calcola dai carichi correnti: $\max\{L_a-t_j,\,L_h+t_j,\,\max_{q\ne a,h}L_q\}-\max_qL_q$. Perché costa $O(m)$ e non $O(1)$?
Serve il massimo sui carichi delle altre macchine
Bisogna ricalcolare i carichi da zero
Bisogna riordinare i lavori di ogni macchina
Bisogna provare tutte le $m$ macchine di arrivo
Spiegazione. Cambiano solo due carichi, ma il nuovo makespan dipende anche dagli altri $m-2$. Per questo un'iterazione move costa $O(nm^2)$.
Nella ricerca locale per lo zaino con valutazione incrementale si conservano profitto e peso della soluzione corrente: $16$ e $8$. Uno swap toglie l'oggetto $j$ ($p_j=6$, $w_j=3$) e aggiunge l'oggetto $k$ ($p_k=7$, $w_k=4$). Quali sono il nuovo profitto e il nuovo peso?
Profitto $15$, peso $7$
Profitto $17$, peso $7$
Profitto $23$, peso $11$
Profitto $17$, peso $9$
Spiegazione. $16+7-6=17$ e $8+4-3=9$, in tempo $O(1)$. $23$ e $11$ dimenticano di togliere l'oggetto $j$.
Sull'istanza di riferimento del TSP a $5$ città (ottimo $18$), la ricerca locale 2-opt dal giro del nearest neighbour (lunghezza $25$) arriva all'ottimo con $2$ mosse sia con first improvement ($12$ valutazioni) sia con best improvement ($15$ valutazioni), per percorsi diversi. Che cosa mostra?
Best improvement richiede sempre meno valutazioni di first
La ricerca 2-opt trova sempre il giro ottimo dell'istanza
Su istanze piccole entrambe arrivano all'ottimo, a costo simile
First improvement esegue sempre più mosse di best
Spiegazione. Con $5$ città l'intorno ha solo $5$ mosse ed entrambe le regole trovano l'ottimo; sull'istanza a $10$ città si fermano invece in ottimi locali diversi.
Nella ricerca locale 2-opt per il TSP la città $1$ resta sempre in prima posizione ($\sigma_1=1$). Perché nessuna mossa la sposta?
Perché la città $1$ non appartiene a nessun lato
Il cammino invertito parte sempre dalla posizione $i+1\ge2$
Perché la città $1$ ha la distanza minima da tutte
Perché le mosse con $i=1$ sono escluse
Spiegazione. La mossa inverte $\sigma_{i+1},\dots,\sigma_j$ con $i\ge1$: la posizione $1$ non è mai toccata. Le mosse con $i=1$ esistono (si esclude solo $i=1$, $j=n$).
Nel TSP una mossa Or-opt toglie il segmento $s_1,\dots,s_\ell$ fra $p$ e $q$ e lo inserisce fra $a$ e $b$: $\Delta=d_{pq}+d_{as_1}+d_{s_\ell b}-d_{ps_1}-d_{s_\ell q}-d_{ab}$. Segmento $(9)$ fra $p=7$ e $q=8$, inserito fra $a=3$ e $b=4$, con $d_{78}=3$, $d_{39}=4$, $d_{94}=3$, $d_{79}=4$, $d_{98}=4$, $d_{34}=4$. Quanto vale $\Delta$?
$-2$
$+2$
$-6$
$0$
Spiegazione. Lati aggiunti $3+4+3=10$, lati tolti $4+4+4=12$: $\Delta=-2$, la mossa accorcia il giro.
Una mossa Or-opt nel TSP toglie tre lati e reinserisce un segmento di al più $3$ città senza invertirlo. Che relazione c'è con l'intorno 3-opt?
È disgiunta da 3-opt: toglie soltanto due lati
Coincide con una mossa 2-opt applicata due volte
Contiene tutte le mosse dell'intorno 3-opt
È la parte di 3-opt che si esplora in tempo $O(n^2)$
Spiegazione. 3-opt considera tutti i modi di togliere tre lati e ricollegare, con $O(n^3)$ mosse; Or-opt ne prende la parte con segmenti corti e orientamento conservato.
Su un'istanza del TSP a $10$ città (ottimo $39$), dal giro del nearest neighbour (lunghezza $49$) la ricerca 2-opt con first improvement si ferma a $41$ dopo $138$ valutazioni, quella con best improvement arriva a $39$ dopo $140$. Che cosa mostra?
First improvement è sempre più veloce di best improvement
Best improvement trova sempre l'ottimo globale
Le due regole possono fermarsi in ottimi locali diversi
L'intorno 2-opt è esatto su questa istanza
Spiegazione. Dallo stesso giro i percorsi divergono; delle $181\,440$ soluzioni, $3$ sono ottimi locali 2-opt ($39$, $41$, $43$), quindi l'intorno non è esatto.
Come lavora l'euristica di Lin–Kernighan per il TSP?
Risolve il modello PLI del TSP su un sottoinsieme di città
Concatena un numero variabile di scambi di lati, scelti in modo greedy
Esplora per intero l'intorno 3-opt a ogni iterazione
Prova tutte le mosse $k$-opt per ogni $k$ fino a $n$
Spiegazione. Si ferma quando il guadagno totale non può più diventare positivo: esplora parte dell'intorno $k$-opt per ogni $k$ in un tempo vicino a quello di 2-opt.
L'intorno 3-opt del TSP toglie tre lati e ricollega i tre cammini in tutti i modi. Quanto costa un'iterazione, e come si usa in pratica?
$O(n^3)$; in pratica si esplora solo in parte
$O(n^2)$; si esplora sempre tutto l'intorno
$O(n)$; costa meno dell'intorno 2-opt
$O(2^n)$; per questo non si usa mai
Spiegazione. I suoi ottimi locali sono migliori di quelli di 2-opt, ma il costo $O(n^3)$ per iterazione porta a esplorarlo solo in parte (Or-opt, Lin–Kernighan).
In $P\,||\,C_{\max}$ la variazione del makespan di una mossa che trasferisce $\delta$ dalla macchina $a$ alla $b$ è $F=\max\{L_a-\delta,\,L_b+\delta,\,\max_{q\ne a,b}L_q\}-\max_qL_q$. Con carichi $(12,7,9)$ e $\delta=3$ dalla macchina $1$ alla $2$, quanto vale $F$?
$+1$
$0$
$-3$
$-2$
Spiegazione. Nuovi carichi $(9,10,9)$: makespan $10$ contro $12$, quindi $F=-2$. $-3$ guarda solo la macchina $1$ e dimentica che la $2$ sale a $10$.
Nella ricerca locale per $P\,||\,C_{\max}$ con $n$ lavori e $m$ macchine, la variazione del makespan si valuta in $O(m)$. Quanto costa un'iterazione con l'intorno move e con l'intorno swap?
Move $O(nm)$, swap $O(n^2)$
Move $O(n^2m)$, swap $O(nm^2)$
Move $O(nm^2)$, swap $O(n^2m)$
Entrambi $O(nm)$
Spiegazione. Move: $n(m-1)$ mosse per $O(m)$; swap: $O(n^2)$ coppie per $O(m)$. Senza il fattore $O(m)$ si avrebbe $O(nm)$ e $O(n^2)$.
$P\,||\,C_{\max}$ con carichi $(12,7,10)$: la macchina $1$ è l'unica critica. Una move sposta un lavoro di durata $4$ dalla macchina $1$ alla macchina $2$. Quanto diventa il makespan?
$12$
$11$
$8$
$10$
Spiegazione. Nuovi carichi $(8,11,10)$: il makespan scende da $12$ a $11$, il carico della macchina che riceve il lavoro. $8$ guarda solo la macchina $1$.
$P\,||\,C_{\max}$ con $m=3$: la soluzione di $LPT$ ha carichi $(11,8,8)$, e la macchina $1$ (critica) contiene lavori di durata $5$, $3$, $3$. Perché nessuna move (un lavoro su un'altra macchina) abbassa il makespan?
Spostare il $5$ porta la macchina che lo riceve a $13$, un $3$ a $11$
Perché la macchina $1$ non è l'unica macchina critica
Perché le move non cambiano mai il carico della macchina $1$
Perché i lavori di durata $3$ non si possono spostare
Spiegazione. Ogni move dalla macchina $1$ alza un'altra macchina da $8$ ad almeno $11$; le move dalle altre macchine alzano la macchina $1$. La soluzione è un ottimo locale per move, ma non per swap.
$P\,||\,C_{\max}$ con carichi $(11,8,8)$. Uno swap scambia il lavoro $1$ (durata $5$, sulla macchina $1$) con il lavoro $3$ (durata $4$, sulla macchina $3$). Quali sono i nuovi carichi?
$(10,9,8)$
$(6,8,13)$
$(12,8,7)$
$(10,8,9)$
Spiegazione. Si trasferisce $\delta=5-4=1$ dalla macchina $1$ alla $3$: $(10,8,9)$, makespan $10<11$. $(6,8,13)$ sarebbe la move del solo lavoro $1$.
$P\,||\,C_{\max}$ con $m=4$ e $12$ lavori, makespan ottimo $19$: $LPT$ dà carichi $(20,19,18,19)$, e questa soluzione è un ottimo locale sia per move sia per swap. Che cosa mostra l'esempio?
Lo swap migliora sempre la soluzione trovata da $LPT$
$LPT$ trova sempre il makespan ottimo dell'istanza
Anche più intorni insieme possono fermarsi sopra l'ottimo
Il lower bound $19$ non è raggiungibile su questa istanza
Spiegazione. Sull'istanza a $7$ lavori lo swap portava all'ottimo; qui né move né swap migliorano $20$, anche se l'ottimo $19=\lceil76/4\rceil$ esiste.
Nella ricerca locale per il bin packing e per $P\,||\,C_{\max}$ il paesaggio è fatto di ampi plateau (molte soluzioni con lo stesso valore). Perché?
Perché le soluzioni casuali sono quasi tutte inammissibili
Il numero di contenitori varia poco; il makespan dipende dalle macchine critiche
Perché gli intorni move e swap sono troppo grandi da esplorare
Perché i due problemi hanno sempre un'unica soluzione ottima
Spiegazione. Gli obiettivi sono «grossolani»: quasi tutte le mosse lasciano invariato il numero di contenitori, e una mossa che non tocca la macchina critica non cambia il makespan.
Bin packing con $c=10$ e $12$ oggetti: le $100$ soluzioni di First Fit su ordini casuali hanno in tutto $2374$ vicini move e swap, e tutti hanno lo stesso numero di contenitori della soluzione corrente. Che cosa mostra?
Con l'obiettivo «numero di contenitori» la ricerca è cieca
Le $100$ soluzioni di partenza sono già tutte ottime
Move e swap producono soltanto soluzioni inammissibili
L'istanza ha un solo ottimo locale per la ricerca
Spiegazione. Nessun vicino migliora né peggiora: una ricerca che accetta solo mosse strettamente miglioranti non si muove. Solo $14$ delle $100$ soluzioni sono ottime.
Come obiettivo ausiliario si usa la somma dei quadrati dei carichi: nel bin packing $\sum_bL_b^2$ si massimizza, in $P\,||\,C_{\max}$ $\sum_hL_h^2$ si minimizza. Perché versi opposti?
Perché il bin packing è un problema di massimo
Perché in $P\,||\,C_{\max}$ il totale dei tempi cambia con le mosse
Perché nel bin packing i carichi possono essere negativi
Il BPP vuole carichi sbilanciati, $P\,||\,C_{\max}$ bilanciati
Spiegazione. A totale fisso la somma dei quadrati è grande quando i carichi sono sbilanciati. Nel bin packing si vogliono pochi contenitori pieni e gli altri vuoti; in $P\,||\,C_{\max}$ carichi uguali. Il totale ($\sum_jw_j$ o $\sum_jt_j$) non cambia con le mosse.
Se una quantità $\delta>0$ passa dal carico $L_a$ al carico $L_b$, la somma dei carichi al quadrato varia di $2\delta(L_b-L_a+\delta)$. Quando aumenta?
Se e solo se $L_b>L_a$
Se e solo se $\delta>L_a$
Se e solo se $L_b+\delta>L_a$
Se e solo se $L_b+\delta<L_a$
Spiegazione. Con $\delta>0$ il segno è quello di $L_b-L_a+\delta$: l'elemento va in un carico che, dopo la mossa, supera quello che ha lasciato.
Bin packing con $c=7$, ricerca move con obiettivo $SQ=\sum_bL_b^2$ da massimizzare e best improvement (pareggi: la mossa esaminata prima). Con carichi $(7,2,5,7)$ due mosse hanno il guadagno massimo $20$: l'oggetto $3$ (peso $5$, esaminato prima) dal contenitore $3$ al $2$, e l'oggetto $5$ (peso $2$) dal contenitore $2$ al $3$. Quale si applica, e con che risultato?
Nessuna: il numero di contenitori non cambia
L'oggetto $3$: carichi $(7,7,7)$, tre contenitori
L'oggetto $5$: carichi $(7,7,7)$, tre contenitori
L'oggetto $3$: carichi $(7,2,0,12)$, quattro contenitori
Spiegazione. Il pareggio va alla mossa esaminata prima, l'oggetto $3$: svuota il contenitore $3$ e lascia $(7,7,7)$, $SQ=147$, che è ottimo. Anche l'oggetto $5$ svuoterebbe un contenitore, ma viene dopo.
Nella ricerca locale move per il bin packing con obiettivo $f=nb$ (numero di contenitori), il guadagno di una mossa è il miglioramento di $f$. Quanto vale?
$1$ se la mossa svuota un contenitore, $0$ altrimenti
Il peso dell'oggetto spostato
La differenza fra i carichi dei due contenitori
$-1$ se la mossa apre un contenitore nuovo
Spiegazione. Le move vanno solo in contenitori non vuoti, quindi non aprono mai contenitori: $nb$ scende di $1$ se il contenitore di partenza si svuota, altrimenti resta uguale.
Nel bin packing la ricerca locale swap (scambio di due oggetti di peso diverso in contenitori diversi) si usa solo con l'obiettivo ausiliario $SQ=\sum_bL_b^2$, non con il numero di contenitori. Perché?
Perché con $SQ$ lo swap diventa una move
Perché lo swap aumenta sempre il numero di contenitori
Perché uno swap produce sempre contenitori inammissibili
Uno swap non cambia mai il numero di contenitori
Spiegazione. Entrambi i contenitori restano non vuoti e non se ne crea nessuno: con $f=nb$ nessuno swap sarebbe migliorante.
Bin packing con $c=7$ e obiettivo $SQ=\sum_bL_b^2$ (da massimizzare). Uno swap scambia l'oggetto $j$ (peso $4$, contenitore $a$ di carico $6$) con l'oggetto $k$ (peso $2$, contenitore $b$ di carico $5$): passa $\delta=w_j-w_k$ da $a$ a $b$, e $SQ$ varia di $2\delta(L_b-L_a+\delta)$. Di quanto?
$-4$
$+8$
$+4$
$0$
Spiegazione. $\delta=2$: $2\cdot2\cdot(5-6+2)=4$. I carichi passano da $(6,5)$ a $(4,7)$, entrambi entro $7$: $16+49-36-25=4$.
Bin packing con $c=7$: i carichi $(5,5)$ usano $2$ contenitori e danno $SQ=\sum_bL_b^2=50$, i carichi $(7,2,1)$ ne usano $3$ e danno $SQ=54$. Che cosa insegna il confronto?
L'obiettivo $SQ$ si può usare solo per $P\,||\,C_{\max}$
$SQ$ è una guida: la qualità si misura con il numero di contenitori
Massimizzare $SQ$ equivale a minimizzare i contenitori
La soluzione con $3$ contenitori è la migliore delle due
Spiegazione. Una soluzione con più contenitori può avere $SQ$ maggiore: l'obiettivo ausiliario è una guida, non l'obiettivo.
Bin packing con $c=7$ e pesi $(4,4,5,3,2,3)$ (ottimo $3$). Dalla soluzione di Next Fit ($5$ contenitori), la ricerca move con obiettivo «numero di contenitori» si ferma a $4$; con l'obiettivo $SQ=\sum_bL_b^2$ arriva a $3$, passando per una mossa che non cambia il numero di contenitori. Che cosa mostra?
Una mossa «neutra» per l'obiettivo può preparare quella che migliora
Con $SQ$ ogni mossa riduce il numero di contenitori
La soluzione di Next Fit è già un ottimo locale
Con $SQ$ la ricerca può peggiorare il numero di contenitori
Spiegazione. La seconda mossa ($SQ$ da $115$ a $127$) lascia $4$ contenitori ma rende possibile la terza, che svuota un contenitore. Con $SQ$ una move non aumenta mai il numero di contenitori.
Bin packing con $c=10$ e $12$ oggetti (ottimo $5$): da $100$ soluzioni di First Fit su ordini casuali ($14$ già ottime), la ricerca move con obiettivo «numero di contenitori» termina con $5$ contenitori in $14$ casi, con obiettivo $SQ=\sum_bL_b^2$ in $76$. Che cosa mostra l'esperimento?
La ricerca move con $SQ$ trova sempre la soluzione ottima
Le soluzioni di First Fit sono quasi sempre ottime
L'obiettivo ausiliario peggiora le soluzioni di partenza
Con il numero di contenitori resta sui plateau; con $SQ$ no
Spiegazione. Con $f=nb$ nessuna delle $100$ soluzioni migliora; con $SQ$ altre $62$ esecuzioni raggiungono l'ottimo, ma non tutte.
Zaino con $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$: $x=(1,0,1,0)$ (profitto $16$) è un ottimo locale per l'intorno flip ristretto alle soluzioni ammissibili, mentre l'ottimo è $(1,1,0,0)$. Perché i flip non ci arrivano?
Perché l'oggetto $2$ non entra mai nello zaino
Perché i flip non possono togliere oggetti dallo zaino
Servono due flip, e il passo intermedio è inammissibile o peggiore
Perché $(1,1,0,0)$ non è una soluzione ammissibile
Spiegazione. Bisogna aggiungere $2$ e togliere $3$: passando per $(1,1,1,0)$ (peso $12$) o per $(1,0,0,0)$ (profitto $10<16$). Lo swap fa i due flip insieme; le penalità lasciano attraversare il vettore inammissibile.
Nella ricerca locale penalizzata per lo zaino si massimizza $g_\alpha(x)=\sum_jp_jx_j-\alpha\max\{0,\sum_jw_jx_j-c\}$. Con $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, $x=(1,1,1,0)$ e $\alpha=2$, quanto vale $g_\alpha(x)$?
$14$
$17$
$23$
$20$
Spiegazione. Profitto $23$, peso $12$, eccesso $3$: $23-2\cdot3=17$. $20$ e $14$ corrispondono a $\alpha=1$ e $\alpha=3$.
La ricerca locale flip+swap per lo zaino 0/1 con $n$ oggetti esamina i flip e poi gli swap, scartando i vicini che superano la capacità. Quanto costa un'iterazione?
$O(n^2)$, a causa degli swap
$O(n)$, a causa dei flip
$O(n\log n)$, per l'ordinamento
$O(2^n)$, per i sottoinsiemi
Spiegazione. I flip sono $n$, gli swap fino a $|S|(n-|S|)\le n^2/4$, ciascuno valutato in $O(1)$ con profitto e peso conservati.
Nella ricerca locale flip+swap per lo zaino (flip esaminati prima degli swap) con la regola first improvement, che cosa succede in un'iterazione in cui c'è un flip migliorante?
Si applicano insieme il flip e lo swap migliore
Il flip viene scartato a favore degli swap
Si esaminano comunque tutti gli swap
Gli swap non vengono esaminati
Spiegazione. First improvement accetta il primo vicino migliorante nell'ordine di esame: il flip trovato chiude l'iterazione.
Su un'istanza del TSP a $10$ città (ottimo $39$), la discesa a intorni variabili ($VND$) con $N_1=$ 2-opt e $N_2=$ Or-opt (first improvement) porta il giro del nearest neighbour da $49$ a $41$ con mosse 2-opt, poi a $39$ con una mossa Or-opt, e si ferma. Che cosa mostra?
Or-opt da solo trova sempre il giro ottimo
$VND$ usa solo l'intorno più grande
Or-opt migliora un ottimo locale di 2-opt
2-opt e Or-opt hanno gli stessi ottimi locali
Spiegazione. $41$ è un ottimo locale 2-opt ma non Or-opt; il giro ottimo è l'unico ottimo locale per entrambi gli intorni su questa istanza.
$P\,||\,C_{\max}$ con $m=4$ e $12$ lavori: da $100$ assegnazioni casuali, la ricerca move con obiettivo $\sum_hL_h^2$ raggiunge l'ottimo in $4$ casi, $VND$ (move poi swap) con lo stesso obiettivo in $68$, $VND$ con il makespan in $15$. Che cosa mostrano i numeri?
$VND$ trova sempre la soluzione ottima
Intorni combinati e obiettivo ausiliario si sommano
Lo swap da solo è sempre migliore di $VND$
Il makespan guida meglio di $\sum_hL_h^2$
Spiegazione. Ognuna delle due idee aiuta da sola, e insieme danno $68$ esecuzioni ottime su $100$, contro $4$ e $15$.
Su un TSP a $10$ città (ottimo $39$), da $100$ giri casuali: 2-opt con first improvement termina nell'ottimo in $46$ casi, con best improvement in $87$, e $VND$ (2-opt e Or-opt) in tutti i $100$. Che cosa mostra?
Qui best batte first, e $VND$ trova sempre l'ottimo
First improvement è sempre migliore di best improvement
Ogni giro casuale porta all'ottimo con 2-opt
Il multi-start non serve con $VND$ su nessuna istanza
Spiegazione. Su questa istanza il giro ottimo è l'unico ottimo locale sia per 2-opt sia per Or-opt, quindi $VND$ lo raggiunge da ogni partenza; su istanze grandi non succede.
Su un TSP a $30$ città (ottimo $478$), $100$ giri casuali lunghi in media circa $1769$ diventano, dopo la ricerca 2-opt, giri lunghi in media circa $488$ ($2\%$ sopra l'ottimo); solo circa un'esecuzione su otto raggiunge l'ottimo. Che cosa mostra?
I giri casuali sono buone soluzioni di partenza
Più esecuzioni non aumentano mai la probabilità di trovare l'ottimo
La ricerca 2-opt trova l'ottimo in quasi tutte le esecuzioni
Si arriva vicino all'ottimo in media, ma ogni esecuzione resta nella sua valle
Spiegazione. Gli ottimi locali distinti sono più di $50$: la ricerca migliora moltissimo, ma l'ottimo dipende dalla valle di partenza.
In una ricerca locale multi-start ogni esecuzione raggiunge l'ottimo con probabilità $q=0.12$, indipendentemente dalle altre, quindi $M$ esecuzioni lo mancano tutte con probabilità $0.88^M$. Quante esecuzioni servono almeno perché questa probabilità scenda sotto l'$1\%$?
$10$
$9$
$37$
$100$
Spiegazione. $0.88^{36}\approx0.0100$ e $0.88^{37}\approx0.0088<0.01$: servono $37$ esecuzioni. Con $10$ la probabilità di mancarlo è ancora circa $0.28$.
Nella ricerca locale multi-start, perché la probabilità $q$ che una singola esecuzione da una partenza casuale raggiunga l'ottimo diminuisce sulle istanze grandi?
Perché la ricerca locale non termina più
Il numero di ottimi locali cresce molto rapidamente con $n$
Perché le esecuzioni diventano dipendenti fra loro
Perché l'intorno diventa esatto per $n$ grande
Spiegazione. Con $10$ città i giri ottimi locali 2-opt sono $3$, con $30$ città $100$ esecuzioni ne trovano più di $50$ distinti: le valli si moltiplicano.
Una ricerca locale per un problema di minimo si ferma in un ottimo locale di valore $f^*$ ($z(I)$ = valore ottimo). Quale relazione si può scrivere con certezza?
$f^*=z(I)$
$z(I)\ge f^*/2$
$f^*\le z(I)$
$z(I)\le f^*$
Spiegazione. L'ottimo locale è una soluzione ammissibile: per un minimo il suo valore è un upper bound. Che si sia fermata non dice che sia arrivata all'ottimo.
Nella ricerca locale 2-opt per il TSP simmetrico, il giro $(1,3,2,4,5)$ è lungo $25$. La mossa che toglie i lati $\{3,2\}$ e $\{4,5\}$ e aggiunge $\{3,4\}$ e $\{2,5\}$ ha $d_{32}=4$, $d_{45}=6$, $d_{34}=3$, $d_{25}=5$. Con la valutazione incrementale, quanto è lungo il nuovo giro?
$17$
$27$
$23$
$25$
Spiegazione. $\Delta=d_{34}+d_{25}-d_{32}-d_{45}=3+5-4-6=-2$, quindi $25-2=23$. Basta guardare i quattro lati che cambiano, invece di ricalcolare tutto il giro.
Nella ricerca locale 2-opt per il TSP con $n$ città, l'intorno ha $\frac{n(n-3)}{2}$ mosse. Quanto costa un'iterazione best improvement con la valutazione incrementale ($O(1)$ per mossa), e quanto ricalcolando ogni giro da zero ($O(n)$ per mossa)?
$O(n^2)$ e $O(n^2)$
$O(n^2)$ e $O(n^3)$
$O(1)$ e $O(n)$
$O(n)$ e $O(n^2)$
Spiegazione. Il costo di un'iterazione è il numero di vicini per il costo di valutarne uno. La valutazione incrementale non cambia gli ottimi locali né il cammino della ricerca, solo il tempo.
In una ricerca locale per un problema di minimo, i vicini della soluzione corrente vengono esaminati in un ordine fisso e hanno variazioni dell'obiettivo $\Delta=(+2,-1,-5,-3)$. Quale vicino scelgono la regola first improvement e la regola best improvement?
First improvement il secondo ($-1$), best improvement il terzo ($-5$)
Entrambe il terzo ($-5$)
First improvement il primo ($+2$), best improvement il terzo ($-5$)
First improvement il secondo ($-1$), best improvement il quarto ($-3$)
Spiegazione. First improvement si ferma al primo vicino che migliora, best improvement esamina tutto l'intorno e prende la variazione più negativa. Con first improvement il risultato dipende dall'ordine di esame.
Nella ricerca locale si confrontano le regole first improvement e best improvement. Quale affermazione è corretta?
Best improvement trova sempre un ottimo locale migliore di first improvement
First improvement non termina se l'intorno è grande
Le due regole seguono sempre lo stesso cammino, con tempi diversi
First improvement fa iterazioni più economiche ma di solito più mosse; le due regole possono fermarsi in ottimi locali diversi
Spiegazione. Nell'ottimo locale entrambe esaminano tutto l'intorno. Prima di arrivarci seguono cammini diversi, e nessuna delle due domina l'altra su tutte le istanze.
Nella ricerca locale per il bin packing che minimizza il numero di contenitori, quasi tutte le mosse (spostare un oggetto in un altro contenitore) lasciano invariato l'obiettivo. Che cosa succede a una ricerca che accetta solo mosse strettamente miglioranti?
Diventa una ricerca casuale, perché tutte le mosse sono equivalenti
Non termina mai, perché le mosse di valore nullo sono infinite
Si ferma su un altopiano, anche se una sequenza di mosse di valore nullo porterebbe a una soluzione migliore
Trova sempre l'ottimo, perché l'obiettivo è intero
Spiegazione. Su un altopiano l'obiettivo non distingue le soluzioni e la ricerca è cieca. Il rimedio è un obiettivo ausiliario, per esempio la somma dei quadrati dei carichi.
Nella ricerca locale per lo zaino 0-1 con penalità, lo spazio di ricerca è $\{0,1\}^n$ e si massimizza il profitto meno una penalità proporzionale al peso in eccesso sulla capacità. Che cosa deve ricordare la ricerca?
Il vettore con la penalità più alta, da evitare
La migliore soluzione ammissibile visitata, perché l'ottimo locale finale può essere inammissibile
Niente: con la penalità ogni ottimo locale è ammissibile
Solo l'ultimo vettore visitato, che è sempre ammissibile
Spiegazione. Con penalità la ricerca può attraversare e fermarsi nella regione inammissibile; la soluzione restituita è la migliore ammissibile incontrata lungo il cammino.
Nella ricerca locale per lo zaino 0-1 con penalità sul peso in eccesso, come influisce il valore della penalità per unità di eccesso?
Grande: gli ottimi locali sono ammissibili ma la ricerca non esce dalla regione ammissibile; piccola: la attraversa ma può fermarsi fuori
Grande: la ricerca diventa casuale; piccola: la ricerca diventa esatta
Non influisce: la penalità cambia solo il valore, non le mosse scelte
Piccola: gli ottimi locali sono sempre ammissibili; grande: mai
Spiegazione. Una penalità alta rende sconveniente ogni vettore inammissibile, una bassa li rende attraenti: il valore bilancia la libertà di movimento e l'ammissibilità del risultato.
In una ricerca locale multi-start ogni esecuzione, da una soluzione iniziale casuale, raggiunge l'ottimo con probabilità $q=0{,}1$, indipendentemente dalle altre. Con $M=10$ esecuzioni, qual è circa la probabilità che nessuna lo trovi?
$0\%$
$10\%$
$90\%$
$35\%$
Spiegazione. Tutte mancano l'ottimo con probabilità $(1-q)^M=0{,}9^{10}\approx 0{,}35$. Le esecuzioni non hanno memoria, e con $n$ grande $q$ diminuisce rapidamente.
Nella ricerca locale multi-start si eseguono $M$ ricerche locali da soluzioni iniziali diverse e si tiene il miglior ottimo locale. Quale affermazione è corretta?
Con $M\ge n$ esecuzioni l'ottimo è garantito
Ogni esecuzione riparte dall'ottimo locale della precedente
Le esecuzioni sono indipendenti e parallelizzabili, ma nessuna usa ciò che hanno trovato le altre
Il risultato dipende dall'ordine delle esecuzioni
Spiegazione. Multi-start è la forma più semplice di diversificazione: senza memoria, ogni esecuzione ricomincia da capo e spende gran parte delle mosse nella discesa.
Ricerca locale per $P\,||\,C_{\max}$ con $3$ macchine di carichi $(10,10,6)$. Si sposta un lavoro di durata $3$ dalla macchina $1$ alla macchina $3$. Come cambia il makespan, e perché?
Scende a $7$, il nuovo carico della macchina $1$
Resta $10$: la macchina $2$ ha ancora carico $10$, e una mossa migliora solo se parte dall'unica macchina critica
Sale a $13$, perché la macchina $3$ riceve il lavoro
Scende a $9$, perché la macchina $3$ arriva a $9$
Spiegazione. I nuovi carichi sono $(7,10,9)$: il massimo resta $10$. Con due macchine critiche nessuna mossa singola migliora il makespan, ed è per questo che serve un obiettivo ausiliario.
Per $P\,||\,C_{\max}$ l'intorno move sposta un lavoro su un'altra macchina e l'intorno swap scambia due lavori su macchine diverse. Quale differenza strutturale c'è fra le due mosse?
Lo swap mantiene il numero di lavori su ogni macchina, la move lo cambia: i due intorni si completano
La move mantiene il numero di lavori su ogni macchina, lo swap lo cambia
Lo swap cambia i carichi di tre macchine, la move di due
Non ci sono differenze: uno swap è sempre una move
Spiegazione. Uno swap equivale a due move, ma come singola mossa non può correggere una macchina con troppi lavori; un ottimo per move può non esserlo per swap, e viceversa.
Una ricerca locale ha bisogno di una soluzione iniziale. Quale scelta è tipica, e quale limite ha sul bin packing se la soluzione di First Fit Decreasing (FFD) è già ottima?
Una soluzione inammissibile, che la ricerca rende ammissibile
La soluzione del rilassamento lineare, sempre intera
La soluzione vuota, perché la ricerca locale aggiunge elementi
La soluzione di un'euristica costruttiva; se è già ottima nessuna mossa la migliora, e conviene partire da soluzioni peggiori per studiare la ricerca
Spiegazione. La ricerca locale migliora una soluzione completa e ammissibile, di solito costruttiva. Da una soluzione già ottima non ci sono mosse miglioranti: per il bin packing le note partono da Next Fit e First Fit.
Per studiare una ricerca locale su molte soluzioni iniziali si generano soluzioni casuali con un generatore di numeri pseudo-casuali (Park e Miller) a partire da un seme. Perché si fissa il seme?
Perché il seme è il numero di iterazioni della ricerca
Perché un seme fisso dà soluzioni iniziali migliori
Lo stesso seme dà le stesse soluzioni iniziali in ogni linguaggio e computer: gli esperimenti sono riproducibili
Perché senza seme il generatore produce solo soluzioni inammissibili
Spiegazione. La sequenza è determinata dal seme: note, esercizi e codice possono ottenere esattamente gli stessi risultati, e i confronti fra metodi usano le stesse partenze.
Nel TSP con distanze euclidee (città nel piano), che cosa si può dire di un giro che è un ottimo locale per l'intorno 2-opt?
Ha tutti i lati di lunghezza uguale
Non ha lati che si incrociano
Contiene il lato più corto dell'istanza
È sempre il giro ottimo
Spiegazione. Se due lati si incrociano, la disuguaglianza triangolare mostra che la mossa 2-opt che li scioglie accorcia il giro; quindi in un ottimo locale non ci sono incroci, ma il giro può non essere ottimo.
Nel TSP, la mossa Or-opt sposta un breve tratto di città consecutive in un altro punto del giro, senza invertirlo. Quale affermazione sui due intorni 2-opt e Or-opt è corretta?
Un ottimo locale per 2-opt può non esserlo per Or-opt, e viceversa
Ogni ottimo locale per 2-opt è anche ottimo locale per Or-opt
Or-opt contiene tutte le mosse 2-opt
I due intorni hanno lo stesso numero di mosse
Spiegazione. Le due mosse cambiano lati diversi (due per 2-opt, tre per Or-opt) e contengono mosse diverse: combinarle, per esempio in una discesa a intorni variabili, migliora i risultati.
La discesa a intorni variabili ($VND$) usa gli intorni $N_1,\dots,N_K$, ordinati dal più piccolo al più grande. Come procede?
Esegue una ricerca locale completa in ogni $N_k$, una sola volta, in ordine
Sceglie a caso un intorno a ogni iterazione
Usa solo l'intorno $N_K$, il più grande, perché contiene gli altri
Cerca un vicino migliore in $N_1$, poi in $N_2$ e così via; dopo ogni miglioramento torna a $N_1$; si ferma quando nessun $N_k$ migliora
Spiegazione. Gli intorni costosi si esplorano solo quando quelli economici sono esauriti; $VND$ è deterministica e termina per lo stesso argomento della ricerca locale.
Quando la discesa a intorni variabili ($VND$) con intorni $N_1,\dots,N_K$ si ferma, che cosa si sa della soluzione restituita?
È la migliore soluzione di $N_1$ partendo dalla soluzione iniziale
È un ottimo globale, perché ha provato tutti gli intorni
È un ottimo locale rispetto a ciascuno degli intorni $N_1,\dots,N_K$
È un ottimo locale solo rispetto all'ultimo intorno $N_K$
Spiegazione. L'ultima esplorazione di ogni intorno non ha trovato miglioramenti e la soluzione non è più cambiata: è un ottimo locale per tutti. Un ottimo globale lo sarebbe per ogni intorno, ma non vale il contrario.
Una ricerca locale con intorno $N$ parte da una soluzione ammissibile e si sposta su un vicino migliore finché ne trova uno. Che cosa garantisce la soluzione finale?
È un bound duale
È un ottimo locale rispetto a $N$: nessun vicino in $N$ è migliore
È una soluzione ottima del problema
È migliore di ogni altra soluzione ottenibile con lo stesso intorno
Spiegazione. Un ottimo locale può essere molto peggiore dell'ottimo globale; con intorni più grandi gli ottimi locali sono migliori ma costano di più.
Nella ricerca locale gli intorni sono definiti da piccole modifiche della rappresentazione delle soluzioni. Che cosa succede a una modifica che produce una soluzione non ammissibile (senza penalità)?
Non appartiene all'intorno: si considerano solo i vicini ammissibili
Si accetta e si ripara alla fine
Si accetta solo se migliora l'obiettivo
Diventa la nuova soluzione corrente
Spiegazione. Nelle ricerche locali di base l'intorno contiene solo vicini ammissibili; l'alternativa è ammettere soluzioni non ammissibili con una penalità nell'obiettivo.
Nella ricerca locale per lo zaino 0/1 con $n=10$ oggetti, la soluzione corrente seleziona $|S|=4$ oggetti. Quanti elementi hanno, prima del test di capacità, l'intorno flip (aggiunge o toglie un oggetto) e l'intorno swap (toglie un selezionato e aggiunge un non selezionato)?
Flip $4$, swap $6$
Flip $6$, swap $24$
Flip $10$, swap $45$
Flip $10$, swap $24$
Spiegazione. Flip: un elemento per oggetto, $n=10$. Swap: $|S|(n-|S|)=4\cdot6=24$. $45=\binom{10}2$ conterebbe anche coppie di oggetti entrambi selezionati.
Nell'intorno move del bin packing un oggetto si sposta in un altro contenitore non vuoto in cui entra; gli spostamenti verso un contenitore vuoto non sono ammessi. Perché questa restrizione non fa perdere mosse utili?
Perché i contenitori vuoti hanno capacità minore
Perché uno spostamento in un contenitore vuoto è sempre inammissibile
Spostare un oggetto in un contenitore vuoto non può diminuire il numero di contenitori
Perché il numero di contenitori non cambia mai con una move
Spiegazione. La mossa aprirebbe un contenitore: nel caso migliore ne svuota un altro, lasciando il numero invariato. Una move utile deve svuotare un contenitore senza aprirne.
Per $P\,||\,C_{\max}$ con $n=7$ lavori e $m=3$ macchine, quanti elementi ha l'intorno move (un lavoro passa a un'altra macchina), e perché lo swap considera solo coppie di lavori con durate diverse?
$7$; ogni lavoro ha una sola mossa
$14$; scambiare due lavori di uguale durata non cambia alcun carico
$21$; scambiare due lavori di uguale durata è inammissibile
$14$; gli swap con durate uguali peggiorano sempre
Spiegazione. Move: $n(m-1)=7\cdot2=14$, tutte ammissibili. Uno swap con $t_j=t_k$ lascia invariati i carichi, quindi non serve esaminarlo.
Problema di minimo, soluzione corrente di valore $20$. I suoi vicini, nell'ordine fissato di esame, valgono $22$, $18$, $15$, $19$. Quale vicino sceglie la regola first improvement e quale la best improvement?
First: quello di valore $18$; best: quello di valore $15$
First: $22$; best: $15$
First: $15$; best: $15$
First: $18$; best: $18$
Spiegazione. First improvement prende il primo vicino migliore di $20$ nell'ordine ($18$); best improvement esamina tutti e prende il migliore ($15$).
Nella ricerca locale, la regola best improvement esamina tutto l'intorno a ogni iterazione. Che cosa si può dire in generale rispetto a first improvement?
First improvement esegue sempre meno iterazioni
Le due regole arrivano sempre allo stesso ottimo locale
Best improvement trova sempre l'ottimo globale
Ogni iterazione costa di più; nessuna delle due regole garantisce un ottimo locale migliore dell'altra
Spiegazione. Le due regole seguono cammini diversi e possono fermarsi in ottimi locali diversi; best improvement fa passi più grandi ma più costosi.
Una mossa 2-opt nel TSP toglie due lati non adiacenti $\{a,b\}$ e $\{c,d\}$ del giro $(\dots,a,b,\dots,c,d,\dots)$ e li sostituisce con $\{a,c\}$ e $\{b,d\}$, invertendo il tratto da $b$ a $c$. Di quanto cambia la lunghezza?
$d_{ab}+d_{cd}-d_{ac}-d_{bd}$
$d_{ac}+d_{bd}$
$d_{ac}+d_{bd}-d_{ab}-d_{cd}$
$d_{ad}+d_{bc}-d_{ab}-d_{cd}$
Spiegazione. Si aggiungono i due lati nuovi e si tolgono i due vecchi; con distanze simmetriche il tratto invertito ha la stessa lunghezza. La mossa migliora se la variazione è negativa.
Un'istanza del TSP con $10$ città ha giro ottimo di lunghezza $39$, e il nearest neighbour dalla città $1$ trova un giro di lunghezza $49$. Quanti giri distinti ha l'istanza, e quale gap relativo ha il giro iniziale?
$2^{10}$ giri; gap $10\%$
$9!/2=181\,440$ giri; gap $\frac{49-39}{39}\approx25.6\%$
$10!=3\,628\,800$ giri; gap $\approx25.6\%$
$9!/2$ giri; gap $\frac{49-39}{49}\approx20.4\%$
Spiegazione. $(n-1)!/2$ con $n=10$. Il gap rispetto all'ottimo si misura dividendo per $z(I)=39$; la ricerca locale 2-opt parte da qui per ridurlo.
Nel TSP, la sequenza di intorni 2-opt, 3-opt, $k$-opt (Lin–Kernighan) illustra un compromesso generale della ricerca locale. Quale?
Un intorno più grande ha ottimi locali migliori ma costa di più da esplorare (3-opt: $O(n^3)$ per iterazione)
Un intorno più grande ha ottimi locali peggiori
Gli intorni più grandi sono sempre più veloci
Lin–Kernighan garantisce l'ottimo globale
Spiegazione. Lin–Kernighan costruisce un numero variabile di scambi in modo greedy e si ferma quando non conviene più: ottiene ottimi locali molto buoni a un costo ragionevole.
In $P\,||\,C_{\max}$ uno swap scambia il lavoro $j$ (durata $7$, sulla macchina $a$) con il lavoro $k$ (durata $4$, sulla macchina $b$). Come cambiano i carichi $L_a$ e $L_b$?
$L_a+3$ e $L_b-3$
Non cambiano: uno swap non modifica i carichi
$L_a-7$ e $L_b+4$
Si trasferisce $\delta=3$ dalla macchina $a$ alla macchina $b$: $L_a-3$, $L_b+3$
Spiegazione. $L_a$ perde $7$ e guadagna $4$, $L_b$ il contrario: uno swap trasferisce $t_j-t_k$, una move trasferisce $t_j$.
Nella ricerca locale per il bin packing, l'obiettivo «numero di contenitori» cambia raramente con una move o uno swap. Perché si usa l'obiettivo ausiliario $SQ=\sum_bL_b^2$ ($L_b$ = carico del contenitore $b$)?
Perché $SQ$ è uguale al numero di contenitori
Perché $SQ$ diminuisce quando i carichi diventano più uguali
Il paesaggio del numero di contenitori è piatto; $SQ$ premia le mosse che concentrano il carico, preparando lo svuotamento di un contenitore
Perché $SQ$ è un bound duale
Spiegazione. Con carico totale fisso, $\sum_bL_b^2$ è più grande quando i carichi sono sbilanciati: aumentarlo svuota progressivamente i contenitori meno carichi.
Nella ricerca locale move per il bin packing con obiettivo $SQ=\sum_bL_b^2$ (da massimizzare), spostare l'oggetto $j$ di peso $w_j$ dal contenitore $a$ al contenitore $b$ cambia $SQ$ di $2w_j(L_b-L_a+w_j)$. Con $w_j=3$, $L_a=5$, $L_b=6$ (capacità $10$), la mossa è migliorante?
Sì, ma la variazione è $6$
Sì: la variazione è $2\cdot3\cdot(6-5+3)=24>0$
No: la variazione è $2\cdot3\cdot(6-5-3)=-12$
No: il contenitore $b$ supera la capacità
Spiegazione. $L_b+w_j=9\le10$, quindi la mossa è ammissibile, e sposta peso verso il contenitore più carico: $SQ$ aumenta di $24$.
La ricerca locale swap per il bin packing scambia due oggetti di peso diverso in contenitori diversi, se entrambi i contenitori restano ammissibili. Perché non si scambiano oggetti di peso uguale, e che effetto ha uno swap sul numero di contenitori?
Lo swap di pesi uguali non cambia alcun carico; uno swap non cambia mai il numero di contenitori
Lo swap di pesi uguali è inammissibile; uno swap può svuotare un contenitore
Lo swap di pesi uguali aumenta $SQ$; uno swap riduce sempre i contenitori
Nessuna ragione; uno swap aumenta sempre i contenitori
Spiegazione. Ogni contenitore cede un oggetto e ne riceve uno, quindi nessuno si svuota: lo swap serve a cambiare i carichi, e solo l'obiettivo ausiliario $SQ$ ne vede il beneficio.
Per il bin packing con obiettivo ausiliario $SQ=\sum_bL_b^2$, una move dell'oggetto $j$ dal contenitore $a$ al contenitore non vuoto $b$ cambia $SQ$ di $2w_j(L_b-L_a+w_j)$. Perché una move che svuota il contenitore $a$ aumenta sempre $SQ$?
Perché svuotare un contenitore diminuisce $\sum_bL_b$
Non è vero: può diminuire $SQ$
Perché $L_b>L_a$ in ogni mossa
Svuotare $a$ significa $L_a=w_j$, quindi la variazione è $2w_jL_b>0$
Spiegazione. Con $L_a=w_j$ il termine diventa $2w_j(L_b-w_j+w_j)=2w_jL_b$, positivo perché $b$ non è vuoto. Quindi ogni mossa che riduce il numero di contenitori migliora anche $SQ$.
Per $P\,||\,C_{\max}$ si usa l'obiettivo ausiliario $\sum_hL_h^2$ (da minimizzare) con move e swap. Quale relazione con il makespan vale?
Una mossa che diminuisce $\sum_hL_h^2$ diminuisce sempre il makespan
Le due funzioni sono indipendenti
Una mossa che diminuisce il makespan diminuisce $\sum_hL_h^2$, e una che diminuisce $\sum_hL_h^2$ non aumenta il makespan
Una mossa che diminuisce il makespan aumenta $\sum_hL_h^2$
Spiegazione. Trasferire carico dalla macchina più carica a una meno carica riduce la somma dei quadrati; l'ausiliario vede anche le mosse neutre per il makespan che bilanciano le altre macchine.
Bin packing con $c=7$: una soluzione ha quattro contenitori con carichi $(7,6,5,3)$. Quanto vale l'obiettivo ausiliario $SQ=\sum_bL_b^2$, e quanto varrebbe con gli stessi pesi in carichi $(7,7,7)$?
$441$ e $147$
$119$ e $147$
$21$ e $21$
$119$ e $119$
Spiegazione. $49+36+25+9=119$; con tre contenitori pieni $3\cdot49=147$. Il numero totale di peso ($21$) non cambia, ma $SQ$ cresce quando i carichi si concentrano.
Nella ricerca locale per lo zaino 0/1, i vettori binari che superano la capacità si possono escludere oppure ammettere con una penalità. Che cosa massimizza la seconda strategia?
Il profitto meno una penalità proporzionale al peso in eccesso sulla capacità
Il profitto, ignorando la capacità
Il peso totale
Il profitto diviso per il peso
Spiegazione. La funzione è $\sum_jp_jx_j-\alpha\max\{0,\sum_jw_jx_j-c\}$: lo spazio di ricerca diventa tutto $\{0,1\}^n$, e la ricerca può attraversare la regione non ammissibile.
Nella ricerca locale flip+swap per lo zaino 0/1 che resta ammissibile, con la regola first improvement, quali flip possono essere miglioranti?
Tutti i flip
Nessun flip: solo gli swap migliorano
Solo quelli che tolgono un oggetto
Solo quelli che aggiungono un oggetto (che entra nella capacità residua)
Spiegazione. Con profitti positivi togliere un oggetto peggiora sempre; un flip che aggiunge migliora se l'oggetto entra. Se ne esiste uno, gli swap non vengono esaminati.
Nella ricerca locale penalizzata per lo zaino 0/1 si massimizza $g_\alpha(x)=\sum_jp_jx_j-\alpha\max\{0,\sum_jw_jx_j-c\}$, con dati interi. Perché, con $\alpha>\max_jp_j$, da un vettore ammissibile nessun flip verso un vettore non ammissibile aumenta $g_\alpha$?
Perché la penalità vale $0$ sui vettori non ammissibili
Perché con $\alpha$ grande nessun oggetto entra
Aggiungere l'oggetto $k$ crea un eccesso $e\ge1$, e la variazione $p_k-\alpha e$ è negativa
Perché $\alpha$ deve essere minore di $\min_jp_j$
Spiegazione. Con dati interi l'eccesso è almeno $1$, quindi $p_k-\alpha e\le p_k-\alpha<0$. Con $\alpha$ piccolo invece la ricerca può fermarsi in un vettore non ammissibile.
Una ricerca locale si ferma in un ottimo locale di valore $478$ su un'istanza del TSP. Che cosa si sa del valore ottimo, senza altre informazioni?
Che è al più $478/2$
Solo che è al più $478$: la ricerca locale dà un bound primale, non un bound duale
Che è esattamente $478$, perché la ricerca si è fermata
Che è almeno $478$
Spiegazione. L'ottimo locale è una soluzione ammissibile, cioè un lato del gap. Per sapere che $478$ è ottimo serve un bound duale, per esempio da un solutore MIP.
La variazione di una mossa 2-opt nel TSP si calcola con i soli quattro lati coinvolti, $d_{ac}+d_{bd}-d_{ab}-d_{cd}$, anche se il tratto fra $b$ e $c$ viene percorso al contrario. Quale ipotesi lo permette?
Le distanze sono simmetriche: invertire il tratto non ne cambia la lunghezza
I lati tolti sono adiacenti
Le distanze soddisfano la disuguaglianza triangolare
Il giro ha un numero pari di città
Spiegazione. Nel TSP asimmetrico il tratto invertito cambierebbe lunghezza, e la variazione richiederebbe di sommare tutti gli archi del tratto: per questo nell'ATSP si preferiscono mosse che non invertono (come Or-opt).
La ricerca locale del capitolo è illustrata su quattro problemi: zaino 0/1 (KP), bin packing (BPP), TSP e $P\,||\,C_{\max}$. Quale di essi è un problema di massimo?
Il BPP
Il TSP
$P\,||\,C_{\max}$
Il KP: si massimizza il profitto
Spiegazione. BPP (numero di contenitori), TSP (lunghezza del giro) e $P\,||\,C_{\max}$ (makespan) sono di minimo: «migliore» significa valore più piccolo.
Una ricerca locale ha bisogno di una soluzione ammissibile di partenza. Da dove viene di solito?
Dal rilassamento lineare, senza arrotondamento
Da un bound duale
Da un'euristica costruttiva (greedy per efficienza, First Fit, nearest neighbour, LPT) o da una soluzione casuale ammissibile
Da una soluzione ottima
Spiegazione. La qualità e la diversità delle soluzioni di partenza influenzano l'ottimo locale raggiunto; il multi-start ripete la ricerca da molte partenze.
In un esperimento di ricerca locale su $P\,||\,C_{\max}$ con $m=4$ macchine e tempi $t=(11,10,9,8,7,7,6,5,4,4,3,2)$, il valore ottimo è $19$. Quale lower bound semplice lo certifica?
$\max_jt_j=11$
$\lceil\sum_jt_j/m\rceil=\lceil76/4\rceil=19$
$\sum_jt_j=76$
$\lceil76/12\rceil=7$
Spiegazione. La somma dei tempi è $76$: una soluzione con makespan $19$ uguaglia il bound della media dei carichi ed è quindi ottima.
Un giro del TSP simmetrico lungo $40$; una mossa 2-opt toglie i lati $\{u_1,v_1\}$ e $\{u_2,v_2\}$, con $d_{u_1v_1}=7$ e $d_{u_2v_2}=9$, e aggiunge $\{u_1,u_2\}$ e $\{v_1,v_2\}$, con $d_{u_1u_2}=4$ e $d_{v_1v_2}=5$. Quanto è lungo il giro nuovo?
$47$
$25$
$40$
$33$
Spiegazione. $\Delta=d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}=4+5-7-9=-7$, quindi $40-7=33$. Il tratto fra $v_1$ e $u_2$ si percorre al contrario ma, con distanze simmetriche, ha la stessa lunghezza.
Due carichi $L_a=10$ e $L_b=6$; si sposta la quantità $\delta=3$ da $a$ a $b$. Come cambia la somma dei quadrati dei carichi?
Diminuisce di $24$
Non cambia
Diminuisce di $6$
Aumenta di $6$
Spiegazione. La variazione è $2\delta(L_b-L_a+\delta)=2\cdot3\cdot(6-10+3)=-6$: infatti $7^2+9^2=130$ e $10^2+6^2=136$. La somma dei carichi non cambia, quella dei quadrati sì.
Ricerca locale per lo zaino 0/1 (problema di massimo, profitti interi) che si sposta solo su vicini strettamente migliori: parte da una soluzione di profitto $9$ e il valore ottimo è $17$. Quante mosse fa al più?
$2^n$
$8$
$17$
Esattamente $8$
Spiegazione. Ogni mossa aumenta il profitto di almeno $1$ e il profitto non supera $z(I)=17$: al più $z(I)-f(x^0)=8$ mosse. Può farne meno, fermandosi in un ottimo locale non globale.
La variable neighbourhood descent usa gli intorni $N_1,\dots,N_k$: torna a $N_1$ dopo ogni miglioramento e passa all'intorno successivo quando quello corrente non migliora. Dove si ferma?
In un ottimo locale per tutti i $k$ intorni
In un ottimo locale per il solo intorno $N_k$
In una soluzione ottima dell'istanza
Dopo esattamente $k$ mosse
Spiegazione. Si ferma quando nessuno dei $k$ intorni contiene un vicino migliore: è un ottimo locale per ciascuno. Non è per forza ottimo globale, e il numero di mosse non è fissato.
Perché una ricerca locale che si sposta solo su vicini strettamente migliori termina per ogni soluzione di partenza, anche senza obiettivo intero?
L'intorno usato dalla ricerca è esatto
La regola di scelta è first improvement
La funzione obiettivo è convessa
Le soluzioni sono finite e $f$ migliora sempre
Spiegazione. Una soluzione non si visita due volte (il valore migliora strettamente) e le soluzioni sono finite. L'obiettivo intero serve solo al bound $f(x^0)-z(I)$ sul numero di mosse.
La ricerca locale multi-start ripete la ricerca da più soluzioni di partenza. Perché le partenze devono essere diverse (per esempio casuali)?
L'intorno cambia con la soluzione di partenza
Partenze diverse servono a calcolare il gap
Dalla stessa partenza si arriva allo stesso ottimo
Altrimenti la ricerca locale non termina
Spiegazione. Con una regola di scelta deterministica la ricerca locale da una partenza fissata arriva sempre allo stesso ottimo locale: ripeterla non serve. Partenze diverse esplorano valli diverse.
Perché la ricerca locale per il bin packing ha bisogno di un obiettivo ausiliario come $\sum_bL_b^2$?
$\sum_bL_b^2$ è uguale al numero di contenitori usati
Quasi ogni mossa lascia invariato il numero di contenitori
Il numero di contenitori non è un valore intero
Le mosse rendono spesso le soluzioni non ammissibili
Spiegazione. Il paesaggio del numero di contenitori è piatto: quasi ogni vicino ha lo stesso valore e la ricerca si ferma subito. $\sum_bL_b^2$ premia i contenitori pieni e guida verso lo svuotamento di uno.
Per $P\,||\,C_{\max}$ si usa l'intorno swap (scambio di due lavori su macchine diverse) oltre a move. In quale situazione serve?
Se ogni move sovraccarica la macchina che riceve
Se le macchine sono più numerose dei lavori
Se tutti i lavori hanno lo stesso tempo di esecuzione
Se il makespan è già uguale al bound inferiore
Spiegazione. Una soluzione può essere un ottimo locale per move (ogni spostamento crea un carico più alto) ma non per swap, che sposta lavori in tutte e due le direzioni: è il caso della soluzione di $LPT$.
Nel simulated annealing per un problema di minimo si usa la regola di Metropolis. Alla temperatura $T=3$ si propone un vicino che peggiora l'obiettivo di $\delta=6$. Con quale probabilità è accettato?
$1$
$e^{-1/2}$
$e^{-2}$
$e^{2}$
Spiegazione. Regola di Metropolis: un peggioramento $\delta>0$ è accettato con probabilità $e^{-\delta/T}=e^{-6/3}=e^{-2}\approx 0{,}14$; un miglioramento è sempre accettato.
La tabu search è una metaeuristica di ricerca locale con una lista tabu di mosse vietate per un certo numero di iterazioni (la durata tabu). Quale affermazione è corretta?
Va sul miglior vicino non tabu solo se migliore; una mossa tabu non è mai ammessa, neanche se batte la migliore
Va sul miglior vicino non tabu anche se peggiore; una mossa tabu è ammessa se batte la migliore soluzione trovata
Va su un vicino casuale, accettato con probabilità $e^{-\delta/T}$; la lista tabu vieta per sempre le soluzioni visitate
Va sul miglior vicino in assoluto; la lista tabu serve solo a fermare l'algoritmo quando è piena
Spiegazione. La lista tabu è una memoria a breve termine: le mosse che disfano le mosse recenti sono vietate per un numero di iterazioni (la durata tabu). Con durata $0$ la tabu search si riduce a una ricerca locale.
Le metaeuristiche (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, algoritmi genetici) esplorano lo spazio delle soluzioni ammissibili. Che tipo di bound producono?
Solo bound primali: non sanno quanto sono lontane dall'ottimo
Il valore ottimo, se eseguite abbastanza a lungo
Solo bound duali: ogni soluzione trovata limita l'ottimo
Bound primali e duali, il cui gap si chiude col tempo
Spiegazione. Le metaeuristiche costruiscono soluzioni ammissibili; per misurarne la qualità serve un bound duale da un'altra fonte (rilassamento, algoritmo esatto).
GRASP (Greedy Randomized Adaptive Search Procedure) è una metaeuristica multi-start. Che cosa fa a ogni iterazione?
Perturba l'ottimo locale corrente con un kick casuale e riapplica la ricerca locale alla soluzione perturbata
Distrugge una parte della soluzione corrente, la ripara con un'euristica e accetta il risultato se è migliore
Seleziona due genitori dalla popolazione, li ricombina e muta il figlio, che sostituisce l'individuo peggiore
Costruisce una soluzione con un greedy randomizzato sulla lista ristretta dei candidati e la migliora con una ricerca locale
Spiegazione. GRASP è un metodo multi-start: costruzione randomizzata più ricerca locale, e alla fine la migliore soluzione trovata. Il kick è di ILS, distruggi e ripara è di LNS, la ricombinazione degli algoritmi genetici.
Una metaeuristica guida una ricerca locale oltre il primo ottimo locale. In quali modi ne esce?
Risolve il rilassamento lineare e arrotonda la soluzione trovata
Ordina gli elementi e li aggiunge uno alla volta alla soluzione
Accetta soluzioni peggiori, salta a una nuova partenza o combina soluzioni
Riduce l'intorno, si ferma prima o rilassa i vincoli del problema
Spiegazione. Accettare peggioramenti (simulated annealing, tabu search), saltare (ILS, VNS, GRASP, LNS), combinare (algoritmi genetici). Le ultime due opzioni descrivono un'euristica PLI e una costruttiva.
Che cosa deve bilanciare ogni metaeuristica (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, algoritmi genetici)?
Bound primali e bound duali
Intensificazione e diversificazione
Ammissibilità e ottimalità
Tempo di costruzione e memoria
Spiegazione. Scendere fino al fondo della valle corrente (intensificare) e lasciarla per un'altra (diversificare); ogni metodo ha parametri che fissano l'equilibrio.
Una metaeuristica è una strategia che guida una ricerca locale oltre il primo ottimo locale. Quale dei seguenti metodi NON è una metaeuristica in questo senso?
Una discesa best improvement che si ferma al primo ottimo locale
La GRASP con costruzione randomizzata e ricerca locale
Il simulated annealing con l'intorno 2-opt per il TSP
La tabu search con l'intorno move per $P\,||\,C_{\max}$
Spiegazione. La discesa si ferma proprio dove una metaeuristica comincia a lavorare; gli altri tre metodi escono dagli ottimi locali.
Per $P\,||\,C_{\max}$ le metaeuristiche confrontano due soluzioni in modo lessicografico: prima il makespan $C_{\max}$, a parità la somma $\sum_hL_h^2$ dei carichi al quadrato. Tre soluzioni hanno $(C_{\max},\sum_hL_h^2)$: $A=(11,249)$, $B=(11,267)$, $C=(12,245)$. Qual è l'ordine dalla migliore?
$C$, $A$, $B$
$A$, $B$, $C$
$A$, $C$, $B$
$B$, $A$, $C$
Spiegazione. $C$ ha il makespan peggiore e viene ultima, anche se ha la somma minore; fra $A$ e $B$, a parità di makespan, vince la somma minore.
Nelle metaeuristiche un elemento casuale di una lista di $K$ elementi è quello in posizione $1+\lfloor u\cdot K\rfloor$, dove $u\in(0,1)$ è il numero casuale. Con $K=5$ e $u=0.7556$, quale posizione si sceglie?
$3$
$5$
$1$
$4$
Spiegazione. $\lfloor0.7556\cdot5\rfloor=\lfloor3.778\rfloor=3$, più $1$: posizione $4$. Senza il $+1$ si otterrebbe $3$.
Con il generatore di Park e Miller ($seed\leftarrow16807\,seed\,\mathrm{mod}\,(2^{31}-1)$, $u=seed/(2^{31}-1)$) e $seed=1$, il primo numero è $u\approx0.0000078$. È un errore?
Sì: il primo numero va sempre scartato
No, ma i numeri successivi sono tutti vicini a $0$
No: con un seme piccolo il primo numero è sempre vicino a $0$
Sì: il generatore va inizializzato con un seme grande
Spiegazione. $16807/(2^{31}-1)$ è piccolo per costruzione; i numeri successivi ($0.1315$, $0.7556$, …) sono distribuiti normalmente nell'intervallo.
Quale metaeuristica esce da un ottimo locale accettando mosse peggioranti in modo deterministico, con una memoria che vieta di tornare alle soluzioni appena visitate?
Il simulated annealing
La tabu search
L'iterated local search
La GRASP
Spiegazione. Il simulated annealing accetta i peggioramenti a caso; ILS e GRASP saltano a nuove partenze.
Fra le metaeuristiche, quali mantengono una sola soluzione corrente e cambiano la regola di accettazione, quali saltano a nuovi punti di partenza, e quale lavora con molte soluzioni?
SA e TS; ILS, VNS, GRASP e LNS; gli algoritmi genetici
TS e LNS; SA, ILS, VNS e GRASP; gli algoritmi genetici
ILS e VNS; SA, TS, GRASP e LNS; gli algoritmi genetici
SA e GRASP; TS, ILS, VNS e LNS; gli algoritmi genetici
Spiegazione. Simulated annealing e tabu search passano per soluzioni peggiori; ILS, VNS, GRASP e LNS generano un nuovo punto di partenza; gli algoritmi genetici mantengono una popolazione.
Perché il simulated annealing (vicino casuale, accettato se migliore o, se peggiore, con una probabilità che dipende dalla temperatura) memorizza a parte la migliore soluzione visitata?
Per poter ripartire da capo a ogni nuova temperatura
Perché la temperatura finale è sempre troppo alta
Lascia gli ottimi locali: la soluzione finale può essere peggiore
Perché la soluzione corrente è sempre inammissibile
Spiegazione. Un ottimo locale viene lasciato appena una mossa peggiorante è accettata, quindi la migliore soluzione può essere stata visitata molto prima della fine.
Nel simulated annealing per un problema di minimo, un vicino con peggioramento $\delta$ è accettato con probabilità $1$ se $\delta\le0$ ed $e^{-\delta/T}$ se $\delta>0$. Che cosa succede alle mosse con $\delta=0$?
Sono accettate con probabilità $\frac12$, a caso
Sono sempre accettate: la ricerca si muove sui plateau
Non sono mai accettate, a nessuna temperatura
Sono accettate soltanto con probabilità $e^{-1/T}$
Spiegazione. $\delta=0$ ricade nel primo caso: probabilità $1$. È ciò che permette al simulated annealing di attraversare i plateau degli obiettivi piatti.
Simulated annealing con schema geometrico $T\leftarrow\alpha T$, $L$ mosse per temperatura, e arresto quando $T\le T_{\min}$. Con $T_0=10$, $\alpha=0.5$, $T_{\min}=1$ e $L=4$, quante iterazioni esegue?
$16$
$40$
$12$
$20$
Spiegazione. Temperature $10$, $5$, $2.5$, $1.25$; la successiva, $0.625\le1$, ferma la ricerca: $4$ temperature per $4$ mosse.
Nel simulated annealing una regola per la temperatura iniziale pone $T_0=-\bar\delta/\mathrm{ln}\,\chi_0$, dove $\bar\delta$ è il peggioramento medio di mosse casuali e $\chi_0$ il tasso di accettazione iniziale voluto. Con $\bar\delta=10$ e $\chi_0=0.8$, quanto vale $T_0$ circa?
$8$
$12.5$
$2.2$
$44.8$
Spiegazione. $\mathrm{ln}\,0.8\approx-0.223$, quindi $T_0\approx10/0.223\approx44.8$, e $e^{-10/44.8}\approx0.8$.
Simulated annealing con l'intorno 2-opt sul TSP a $5$ città (ottimo $18$), temperature $5$, $4$, $3.2$: alle iterazioni $1$ e $3$ accetta giri peggiori ($25\to29$, $22\to24$), alle iterazioni $5$ e $6$, a temperatura più bassa, rifiuta due peggioramenti, e restituisce $18$. Che cosa mostra?
A bassa temperatura si accetta ogni mossa
Il giro restituito è l'ultimo visitato, non il migliore
Il meccanismo: peggioramenti accettati presto, rifiutati poi
Il simulated annealing peggiora sempre la soluzione
Spiegazione. La probabilità $e^{-\delta/T}$ cala con $T$; si restituisce il miglior giro visitato. Su questa istanza anche il 2-opt troverebbe l'ottimo: l'esempio mostra il meccanismo.
Simulated annealing con penalità sullo zaino ($c=9$, ottimo $(1,1,0,0)$ di profitto $17$): da $(1,0,1,0)$, ottimo locale per i flip ammissibili, passa alla soluzione inammissibile $(1,1,1,0)$ (peso $12$) e poi, togliendo l'oggetto $3$, arriva all'ottimo. Che cosa mostra?
Le soluzioni inammissibili vanno sempre scartate
La regione inammissibile fa da ponte fra due valli
La penalità rende ammissibile ogni vettore
L'ottimo si trova solo con flip ammissibili
Spiegazione. Con soli flip ammissibili $(1,0,1,0)$ è bloccata; con la penalità la ricerca attraversa un vettore inammissibile e raggiunge un'altra valle.
Nel simulated annealing con penalità per lo zaino si massimizza $f_\beta(x)=\sum_jp_jx_j-\beta\max\{0,\sum_jw_jx_j-c\}$ su tutti gli $x\in\{0,1\}^n$. Quali soluzioni possono aggiornare la migliore soluzione memorizzata?
Solo quelle ammissibili
Solo quelle accettate alla temperatura minima
Qualunque soluzione con $f_\beta$ maggiore
Solo quelle con eccesso di peso al più $1$
Spiegazione. La ricerca può visitare vettori inammissibili, ma la soluzione restituita deve essere ammissibile: la migliore si aggiorna solo con quelle.
Simulated annealing su un TSP a $20$ città (ottimo $291$), $10$ esecuzioni per parametri: con $\alpha=0.9$ e $T_0=1$ ($700$ iterazioni) l'ottimo si trova $1$ volta; con $\alpha=0.99$ e $T_0=20$ ($36\,800$ iterazioni) $10$ volte. Che cosa mostra la tabella?
Una temperatura iniziale bassa dà sempre i risultati migliori
Il numero di iterazioni non influisce sul risultato
Basta una sola esecuzione per confrontare i parametri
Raffreddare lentamente aiuta, ma costa molte più iterazioni
Spiegazione. Con $T_0=1$ si accettano pochi peggioramenti e si ha quasi una ricerca locale; con $\alpha$ vicino a $1$ si passano più iterazioni a ogni temperatura. I parametri scambiano qualità con tempo.
A temperatura fissata il simulated annealing è una catena di Markov. Sotto quali ipotesi ha come unica distribuzione stazionaria la distribuzione di Boltzmann $\pi_T(S)\propto e^{-f(S)/T}$?
Obiettivo a valori interi e positivi
Intorno esatto e di dimensione costante
Intorno simmetrico e connesso
Schema di raffreddamento geometrico
Spiegazione. Simmetrico ($S'\in N(S)$ se e solo se $S\in N(S')$, intorni della stessa dimensione) e connesso (ogni soluzione raggiunge ogni altra). Lo schema di raffreddamento non c'entra: la temperatura è fissata.
Hajek (1988) ha dimostrato che il simulated annealing con lo schema logaritmico $T_k=\Gamma/\mathrm{ln}\,(k+1)$ ($\Gamma$ abbastanza grande) porta la probabilità di trovarsi in una soluzione ottima a $1$. Perché in pratica si usa lo schema geometrico?
Perché lo schema logaritmico vale solo per il TSP
È una garanzia al limite: le iterazioni necessarie sono troppe
Perché lo schema geometrico ha la stessa garanzia
Perché lo schema logaritmico non converge mai
Spiegazione. Le iterazioni richieste possono superare il numero di soluzioni; lo schema geometrico è molto più veloce, ma senza garanzie.
Tabu search per $P\,||\,C_{\max}$ (intorno move, confronto lessicografico, durata tabu $6$) dalla soluzione di $LPT$ con carichi $(11,8,8)$: all'iterazione $5$ i vicini con makespan $11$ sono tutti tabu, e la ricerca si sposta su un vicino con makespan $12$; all'iterazione $8$ arriva a $(9,9,9)$. Che cosa mostra?
Una mossa peggiorante non tabu fa lasciare il plateau
Il makespan $12$ è il valore restituito
La tabu search non accetta mai mosse peggioranti
La lista tabu impedisce di raggiungere l'ottimo
Spiegazione. Una ricerca locale si fermerebbe sul plateau di makespan $11$; la tabu search va sul miglior vicino non tabu anche se peggiore, e poi scende a $10$ e a $9=\mathrm{LB}$.
Nella tabu search per il TSP con l'intorno 2-opt, quali sono gli attributi tabu?
Le due città appena spostate, che restano ferme per sempre
I giri già visitati, memorizzati per intero
I lati appena aggiunti, che non si possono togliere
I due lati appena tolti, che non possono rientrare per un po'
Spiegazione. Per $tenure$ iterazioni i lati tolti non possono essere rimessi nel giro, a meno che la mossa dia un giro più corto del migliore (aspirazione).
Tabu search sulle istanze medie: sul TSP a $20$ città basta una durata tabu $1$ per arrivare all'ottimo ($0$ resta a $319$), su $P\,||\,C_{\max}$ con $15$ lavori serve una durata $15$ (con $20$ o più l'ottimo si perde di nuovo). Che cosa mostrano i risultati?
La durata tabu non influisce sul risultato
Senza memoria la tabu search trova sempre l'ottimo
La durata tabu va calibrata su problema e istanza
Una durata tabu lunga è sempre la scelta migliore
Spiegazione. Con durata $0$ la ricerca cicla; sul plateau di $P\,||\,C_{\max}$ serve una lista lunga, ma una lista troppo lunga vieta troppo.
L'iterated local search ha tre componenti: ricerca locale, perturbazione (kick) e criterio di accettazione. Che ruolo ha ciascuna?
Diversifica; intensifica; bilancia le due
Intensifica; diversifica; bilancia le due
Bilancia; intensifica; diversifica
Intensifica; bilancia; diversifica
Spiegazione. La ricerca locale porta al fondo della valle, il kick sposta in un'altra valle, l'accettazione (solo ottimi migliori o anche peggiori) decide l'equilibrio.
Iterated local search su un TSP a $20$ città (ottimo $291$): dall'ottimo locale 2-opt di lunghezza $319$, il primo kick double bridge dà un giro lungo $432$, che la ricerca 2-opt porta a $303$ (accettato); il secondo kick porta a $291$. Che cosa mostra?
Il kick peggiora, ma la discesa ripara e conserva il buono
L'ILS accetta soltanto giri peggiori del corrente
Il kick deve migliorare subito il giro perturbato
La ricerca locale annulla sempre l'effetto del kick
Spiegazione. Il giro perturbato è molto peggiore, ma la ricerca locale ripara i lati lunghi creati dal kick e conserva le parti buone; con $100$ iterazioni l'ottimo si trova con tutti i $10$ semi.
Nella VNS per $P\,||\,C_{\max}$, l'intorno $N_k$ contiene gli assegnamenti ottenuti spostando $k$ lavori. Perché $N_2$ contiene l'intorno swap (scambio di due lavori su macchine diverse)?
Perché $N_2$ contiene tutte le soluzioni
Perché uno swap sposta un solo lavoro
Perché $N_2$ coincide con l'intorno move
Uno swap è la combinazione di due spostamenti
Spiegazione. Scambiare $j$ e $k$ equivale a spostare $j$ sulla macchina di $k$ e $k$ su quella di $j$: lo shaking con $k=2$ riproduce gli swap che l'intorno move non vede.
VNS per $P\,||\,C_{\max}$ (ricerca locale con l'intorno move) sull'istanza con carichi iniziali $(11,8,8)$: all'iterazione $3$, con $k=2$, due spostamenti casuali e la discesa scambiano di fatto i lavori $1$ e $4$, e si arriva all'ottimo $(9,9,9)$. Che cosa mostra?
Lo shaking con $k=1$ basta sempre a uscire
La VNS non usa nessuna ricerca locale
Lo shaking in $N_2$ trova uno swap che move non vede
La ricerca locale move trova da sola la soluzione ottima
Spiegazione. La soluzione corrente era un ottimo locale per move; il salto in $N_2$ seguito dalla discesa realizza uno swap migliorante.
GRASP per lo zaino: la lista ristretta contiene gli oggetti candidati con efficienza $p_j/w_j\ge e_{\max}-\alpha(e_{\max}-e_{\min})$. Le efficienze dei quattro oggetti candidati sono $2$, $1.75$, $2$, $\frac43$. Con $\alpha=\frac14$, quali oggetti entrano nella lista?
Gli oggetti $1$, $3$ e $2$
Gli oggetti $1$ e $3$
Solo l'oggetto $1$
Tutti e quattro gli oggetti
Spiegazione. Soglia $2-\frac14\cdot\frac23=\frac{11}6\approx1.83$: passano solo le efficienze $2$. Con $\alpha=\frac12$ la soglia è $\frac53$ ed entra anche l'oggetto $2$.
GRASP con $20$ iterazioni, $10$ esecuzioni: sul TSP a $20$ città con $\alpha=0$ il risultato è $319$ in ogni esecuzione, con $\alpha=0.1$ è l'ottimo $291$ in ogni esecuzione. Che cosa mostra?
Con $\alpha=0$ le iterazioni sono uguali; basta poca casualità
Il valore di $\alpha$ non influisce sul risultato
Con $\alpha=0$ la GRASP trova sempre l'ottimo
Più casualità peggiora sempre il risultato
Spiegazione. Con $\alpha=0$ ogni iterazione costruisce il giro greedy e la ricerca locale arriva sempre allo stesso ottimo locale; un po' di randomizzazione diversifica le partenze.
LNS sul TSP a $5$ città (ottimo $18$): dal giro $(1,3,2,4,5)$ di lunghezza $25$ si tolgono le città $3$ e $2$ e le si reinserisce con cheapest insertion, ottenendo $(1,4,2,5,3)$ di lunghezza $18$. Che cosa mostra l'esempio?
La LNS è una ricerca locale con l'intorno 2-opt
Togliere città peggiora sempre il giro finale
Un solo passo di distruzione e riparazione cambia molti lati
La riparazione rimette sempre le città dov'erano prima
Spiegazione. Il passo cambia quattro lati del giro, cosa che una singola mossa 2-opt non può fare: l'intorno della LNS è grande.
Nella large neighbourhood search per il TSP si tolgono $q$ città e le si reinserisce. Perché il suo intorno non si esplora mossa per mossa, come in una ricerca locale?
Perché contiene una sola soluzione vicina
È enorme: lo esplora implicitamente il metodo di riparazione
Perché le mosse non si possono valutare in alcun modo
Perché la distruzione è sempre deterministica e fissa
Spiegazione. Ci sono $\binom{n-1}{q}$ modi di scegliere le città tolte e molti modi di reinserirle: è il metodo di riparazione (euristico o esatto) che cerca un buon vicino.
LNS per il bin packing dalla soluzione di First Fit Decreasing ($10$ contenitori, ottimo $9$): svuotando $q=3$ contenitori e riparando in modo esatto si arriva a $9$ in ogni esecuzione, ma con $q=2$ anche la riparazione esatta fallisce sempre. Perché?
Gli oggetti di due contenitori FFD non entrano mai in uno solo
Perché FFD usa già il numero minimo di contenitori
Perché la riparazione esatta con due contenitori è troppo lenta
Perché con $q=2$ si svuota sempre il contenitore più pieno
Spiegazione. FFD è un algoritmo Any Fit: due suoi contenitori pesano insieme più di $c$, quindi riottimizzarne due non risparmia mai un contenitore. Con tre, gli oggetti possono entrare in due.
Nella LNS per il bin packing si svuotano alcuni contenitori e si reimpacchettano gli oggetti tolti. Quando si accetta il nuovo impacchettamento?
Solo se usa meno contenitori della soluzione corrente
Sempre, anche se usa più contenitori della corrente
Se $\sum_bL_b^2$ diminuisce, qualunque sia il numero di contenitori
Se usa meno contenitori, o tanti quanti e $\sum_bL_b^2$ non minore
Spiegazione. Sui plateau del numero di contenitori, l'obiettivo ausiliario $\sum_bL_b^2$ ($L_b$ carico del contenitore $b$) spinge verso contenitori più pieni.
LNS adattiva sul TSP a $20$ città con due metodi di distruzione (rimozione casuale e worst removal, che toglie le città la cui rimozione accorcia di più il giro): alla fine i pesi sono fra $0.77$ e $0.98$ per la casuale, fra $0.03$ e $0.08$ per la worst removal. Che cosa mostra?
I pesi non dipendono dai risultati delle iterazioni
La rimozione casuale non viene quasi mai usata
Il metodo ha imparato che la worst removal qui non paga
La worst removal è sempre il metodo migliore
Spiegazione. Da un giro buono, togliere le città peggio posizionate e reinserirle con cheapest insertion ricostruisce quasi sempre un giro non migliore: il peso della worst removal crolla.
Sul TSP a $20$ città la LNS semplice con rimozione casuale fa leggermente meglio della LNS adattiva (ALNS). Quando ripaga l'adattività?
Con un solo metodo di distruzione disponibile
Con molti metodi di qualità ignota ed esecuzioni lunghe
Solo sulle istanze molto piccole e facili
Mai: la LNS semplice è sempre migliore dell'ALNS
Spiegazione. L'ALNS impara i pesi dei metodi durante la ricerca: serve quando ci sono molti metodi da selezionare e abbastanza iterazioni per imparare.
Algoritmo genetico per lo zaino ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$): la riparazione toglie l'oggetto selezionato di efficienza $p_j/w_j$ minima (pareggi: indice massimo) finché il peso non supera $c$. Quale individuo si ottiene dal figlio $(1,1,0,1)$, di peso $12$?
$(1,1,0,0)$
$(1,1,0,1)$
$(0,1,0,1)$
$(1,0,0,1)$
Spiegazione. Efficienze degli oggetti selezionati: $2$, $1.75$, $1.33$; si toglie l'oggetto $4$: peso $9$, profitto $17$, l'ottimo.
In un algoritmo genetico steady-state, il figlio sostituisce l'individuo peggiore se è migliore e non è già nella popolazione. Perché si scartano i duplicati?
Perché un duplicato è sempre inammissibile
Perché la selezione non funziona con duplicati
Perché un duplicato ha sempre fitness minima
Farebbero perdere diversità alla popolazione
Spiegazione. Con molte copie dello stesso individuo, crossover e selezione producono sempre gli stessi figli e la ricerca si blocca.
La tabella finale del capitolo confronta le metaeuristiche su quattro istanze medie, con $10$ esecuzioni ciascuna. Stabilisce una classifica dei metodi?
Sì: vince il metodo con la media più bassa
No, perché i metodi sono tutti deterministici
No: servirebbero molte istanze e tempi di calcolo uguali
Sì: vince il metodo con più esecuzioni ottime
Spiegazione. Mostra che i risultati dipendono da parametri e componenti; una classifica richiede molte istanze e un confronto a parità di tempo.
In ogni metaeuristica un parametro fissa l'equilibrio fra intensificazione e diversificazione. Quale lo fissa nella GRASP (costruzione randomizzata più ricerca locale)?
La durata tabu delle mosse vietate
Il parametro $\alpha$ della lista ristretta
La temperatura iniziale $T_0$ del raffreddamento
La dimensione massima $k_{\max}$ dello shaking
Spiegazione. $\alpha$ decide quanto è casuale la costruzione; la durata tabu è della tabu search, $T_0$ del simulated annealing, $k_{\max}$ della VNS.
Due metaeuristiche hanno la stessa qualità media sulle istanze di prova. Quale è preferibile secondo le note?
Quella con più parametri da calibrare
Quella calibrata sulle stesse istanze di prova
Quella che va bene per un ampio intervallo di parametri
Quella che va molto bene per un intervallo ristretto
Spiegazione. Un metodo robusto rispetto ai parametri si trasferisce meglio su istanze nuove; calibrare sulle istanze di valutazione dà un quadro ottimistico.
Che cosa NON usano le metaeuristiche del capitolo (simulated annealing, tabu search, ILS, VNS, GRASP, LNS, algoritmi genetici)?
Intorni e ricerche locali sulle soluzioni
Rilassamenti del problema e solver MIP
Numeri casuali dal generatore di Park e Miller
Soluzioni di partenza da euristiche costruttive
Spiegazione. Manipolano solo soluzioni ammissibili (o penalizzate) e producono solo bound primali; la qualità si è misurata grazie agli ottimi calcolati a parte.
Nella LNS per il bin packing, la riparazione esatta (riottimizzare gli oggetti di pochi contenitori, con il resto fissato) ha raggiunto l'ottimo dove la riparazione con FFD falliva. Che cosa suggerisce?
Riottimizzare esattamente una parte dà intorni molto potenti
La riparazione non conta: conta solo la distruzione
Le metaeuristiche devono sempre usare algoritmi esatti
FFD è un algoritmo esatto per il bin packing
Spiegazione. È l'idea delle euristiche basate sulla PLI: fissare una parte della soluzione e risolvere in modo esatto il sottoproblema che resta.
Nelle metaeuristiche per il bin packing e per $P\,||\,C_{\max}$, le soluzioni con lo stesso obiettivo si confrontano con la somma dei quadrati dei carichi. In quale verso si ottimizza nei due problemi?
Si minimizza in entrambi, perché carichi bilanciati sono sempre migliori
Si massimizza in entrambi, perché il totale è fisso
Bin packing: si minimizza; $P\,||\,C_{\max}$: si massimizza
Bin packing: si massimizza (oggetti in pochi contenitori pieni); $P\,||\,C_{\max}$: si minimizza (carichi bilanciati)
Spiegazione. Nel bin packing si vuole svuotare un contenitore, e la somma dei quadrati cresce quando il peso si concentra; in $P\,||\,C_{\max}$ si vuole abbassare il carico massimo, e la somma decresce quando i carichi si bilanciano.
Le metaeuristiche del modulo usano numeri pseudo-casuali generati dal metodo di Park e Miller a partire da un seme. Perché i risultati si riportano su più semi?
Perché i semi diversi cambiano l'istanza risolta
Perché ogni seme dà un ottimo globale diverso
Il risultato di una metaeuristica dipende dai numeri casuali: un solo seme non basta a valutarla
Perché con un solo seme la metaeuristica non termina
Spiegazione. L'istanza è la stessa, ma le scelte casuali cambiano il cammino: si riportano minimo, media e massimo su più esecuzioni, come raccomandato per ogni euristica randomizzata.
Nel simulated annealing la temperatura si abbassa con la regola $T\leftarrow\alpha T$, con $0<\alpha<1$. Che effetto ha la temperatura sull'accettazione di un vicino peggiore di $\delta>0$, accettato con probabilità $e^{-\delta/T}$?
La temperatura cambia solo il numero di iterazioni, non l'accettazione
A temperatura alta si accettano spesso peggioramenti (diversificazione); a temperatura bassa quasi mai (intensificazione)
A temperatura bassa si accettano tutti i vicini
A temperatura alta non si accettano mai peggioramenti
Spiegazione. $e^{-\delta/T}$ tende a $1$ per $T$ grande e a $0$ per $T$ piccola: il raffreddamento passa gradualmente dall'esplorazione alla discesa, come nella ricottura dei metalli.
Nella tabu search la lista tabu non memorizza le soluzioni visitate ma attributi delle mosse recenti (per esempio «il lavoro $j$ sulla macchina $h$»), per una durata tabu fissata. Quale problema crea, e come si ripara?
Vieta anche soluzioni mai visitate; il criterio di aspirazione ammette una mossa tabu che batte la migliore soluzione trovata
Non impedisce di tornare alla soluzione appena lasciata; si ripara con una durata infinita
Rende la ricerca casuale; si ripara con il criterio di Metropolis
Vieta solo la soluzione corrente; si ripara memorizzando tutto il cammino
Spiegazione. Un attributo vieta tutte le soluzioni che lo contengono, non solo quella lasciata. L'aspirazione ripristina le mosse tabu che porterebbero a un nuovo record.
L'iterated local search ($ILS$) ripete: perturbazione dell'ottimo locale corrente, ricerca locale, criterio di accettazione. Che ruolo ha la forza della perturbazione?
Più è forte, migliore è sempre il risultato
Non conta: la ricerca locale annulla qualsiasi perturbazione
Troppo debole: la ricerca non termina; troppo forte: la ricerca diventa esatta
Troppo debole: la ricerca locale torna allo stesso ottimo; troppo forte: si riparte quasi da una soluzione casuale
Spiegazione. La perturbazione deve uscire dalla valle corrente senza perdere la struttura della buona soluzione: con una perturbazione troppo forte $ILS$ degenera in un multi-start.
Nell'iterated local search ($ILS$) per il TSP con la ricerca locale 2-opt si usa come perturbazione il double bridge, che taglia il giro in quattro segmenti $A,B,C,D$ e li ricollega come $A\,C\,B\,D$. Perché è adatto?
Cambia un solo lato, quindi non perde la struttura del giro
È una mossa 2-opt, quindi la ricerca locale lo accetta sempre
Cambia tre lati senza invertire segmenti, e una singola mossa 2-opt non lo annulla facilmente
Restituisce sempre un giro più corto
Spiegazione. Il double bridge è una mossa che 2-opt non contiene e non annulla con una mossa sola: sposta la ricerca in un'altra valle mantenendo gran parte del giro.
Nella variable neighbourhood search ($VNS$) l'intorno $N_k$ contiene le soluzioni ottenute con $k$ mosse. A ogni iterazione si sceglie a caso una soluzione di $N_k$ (shaking) e la si migliora con una ricerca locale. Come si aggiorna $k$?
Se l'ottimo locale è migliore si passa a $k+1$; altrimenti si torna a $k=1$
Se l'ottimo locale trovato è migliore lo si accetta e si torna a $k=1$; altrimenti si passa a $k+1$
$k$ si sceglie a caso a ogni iterazione
$k$ cresce sempre di $1$, qualunque sia il risultato
Spiegazione. Si esplora prima vicino all'ottimo corrente e si va più lontano solo quando le vicinanze non danno miglioramenti: lo shaking diversifica, la ricerca locale intensifica.
Quale differenza c'è fra la discesa a intorni variabili ($VND$) e la variable neighbourhood search ($VNS$)?
$VND$ esplora gli intorni in modo completo e deterministico; $VNS$ ne estrae soluzioni a caso (shaking) e poi applica una ricerca locale
$VND$ è randomizzata, $VNS$ è deterministica
$VND$ usa un solo intorno, $VNS$ più intorni
Sono lo stesso algoritmo con due nomi
Spiegazione. $VND$ si ferma in un ottimo locale per tutti gli intorni; $VNS$ usa gli intorni crescenti per saltare fuori dagli ottimi locali, ed è una metaeuristica.
In $GRASP$ ogni iterazione costruisce una soluzione con un greedy randomizzato (lista ristretta dei candidati con parametro $\alpha$) e la migliora con una ricerca locale. Che cosa succede con $\alpha=0$?
La costruzione diventa del tutto casuale
La ricerca locale non viene più eseguita
$GRASP$ trova sempre l'ottimo globale
Ogni iterazione costruisce la stessa soluzione greedy: $GRASP$ diventa una sola ricerca locale
Spiegazione. Con $\alpha=0$ la lista contiene solo i candidati migliori, e a meno di pareggi la costruzione è sempre la stessa; un po' di casualità basta a ottenere soluzioni diverse.
Nella large neighbourhood search ($LNS$) un metodo di distruzione toglie una parte della soluzione e un metodo di riparazione la ricostruisce. Quali ruoli hanno i due metodi?
Entrambi intensificano: $LNS$ non diversifica
La distruzione intensifica, la riparazione diversifica
La distruzione (di solito casuale) diversifica, la riparazione intensifica
Entrambi diversificano, e la ricerca locale intensifica
Spiegazione. Togliere parti diverse sposta la ricerca, e il numero $q$ di elementi tolti controlla quanto; la riparazione ricostruisce al meglio la parte tolta, con un'euristica o anche in modo esatto.
In $LNS$ per il bin packing, si svuotano alcuni contenitori di una soluzione di First Fit Decreasing (FFD) e si ricollocano gli oggetti tolti con FFD stesso. Che cosa succede?
La soluzione diventa inammissibile
La soluzione non migliora mai: FFD ricolloca gli oggetti tolti nello stesso modo
Si ottiene sempre l'ottimo dopo un'iterazione
La soluzione migliora sempre di almeno un contenitore
Spiegazione. La riparazione con lo stesso algoritmo che ha costruito la soluzione rifà le stesse scelte; con una riparazione esatta del sottoproblema, invece, $LNS$ può svuotare un contenitore.
In un algoritmo genetico per lo zaino 0-1 con codifica binaria, il crossover a un punto con taglio $cut=2$ combina i genitori $(1,1,0,0,1)$ e $(0,1,1,1,0)$. Quale figlio produce, prendendo i primi $cut$ geni dal primo genitore?
$(1,1,1,1,0)$
$(0,1,0,0,1)$
$(1,1,0,1,0)$
$(1,1,0,0,0)$
Spiegazione. Geni $1,2$ dal primo genitore, $(1,1)$, e geni $3,4,5$ dal secondo, $(1,1,0)$. Il figlio può superare la capacità e va riparato, per esempio togliendo gli oggetti di efficienza minima.
Una metaeuristica è una strategia generale che guida una ricerca locale oltre il primo ottimo locale. Perché si dice che è uno schema e non un algoritmo?
Perché non usa mai la ricerca locale
Perché garantisce l'ottimo solo per alcuni problemi
Diventa un algoritmo solo scegliendo rappresentazione, intorni, ricerca locale e parametri
Perché non termina mai
Spiegazione. Lo stesso schema (per esempio tabu search) dà algoritmi molto diversi per il TSP e per $P\,||\,C_{\max}$, a seconda delle scelte e della calibrazione.
Il multi-start ripete la ricerca locale da molte soluzioni di partenza. Quale limite cercano di superare le metaeuristiche?
Il multi-start è deterministico
Ogni partenza ignora ciò che è stato appreso prima, mentre le valli buone si trovano di solito vicino ad altre valli buone
Il multi-start non trova mai ottimi locali
Il multi-start richiede un bound duale
Spiegazione. Le metaeuristiche escono da un ottimo locale restando vicino a quanto trovato: accettando mosse peggiori (SA), vietando mosse recenti (TS), perturbando (ILS) o cambiando intorno (VNS).
Nel simulated annealing per un problema di minimo, un vicino peggiore di $\delta>0$ si accetta con probabilità $e^{-\delta/T}$, dove $T$ è la temperatura. Con $\delta=3$ e $T=3$, quanto vale, circa?
$e^{-1}\approx0.37$
$e^{-3}\approx0.05$
$1$
$e^{-9}\approx0.0001$
Spiegazione. $\delta/T=1$. A temperatura alta si accettano quasi tutte le mosse peggiori; al diminuire di $T$ la ricerca diventa una discesa.
Nel simulated annealing con penalità per lo zaino 0/1 si massimizza $f_\beta(x)=\sum_jp_jx_j-\beta\max\{0,\sum_jw_jx_j-c\}$. Un vettore ha profitto $30$ e peso $14$, con $c=10$ e $\beta=2$. Quanto vale $f_\beta$, e può diventare la migliore soluzione trovata?
$30$; no
$2$; no
$22$; sì, perché $f_\beta$ è alta
$22$; no, la migliore soluzione si aggiorna solo con soluzioni ammissibili
Spiegazione. $30-2\cdot4=22$. Il vettore non è ammissibile: la ricerca può attraversarlo, ma non lo restituisce.
In un esperimento di simulated annealing sul TSP con $20$ città, partendo da un giro di lunghezza $326$, nelle prime iterazioni il giro corrente arriva a lunghezza $765$. Come si spiega?
Il simulated annealing ha un errore di implementazione
Il giro iniziale era inammissibile
All'inizio la temperatura è alta rispetto ai peggioramenti tipici, e quasi tutte le mosse peggiori sono accettate
La temperatura iniziale era troppo bassa
Spiegazione. Ad alta temperatura la ricerca è quasi una passeggiata casuale (diversificazione); raffreddando si concentra sulle soluzioni buone (intensificazione).
A temperatura fissata $T$ e con intorno simmetrico, il simulated annealing ha distribuzione stazionaria $\pi_T(S)\propto e^{-f(S)/T}$ (problema di minimo). Con $f(S_1)=10$, $f(S_2)=12$ e $T=2$, quanto vale $\pi_T(S_1)/\pi_T(S_2)$?
$e^{2}\approx7.39$
$e\approx2.72$
$e^{-1}\approx0.37$
$\frac56$
Spiegazione. $\pi_T(S_1)/\pi_T(S_2)=e^{(f(S_2)-f(S_1))/T}=e^{2/2}=e$: la soluzione migliore è più probabile, tanto più quanto più $T$ è bassa.
Nella tabu search per $P\,||\,C_{\max}$ con l'intorno move, dopo aver spostato il lavoro $j$ dalla macchina $h$ a un'altra, l'attributo $(j,h)$ diventa tabu per un certo numero di iterazioni. Che cosa vieta?
Di riportare il lavoro $j$ sulla macchina $h$, per non tornare subito alla soluzione appena lasciata
Di spostare qualsiasi lavoro sulla macchina $h$
Di spostare di nuovo il lavoro $j$ ovunque
Di usare la macchina $h$ fino alla fine
Spiegazione. La tabu search si sposta sul miglior vicino non tabu anche se peggiore; la lista tabu impedisce di annullare subito la mossa e quindi di ciclare.
Nella tabu search per il TSP con l'intorno 2-opt, i lati tolti da una mossa restano tabu per un numero di iterazioni detto durata tabu. Che cosa succede con una durata troppo corta o troppo lunga?
La durata non ha effetto sui risultati
Troppo lunga: la tabu search diventa simulated annealing
Troppo corta: la ricerca si ferma subito; troppo lunga: cicla
Troppo corta: la ricerca può ciclare; troppo lunga: vieta troppe mosse e la ricerca diventa rigida
Spiegazione. La durata bilancia diversificazione e intensificazione; gli esperimenti sulle istanze medie mostrano che il valore giusto dipende dall'istanza.
L'iterated local search per il TSP usa la ricerca locale 2-opt e, come perturbazione (kick), la mossa double bridge. Perché si usa un kick che la ricerca locale non annulla facilmente?
Perché il double bridge migliora sempre il giro
Perché la ricerca locale non accetta giri peggiori
Se la ricerca locale potesse annullarlo con una sola mossa, tornerebbe subito all'ottimo locale di partenza
Perché il kick deve rendere il giro inammissibile
Spiegazione. Il double bridge è una mossa 4-opt: 2-opt non la annulla in un passo, quindi la discesa successiva esplora una valle vicina ma diversa.
Nella variable neighbourhood search con intorni $N_1,\dots,N_{k_{\max}}$ di dimensione crescente, dopo lo shaking in $N_k$ e la ricerca locale, che cosa si fa se il nuovo ottimo locale è migliore e se non lo è?
In entrambi i casi si ricomincia da una soluzione casuale
Se migliore: lo si accetta e si torna a $k=1$; altrimenti si passa a $k+1$
Se migliore: si passa a $k+1$; altrimenti si torna a $k=1$
In entrambi i casi si passa a $k+1$
Spiegazione. Si allarga l'intorno solo quando serve: un miglioramento riporta all'intorno più piccolo, che è il più economico.
Nella GRASP per il TSP la città successiva si sceglie a caso nella lista ristretta dei candidati (RCL), le città non visitate a distanza al più $d_{\min}+\alpha(d_{\max}-d_{\min})$ dall'ultima città. Che cosa succede con $\alpha=0$ e con $\alpha=1$?
$\alpha=0$: nearest neighbour (scelta greedy, a parte i pareggi); $\alpha=1$: scelta del tutto casuale
Nella LNS adattiva (ALNS) il metodo di distruzione $o$ si sceglie con probabilità $w_o/\sum_{o'}w_{o'}$, e dopo l'uso il peso si aggiorna con $w_o\leftarrow(1-\rho)w_o+\rho\psi$, dove $\psi$ premia il risultato. Con $w_o=2$, $\rho=0.5$ e $\psi=4$, quanto vale il nuovo peso?
$2.5$
$6$
$4$
$3$
Spiegazione. $0.5\cdot2+0.5\cdot4=3$: i metodi che funzionano vengono scelti più spesso, ma il fattore $\rho$ conserva memoria del passato.
I parametri di una metaeuristica vanno calibrati. Quale procedura evita un quadro troppo ottimistico delle prestazioni?
Non calibrare: usare sempre i valori di letteratura
Calibrare su istanze di addestramento e valutare su istanze diverse
Calibrare e valutare sulle stesse istanze
Scegliere i parametri che danno il risultato migliore su una sola istanza
Spiegazione. Valutare sulle istanze usate per calibrare sovrastima le prestazioni; inoltre calibrare un parametro alla volta ignora le interazioni fra parametri.
Le metaeuristiche del capitolo non usano rilassamenti né solver MIP. Eppure per $P\,||\,C_{\max}$ e il bin packing alcune si sono fermate certificando l'ottimo. Come è possibile?
Hanno raggiunto un lower bound semplice (per esempio $\lceil\sum_jt_j/m\rceil$), che è un bound duale calcolato a parte
Perché una metaeuristica che si ferma è sempre ottima
Perché la tabu search calcola un rilassamento lineare
Perché quelle istanze avevano un solo ottimo locale
Spiegazione. Senza un bound duale una metaeuristica non può sapere quanto è buona; quando trova una soluzione che uguaglia un lower bound semplice, l'ottimalità è certificata.
La tabu search si sposta sempre sul miglior vicino non tabu, anche se peggiore della soluzione corrente. Che cosa succederebbe con durata tabu nulla (nessuna mossa vietata) in un ottimo locale?
La ricerca diventerebbe un simulated annealing
La ricerca troverebbe l'ottimo globale
La ricerca si fermerebbe nell'ottimo locale, come una discesa
La ricerca può tornare subito alla soluzione appena lasciata e ciclare fra due soluzioni
Spiegazione. Dall'ottimo locale si va al miglior vicino (peggiore); da lì il miglior vicino è spesso l'ottimo locale di prima. La lista tabu impedisce proprio questo ritorno.
La tabu search esplora tutto l'intorno e si sposta sul miglior vicino non tabu, anche se peggiore. In che cosa differisce dal simulated annealing nel modo di uscire da un ottimo locale?
Riparte da una soluzione casuale
Non esce mai da un ottimo locale
È deterministica: esce perché si sposta sempre, e la memoria tabu le impedisce di tornare indietro; il simulated annealing accetta peggioramenti a caso
Accetta peggioramenti con probabilità $e^{-\delta/T}$
Spiegazione. Con gli stessi dati e la stessa soluzione di partenza la tabu search fa sempre le stesse mosse; la diversificazione viene dalla lista tabu, non dal caso.
Le metaeuristiche del capitolo sono illustrate sugli stessi quattro problemi della ricerca locale (KP, BPP, TSP, $P\,||\,C_{\max}$). Perché si riusano gli stessi intorni?
Perché le metaeuristiche risolvono solo il TSP
Una metaeuristica guida una ricerca locale: rappresentazione e intorni restano quelli del problema
Perché le metaeuristiche non usano intorni
Perché i quattro problemi hanno lo stesso intorno
Spiegazione. Cambia la strategia per uscire dagli ottimi locali, non la struttura delle mosse: flip e swap per il KP, move e swap per BPP e $P\,||\,C_{\max}$, 2-opt per il TSP.
Sulle istanze medie le metaeuristiche si eseguono $10$ volte con semi diversi, riportando minimo, media e massimo del valore trovato. Perché più esecuzioni?
Perché la prima esecuzione è sempre di prova
Perché ogni esecuzione usa un'istanza diversa
Per calcolare un bound duale
Molte metaeuristiche sono randomizzate: una sola esecuzione può essere fortunata o sfortunata
Spiegazione. Il seme fissa le scelte casuali; più semi mostrano la variabilità del metodo, e il numero di esecuzioni che raggiungono l'ottimo ne misura l'affidabilità.
Nel confronto finale delle metaeuristiche sulle istanze medie, per ogni metodo si riporta anche il numero di esecuzioni (su $10$) che raggiungono il valore ottimo. Che cosa aggiunge rispetto al solo miglior valore?
Misura il tempo di calcolo
Misura il bound duale
Misura l'affidabilità: un metodo che trova l'ottimo una volta su dieci è meno robusto di uno che lo trova sempre
Niente: conta solo il miglior valore
Spiegazione. Minimo, media, massimo e numero di successi descrivono la distribuzione dei risultati, che dipende anche dai parametri.
Simulated annealing per un problema di minimo, alla temperatura $T=5$: un vicino peggiore di $\delta=10$. Con quale probabilità lo accetta la regola di Metropolis?
$e^{-10}\approx 0{,}00005$
$e^{-2}\approx 0{,}14$
$e^{-0{,}5}\approx 0{,}61$
$1-e^{-2}\approx 0{,}86$
Spiegazione. Per $\delta>0$ la probabilità è $e^{-\delta/T}=e^{-10/5}=e^{-2}\approx0{,}14$. I vicini non peggiori ($\delta\le0$) si accettano con probabilità $1$.
Nella tabu search una mossa è tabu, ma porta a una soluzione migliore della migliore trovata finora. Che cosa fa l'algoritmo?
Non la esegue finché resta tabu
Riparte da una soluzione casuale
Raddoppia la tenure
Può eseguirla: criterio di aspirazione
Spiegazione. Il criterio di aspirazione ammette una mossa tabu che porta a una soluzione migliore della migliore trovata: quella soluzione non è certo già stata visitata.
Quale scelta dei parametri rende il simulated annealing simile a una passeggiata casuale fra le soluzioni?
Una temperatura minima alta
Una sola mossa per temperatura
Una temperatura molto alta
Un fattore $\alpha$ vicino a $0$
Spiegazione. Con $T$ molto alta $e^{-\delta/T}\approx1$: quasi ogni vicino peggiore è accettato. Con $\alpha$ vicino a $0$ la temperatura crolla subito e l'algoritmo si comporta come una discesa.
Che cosa succede nella tabu search se la tenure è troppo lunga?
Il criterio di aspirazione smette di agire
Si vietano troppe mosse, perdendo buone soluzioni
La ricerca torna a ciclare fra poche soluzioni
Si comporta come un simulated annealing
Spiegazione. Una lista tabu lunga vieta troppo (sulle istanze del capitolo, con tenure grande si perde l'ottimo); è la tenure troppo corta che lascia ciclare la ricerca.
Nell'iterated local search la perturbazione è troppo debole. Che cosa succede?
La ricerca locale la annulla: stesso ottimo locale
Diventa un riavvio da una soluzione casuale
L'algoritmo non termina più
Il criterio di accettazione rifiuta ogni ottimo
Spiegazione. Una perturbazione debole resta nella stessa valle: la ricerca locale riporta allo stesso ottimo locale. Una perturbazione troppo forte, al contrario, è un riavvio casuale.
GRASP con una lista ristretta dei candidati (RCL) di un solo elemento: a che cosa si riduce?
A una ricerca locale da partenze casuali
Al simulated annealing con temperatura $T=0$
A una large neighbourhood search sul greedy
Allo stesso greedy migliorato a ogni iterazione
Spiegazione. Con una RCL di un elemento la costruzione sceglie sempre il migliore: è il greedy deterministico, e ogni iterazione ripete la stessa soluzione e lo stesso ottimo locale.
Perché l'algoritmo genetico per lo zaino 0/1 ha bisogno di un passo di riparazione?
La mutazione diminuisce sempre il profitto
Incrocio e mutazione possono superare la capacità
La popolazione potrebbe svuotarsi
I profitti cambiano a ogni generazione
Spiegazione. Il figlio di due soluzioni ammissibili, e una mutazione che porta un bit a $1$, possono violare il vincolo di capacità: la riparazione toglie oggetti finché il vettore torna ammissibile.
Perché gli esperimenti del capitolo sulle metaeuristiche usano un generatore di numeri casuali con un seme fissato?
Perché le metaeuristiche diventino esatte
Perché senza seme l'algoritmo non termina
Perché garantisce di raggiungere l'ottimo
Perché ogni corsa sia riproducibile
Spiegazione. Con lo stesso seme si ottengono gli stessi numeri e quindi la stessa corsa, nelle note, nel codice e nell'app. Il seme non cambia la natura euristica del metodo.
Nella variable neighbourhood search lo shaking prende una soluzione casuale in $N_k$, e $k$ cresce dopo ogni insuccesso. Perché?
Perché $N_k$ è più piccolo per $k$ più grande
Per ridurre il tempo di calcolo di ogni iterazione
Per diversificare: soluzioni più lontane escono dalla valle
Per intensificare la ricerca attorno all'incumbent
Spiegazione. Se la ricerca locale riporta allo stesso ottimo, una perturbazione più forte serve a cambiare valle; dopo un miglioramento si torna a $k=1$ per intensificare.
Simulated annealing alla temperatura $T=2$: due vicini peggiori, con $\delta_1=2$ e $\delta_2=6$. Quante volte è più probabile accettare il primo?
$e^{-2}\approx0{,}14$ volte
$e^{2}\approx7{,}4$ volte
$3$ volte
$e^{4}\approx54{,}6$ volte
Spiegazione. Il rapporto è $\frac{e^{-2/2}}{e^{-6/2}}=e^{-1+3}=e^2\approx7{,}4$. Non è il rapporto dei peggioramenti ($3$): la probabilità decresce in modo esponenziale con $\delta/T$.
Simulated annealing: fissato un peggioramento $\delta>0$, come si comporta la probabilità di accettarlo quando $T\to0$?
Tende a $0$, come una discesa
Tende a $1$: si accetta ogni vicino
Resta $e^{-\delta}$
Tende a $\frac12$
Spiegazione. $e^{-\delta/T}\to0$ per $T\to0$: l'algoritmo diventa una discesa (randomizzata). Per $T\to\infty$ invece $e^{-\delta/T}\to1$ e si accetta quasi tutto.
Iterated local search con il criterio che accetta ogni nuovo ottimo locale, anche peggiore. Che cosa fa la ricerca?
Intensifica: accetta solo ottimi migliori
Diventa una ricerca locale semplice
Si ferma al primo ottimo locale
Diversifica: una passeggiata fra ottimi locali
Spiegazione. Accettare solo ottimi migliori intensifica; accettarli tutti diversifica, perché la ricerca si sposta di valle in valle. Criteri intermedi accettano un ottimo peggiore con una probabilità, come in $SA$.
Nella variable neighbourhood search, che cosa succede a $k$ quando la soluzione ottenuta con lo shaking e la ricerca locale è migliore della corrente?
Si scarta e $k$ torna a $1$
Si tiene e $k$ resta uguale
Diventa la corrente e $k$ torna a $1$
Diventa la corrente e $k$ cresce di $1$
Spiegazione. Dopo un miglioramento si riparte dall'intorno più piccolo per intensificare; dopo un insuccesso $k$ cresce (fino a $k_{\max}$) per diversificare.
Large neighbourhood search con distruzione di tutti gli $n$ elementi e riparazione esatta. Che cosa fa la prima iterazione?
Calcola solo un bound duale
Risolve l'istanza all'ottimo
Restituisce la soluzione di partenza
Fa una mossa 2-opt
Spiegazione. Se si toglie tutto, la riparazione esatta deve risolvere l'istanza intera: l'intorno contiene tutte le soluzioni. Per questo $q$ si tiene piccolo, così la riparazione resta veloce.
Tabu search parte da un ottimo locale e si sposta sempre sul miglior vicino non tabu. Come può migliorare la miglior soluzione trovata?
Attraversando soluzioni peggiori fino a un'altra valle
Accettando i peggioramenti con probabilità $e^{-\delta/T}$
Ripartendo da una soluzione casuale
Risolvendo un sotto-MIP
Spiegazione. Dal fondo della valle il miglior vicino non tabu è peggiore, e la lista tabu impedisce di tornare indietro: la ricerca risale e scende in un'altra valle. La regola probabilistica è quella di $SA$.
Che cosa restituisce GRASP dopo le sue iterazioni di costruzione randomizzata e ricerca locale?
L'ultimo ottimo locale trovato
La soluzione greedy deterministica
La media delle soluzioni trovate
Il miglior ottimo locale trovato
Spiegazione. Ogni iterazione costruisce una soluzione con la lista ristretta dei candidati e la migliora con la ricerca locale; GRASP tiene il miglior ottimo locale di tutte le iterazioni.
Perché la lista tabu memorizza attributi delle mosse (per esempio «il lavoro $j$ ha lasciato la macchina $h$») invece delle soluzioni visitate?
Le soluzioni visitate non sono ammissibili
Così la tenure non serve più
Confrontare soluzioni intere costa troppo
Gli attributi vietano meno soluzioni
Spiegazione. Confrontare ogni vicino con tutte le soluzioni visitate è troppo costoso. Gli attributi vietano anzi più del necessario (anche soluzioni mai viste), e per questo serve il criterio di aspirazione.
Perché il simulated annealing con raffreddamento geometrico $T\leftarrow\alpha T$ ha bisogno di una temperatura minima $T_{\min}$?
Serve a calcolare il bound duale
$\alpha^kT_0$ non arriva mai a $0$
Sotto $T_{\min}$ la regola di Metropolis non vale
Con $T$ piccolo non si accettano miglioramenti
Spiegazione. Con $0<\alpha<1$ la temperatura decresce ma resta positiva: serve un criterio d'arresto, come $T\le T_{\min}$. I miglioramenti si accettano a ogni temperatura.
Nella large neighbourhood search adattiva (ALNS), come si scelgono gli operatori di distruzione e di riparazione?
Con pesi dati dal successo passato
Sempre gli stessi due operatori
In ordine fisso, a turno
Con il criterio di aspirazione
Spiegazione. ALNS tiene un peso per ogni operatore, che cresce quando l'operatore produce soluzioni buone: gli operatori che funzionano meglio sull'istanza vengono scelti più spesso.
Oltre alla scelta casuale, che cosa serve alla fase di costruzione di GRASP?
Una soluzione ammissibile di partenza
Una lista tabu delle mosse
Una temperatura e un raffreddamento
Una funzione greedy che valuta i candidati
Spiegazione. La lista ristretta dei candidati raccoglie i migliori secondo una funzione greedy (per lo zaino, l'efficienza); la scelta casuale avviene fra quelli.
Nello scheduling $P\,||\,C_{\max}$ un assegnamento è un vettore binario $\vet x$ con $x_{ij}=1$ se il lavoro $j$ è sulla macchina $i$; la distanza $\Delta(\vet x,\bar{\vet x})$ conta le componenti diverse. Due assegnamenti differiscono per la macchina di $3$ lavori. Quanto vale $\Delta(\vet x,\bar{\vet x})$?
$3m$
$3$
$9$
$6$
Spiegazione. Ogni lavoro spostato cambia due componenti (una da $1$ a $0$, l'altra da $0$ a $1$): $\Delta=2r=6$.
Nei modelli del bin packing e di $P\,||\,C_{\max}$, le variabili binarie $x_{jb}$ assegnano ogni oggetto (lavoro) $j$ a un contenitore (macchina) $b$. Perché arrotondare all'intero più vicino la soluzione del rilassamento lineare fallisce quasi sempre?
Il rilassamento lineare di questi modelli è illimitato, quindi non c'è una soluzione da arrotondare
Il rilassamento lineare di questi modelli ha sempre soluzione intera, quindi arrotondare non cambia nulla
I vincoli $\sum_b x_{jb}=1$ sono uguaglianze: valori frazionari arrotondati uno per uno quasi mai sommano a $1$
I vincoli di capacità sono disuguaglianze: valori frazionari arrotondati uno per uno li soddisfano sempre
Spiegazione. Con $\sum_b x_{jb}=1$ e valori frazionari, arrotondare ogni variabile separatamente lascia oggetti non assegnati o assegnati due volte.
Nelle euristiche per la programmazione lineare intera, il diving fissa variabili in sequenza risolvendo il rilassamento lineare, e RINS risolve un sotto-problema intero vicino alla soluzione incumbent (la migliore nota). Quale affermazione è corretta?
Un dive esplora tutto l'albero; RINS garantisce una soluzione migliore dell'incumbent
Un dive è un solo cammino nell'albero; RINS fissa le variabili su cui rilassamento e incumbent concordano
Un dive è un solo cammino nell'albero; RINS fissa le variabili su cui rilassamento e incumbent sono diversi
Un dive esplora tutto l'albero; RINS fissa le variabili su cui rilassamento e incumbent concordano
Spiegazione. Il primo fissaggio sbagliato di un dive non viene mai corretto; RINS risolve un sotto-MIP con le variabili concordi fissate, quindi non può trovare soluzioni che le cambiano.
Nelle euristiche basate sulla PLI si usano l'arrotondamento $[v]=\lfloor v+\frac12\rfloor$ e la distanza $\Delta(\vet x,\bar{\vet x})=\sum_j|x_j-\bar x_j|$ da un punto intero. Quanto valgono $[0.5]$, $[0.25]$ e $\Delta\big((1,0,1,0),(1,1,0,0)\big)$?
$1$, $0$ e $2$
$1$, $0$ e $1$
$1$, $1$ e $4$
$0$, $0$ e $2$
Spiegazione. $\lfloor1\rfloor=1$, $\lfloor0.75\rfloor=0$; i due vettori differiscono nelle componenti $2$ e $3$: $\Delta=2$.
Il modello del bin packing per le euristiche PLI ha variabili binarie $x_{jb}$ (oggetto $j$ nel contenitore $b$) e $y_b$ (contenitore $b$ usato), vincoli di assegnamento (uno per oggetto) e di capacità (uno per contenitore). Con $n=6$ oggetti e $m=6$ contenitori, quante variabili e quanti vincoli ha?
$48$ variabili e $18$ vincoli
$36$ variabili e $12$ vincoli
$42$ variabili e $6$ vincoli
$42$ variabili e $12$ vincoli
Spiegazione. $6\cdot6=36$ variabili $x_{jb}$ più $6$ variabili $y_b$; $6$ vincoli di assegnamento e $6$ di capacità.
Nelle euristiche basate sulla PLI i metodi sono descritti per un problema di minimo. Come si trattano il modello $\mathrm{ILP}_{\mathrm{KP}}$ dello zaino ($\max\sum_jp_jx_j$) e i suoi cutoff?
Sostituendo il vincolo di capacità con un'uguaglianza
Rilassando le variabili binarie a variabili continue
Scambiando $\min$ e $\max$, $\le$ e $\ge$ nei confronti fra valori
Cambiando segno ai pesi e lasciando i cutoff invariati
Spiegazione. Per lo zaino il cutoff diventa $\sum_jp_jx_j\ge f(\bar{\vet x})+\theta$: si cerca una soluzione di profitto maggiore.
Zaino con $c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$. Il rilassamento lineare prende gli oggetti per efficienza $p_j/w_j$ non crescente: gli oggetti $1$ e $3$ (peso $8$) per intero, poi l'oggetto critico $2$ per una frazione. Quale frazione, e quanto vale $z(\mathrm{LP})$?
$\frac14$, e $z(\mathrm{LP})=17$
$\frac14$, e $z(\mathrm{LP})=17.75$
$\frac12$, e $z(\mathrm{LP})=19.5$
$1$, e $z(\mathrm{LP})=23$
Spiegazione. Resta capacità $9-8=1$ su un peso $4$: frazione $\frac14$, valore $10+6+\frac74=17.75$. Arrotondato per difetto, $17$ è un bound valido, non il valore del LP.
Nel modello del bin packing ($y_b=1$ se il contenitore $b$ è usato, $x_{jb}=1$ se l'oggetto $j$ è nel contenitore $b$, capacità $c$) il vincolo è $-\sum_jw_jx_{jb}+c\,y_b\ge0$ per ogni $b$. Che cosa impone?
Un contenitore usato contiene al più $c$, uno non usato è vuoto
Ogni oggetto va in esattamente un contenitore usato
I contenitori si usano in ordine crescente di indice
Ogni contenitore è usato da almeno un oggetto dell'istanza
Spiegazione. Con $y_b=0$ il vincolo diventa $\sum_jw_jx_{jb}\le0$; con $y_b=1$ diventa $\sum_jw_jx_{jb}\le c$. L'assegnamento unico è un altro vincolo.
Nel modello del bin packing si minimizza $\sum_by_b$, con vincoli di capacità $-\sum_jw_jx_{jb}+c\,y_b\ge0$. In una soluzione ottima, quanto vale $y_b$ per un contenitore che non contiene oggetti?
$1$, perché lo richiede il vincolo di capacità
$1$: ogni contenitore disponibile va sempre aperto
Un valore qualsiasi compreso fra $0$ e $1$
$0$: il vincolo è soddisfatto e l'obiettivo lo vuole basso
Spiegazione. Senza oggetti il vincolo diventa $c\,y_b\ge0$, vero anche con $y_b=0$, e minimizzare $\sum_by_b$ porta $y_b$ a $0$.
Il modello $\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}$ ha i vincoli di eliminazione dei sottogiri sui sottoinsiemi $S\subseteq\mathscr{V}\setminus\{1\}$ con $|S|\ge2$. Quanti sono con $n=5$ città?
$26$
$10$
$11$
$16$
Spiegazione. I sottoinsiemi di $\{2,3,4,5\}$ sono $2^4=16$; tolti il vuoto e i $4$ singoletti restano $11$. Con i $5+5$ vincoli sugli archi entranti e uscenti si arriva a $21$.
Sull'istanza a $5$ città usata per le euristiche, il rilassamento lineare del modello DFJ del TSP ha già come soluzione il giro ottimo. Perché il TSP non si usa negli altri esempi del capitolo sulle euristiche PLI?
Perché le euristiche PLI non si applicano al TSP
Ogni metodo troverebbe subito l'ottimo: il LP è già intero
Perché il modello DFJ non ha variabili binarie
Perché il LP del TSP è inammissibile
Spiegazione. Con soluzione LP intera arrotondamento, diving e gli altri metodi si fermano al primo passo. Il modello MTZ ha un rilassamento più debole ($17$).
Nel modello di $P\,||\,C_{\max}$ (binarie $x_{jh}$, continua $C_{\max}$), RINS, local branching e proximity search usano la distanza $\Delta(\vet x,\bar{\vet x})=\sum_{j\in\mathscr{D}}|x_j-\bar x_j|$ sulle variabili intere $\mathscr{D}$. Su quali variabili si calcola?
Solo sulle binarie $x_{jh}$: $C_{\max}$ non vi entra
Solo sulla variabile $C_{\max}$
Solo sulle variabili frazionarie del rilassamento
Su tutte le variabili, $C_{\max}$ compresa
Spiegazione. $C_{\max}$ è l'unica variabile continua; per questo la feasibility pump, guidata da $\Delta$, ignora i carichi.
Nel modello di $P\,||\,C_{\max}$ (variabili $x_{jh}$, tempi $t_j$) il vincolo è $-\sum_jt_jx_{jh}+C_{\max}\ge0$ per ogni macchina $h$. Che cosa significa?
Il carico totale è al più $C_{\max}$
Ogni macchina ha carico esattamente $C_{\max}$
Ogni lavoro va su una sola macchina
$C_{\max}$ non è minore del carico di nessuna macchina
Spiegazione. Minimizzando $C_{\max}$ con questi vincoli si ottiene il carico massimo. Il carico totale è $\sum_jt_j$, che in generale supera $C_{\max}$.
Per $P\,||\,C_{\max}$ con $m=3$ e $t=(5,5,4,4,3,3,3)$, il rilassamento lineare ha valore $\frac{27}3=9$, e la soluzione restituita dal solver assegna in modo frazionario i lavori $2$ e $3$, con tre carichi uguali a $9$. Perché il LP ha infinite soluzioni ottime?
Perché nel modello mancano i vincoli di assegnamento
Perché il valore ottimo intero dell'istanza è $10$
Ogni assegnamento frazionario con tre carichi pari a $9$ è ottimo
Perché la variabile $C_{\max}$ non è limitata dal basso
Spiegazione. Il LP vede solo i carichi: qualunque modo di distribuire frazioni di lavori che pareggi i carichi a $9$ è ottimo. L'ottimo intero è $9$.
Euristica di arrotondamento su $P\,||\,C_{\max}$: nella soluzione del rilassamento lineare il lavoro $3$ ha $\tilde x_{32}=\tilde x_{33}=\frac12$ (macchine $2$ e $3$), e si arrotonda con $[v]=\lfloor v+\frac12\rfloor$. Che cosa succede?
Il makespan arrotondato diventa $10$
Il lavoro $3$ va su due macchine: l'assegnamento è violato
Il lavoro $3$ resta senza macchina
Il lavoro $3$ va sulla macchina $2$, e la soluzione è ammissibile
Spiegazione. $[\frac12]=1$ per entrambe: $\bar x_{31}+\bar x_{32}+\bar x_{33}=2\neq1$, e l'arrotondamento fallisce.
L'arrotondamento della soluzione LP funziona sullo zaino ma fallisce sul bin packing e su $P\,||\,C_{\max}$. Perché?
Il LP spezza gli oggetti: arrotondare viola gli assegnamenti
Perché il LP del bin packing è sempre inammissibile
Perché i pesi del bin packing non sono interi
Perché lo zaino ha soltanto variabili continue
Spiegazione. Sullo zaino, un solo vincolo di packing con coefficienti non negativi, l'arrotondamento per difetto è sicuro; i vincoli di assegnamento $\sum_bx_{jb}=1$ sono quasi sempre violati da arrotondamenti indipendenti.
Fractional diving sullo zaino ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$, ottimo $\{1,2\}$ di profitto $17$): dal LP $\tilde{\vet x}=(1,\frac14,1,0)$ fissa $x_2:=[\frac14]=0$, poi $x_4:=0$, e termina con $\{1,3\}$, di profitto $16$. Che cosa mostra?
Fissare $x_2:=0$ è sempre la scelta giusta per il diving
Il diving trova sempre la soluzione ottima dell'istanza
Il rilassamento lineare dello zaino è inammissibile
La prima decisione era sbagliata: il ramo $x_2=1$ conteneva l'ottimo
Spiegazione. Il diving non torna indietro: una variabile fissata male non si recupera. Il ramo abbandonato al primo passo conteneva $\{1,2\}$.
Guided diving su $P\,||\,C_{\max}$: si fissa la variabile frazionaria più vicina all'incumbent, al valore dell'incumbent. Variabili frazionarie $\tilde x_{21}=\frac35$, $\tilde x_{23}=\frac25$, $\tilde x_{32}=\frac12$, $\tilde x_{33}=\frac12$; incumbent $\bar x_{21}=\bar x_{23}=\bar x_{32}=0$, $\bar x_{33}=1$. Quale fissaggio?
$x_{33}:=1$
$x_{32}:=0$
$x_{23}:=0$
$x_{21}:=1$
Spiegazione. Distanze dall'incumbent: $\frac35$, $\frac25$, $\frac12$, $\frac12$: la minima è quella di $x_{23}$, che si fissa al valore dell'incumbent, $0$.
La feasibility pump alterna la proiezione sul LP (minimizzando la distanza $\Delta$ dal punto intero corrente) e l'arrotondamento. Su $P\,||\,C_{\max}$ (ottimo $9$) trova in due proiezioni una soluzione di makespan $11$, come $LPT$. Perché non meglio?
Perché la pump riparte dalla soluzione di $LPT$
La distanza guarda gli assegnamenti, non i carichi
Perché la pump fallisce sempre su $P\,||\,C_{\max}$
Perché la proiezione massimizza il makespan
Spiegazione. La pump cerca una soluzione ammissibile, non buona: $C_{\max}$ è continua e non compare nella distanza. Per $P\,||\,C_{\max}$ l'ammissibilità non era difficile.
Feasibility pump sul bin packing ($c=7$, ottimo $3$): con un seme apre $5$ contenitori, due dei quali vuoti, anche se gli oggetti sono distribuiti in modo ottimo in $3$ contenitori. Perché la soluzione vale $5$?
Nulla nella distanza chiede di chiudere i contenitori vuoti
Perché il seme scelto rende inammissibile il LP
Perché i contenitori vuoti violano la capacità
Perché la pump non può produrre soluzioni ammissibili
Spiegazione. La pump minimizza la distanza da un punto intero, non $\sum_by_b$: un $y_b=1$ su un contenitore vuoto resta. Solo con un seme su dieci la soluzione è ottima.
RINS, local branching e proximity search partono da un incumbent $\bar{\vet x}$ e risolvono un sotto-MIP con un vincolo di cutoff. Che cosa li distingue?
Tutti e tre minimizzano $\Delta$, con cutoff diversi
RINS minimizza $\Delta$; LB fissa dove LP e incumbent concordano; PS impone $\Delta\le k$
Il local branching sullo zaino 0/1 risolve un sotto-MIP con il vincolo $\Delta(\vet x,\bar{\vet x})\le k$ (al più $k$ componenti binarie diverse dall'incumbent). A quali intorni della ricerca locale corrispondono $k=1$ e $k=2$?
$k=1$: move; $k=2$: 2-opt
$k=1$ e $k=2$: entrambi solo flip
$k=1$: flip; $k=2$: contiene anche lo swap
$k=1$: swap; $k=2$: contiene anche il flip
Spiegazione. Un flip cambia una componente, uno swap due. Per gli assegnamenti di $P\,||\,C_{\max}$, invece, $\Delta\le2$ è l'intorno move.
RINS sullo zaino ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$): incumbent $(1,0,1,0)$ di profitto $16$, soluzione LP $(1,\frac14,1,0)$. Si fissano $x_1=1$, $x_3=1$, $x_4=0$ e si impone profitto almeno $17$. Che cosa restituisce RINS, e perché?
Nessuna soluzione: RINS non si applica allo zaino
L'incumbent: con $x_3=1$ fissata, il sotto-MIP è inammissibile
$\{1,2\}$, perché il sotto-MIP pone $x_2=1$
$\{1,2,3\}$, perché il cutoff è soddisfatto
Spiegazione. La capacità richiede $x_2=0$, il cutoff $x_2=1$. L'ottimo $\{1,2\}$ ha $x_3=0$, ma $x_3$ è fissata perché LP e incumbent concordano.
RINS su $P\,||\,C_{\max}$ dall'incumbent di $LPT$ (makespan $11$): incumbent e soluzione LP concordano solo su $8$ delle $21$ variabili binarie, e il sotto-MIP con cutoff $C_{\max}\le10$ trova l'ottimo $9$. Sullo zaino, invece, RINS non migliorava. Che cosa mostra il confronto?
Con incumbent e LP diversi l'intorno di RINS è grande
Fissare più variabili rende RINS più efficace
Il cutoff $C_{\max}\le10$ basta a trovare l'ottimo
RINS funziona solo sui problemi di minimo
Spiegazione. Sullo zaino le due soluzioni erano troppo simili e restava una sola variabile libera; qui ne restano $13$, abbastanza per contenere l'ottimo.
Proximity search su $P\,||\,C_{\max}$ dall'incumbent di $LPT$: con cutoff $C_{\max}\le10$ la soluzione più vicina è a distanza $\Delta=4$ (makespan $10$), con $C_{\max}\le9$ di nuovo a distanza $4$ (makespan $9$), con $C_{\max}\le8$ il sotto-MIP è inammissibile. Che cosa significano $\Delta=4$ e l'ultima inammissibilità?
Quattro macchine usate; il makespan $9$ è ottimo
Quattro lavori riassegnati; il makespan $8$ è ottimo
Due lavori riassegnati; la ricerca è fallita
Due lavori riassegnati; il makespan $9$ è ottimo
Spiegazione. Per gli assegnamenti $\Delta=2r$, con $r$ lavori che cambiano macchina. Con obiettivo intero e $\theta=1$, un sotto-MIP inammissibile dimostra che l'incumbent è ottimo.
Proximity search sullo zaino ($c=9$, $p=(10,7,6,4)$, $w=(5,4,3,3)$) dall'incumbent $(1,0,1,0)$ di profitto $16$: il sotto-MIP cerca la soluzione più vicina (distanza $\Delta=\sum_j|x_j-\bar x_j|$) di profitto almeno $17$. Quale trova, e a che distanza?
$(1,1,0,0)$, a distanza $1$
$(0,1,1,1)$, a distanza $3$
$(1,1,0,0)$, a distanza $2$
$(1,1,1,0)$, a distanza $1$
Spiegazione. Esce l'oggetto $3$ ed entra l'oggetto $2$: due componenti cambiano, peso $9$, profitto $17$. $(1,1,1,0)$ e $(0,1,1,1)$ superano la capacità.
Relax-and-fix su un lot sizing capacitato (ottimo $160$, con setup nei periodi $1,2,5$): al passo $2$, con i setup futuri rilassati, $y_2=0$ costa $132.38$ e $y_2=1$ costa $142.38$, quindi fissa $y_2:=0$; poi la capacità impone un setup nel periodo $3$, e il risultato vale $170$. Che cosa mostra?
Fissare $y_2:=0$ è sempre la scelta giusta
Decisione miope: i setup futuri, rilassati, sembrano economici
Il relax-and-fix trova sempre la soluzione ottima
Il rilassamento lineare del lot sizing è forte
Spiegazione. Il rilassamento aveva pagato il setup del periodo $3$ solo per una frazione $0.143$; quando diventa intero, il risparmio del periodo $2$ si rivela un errore.
Fix-and-optimize sul lot sizing capacitato parte dalla soluzione di relax-and-fix (setup nei periodi $1,3,5$, costo $170$) e riottimizza le finestre $\{y_t,y_{t+1}\}$ con gli altri setup fissati: la finestra $\{y_2,y_3\}$ sposta il setup dal periodo $3$ al $2$ e porta il costo a $160$, l'ottimo. Che cosa mostra?
Bin packing con $60$ oggetti (lower bound $23$, FFD $24$) risolto con Gurobi: con i parametri di default l'ottimo $23$ arriva dopo $2533$ nodi; con più sforzo sulle euristiche si trova $23$ alla radice, circa $30$ volte prima; senza euristiche non si trova entro il limite. Il bound vale $23$ già alla radice. Che cosa mostra?
Il branch-and-bound non serve mai sul bin packing
La difficoltà è dimostrare il bound $23$
Le euristiche del solver rallentano sempre la soluzione
La difficoltà è primale: contano euristiche e MIP start
Spiegazione. Con un bound forte, il tempo di soluzione è il tempo per trovare una buona soluzione. Una sola istanza non dimostra nulla in generale: la lezione è qualitativa.
Negli esperimenti con Gurobi del capitolo sulle euristiche PLI si fissa un limite in «work unit» invece che in secondi. Perché?
Perché un work unit conta i nodi esplorati
Perché così il solver usa più thread in parallelo
Misura deterministica dello sforzo, quindi riproducibile
Perché i secondi non si possono misurare con precisione
Spiegazione. Il tempo in secondi dipende dalla macchina e dal carico; il work unit misura lo sforzo di calcolo in modo deterministico (circa un secondo ciascuno).
Lot sizing capacitato: relax-and-fix dà $170$ con bound LP $102.38$ (gap $66\%$); fix-and-optimize dà $160$. Che cosa chiude il gap e dimostra che $160$ è ottimo?
Un secondo passaggio completo di relax-and-fix
Il branch-and-bound del solver, perché il bound LP è debole
Il bound del rilassamento lineare arrotondato per eccesso
Il fatto che il fix-and-optimize si fermi
Spiegazione. Qui il rilassamento lineare è debole; il bound duale del branch-and-bound sale fino a $160$. Che un'euristica si fermi non dimostra nulla.
Bin packing con $60$ oggetti: FFD usa $24$ contenitori e il lower bound è $\lceil2271/100\rceil=23$. Quanto vale il gap relativo $(\mathscr{A}(I)-\mathrm{LB})/\mathrm{LB}$ della soluzione di FFD?
Circa $4.3\%$
Circa $1\%$
$0\%$
Circa $4.2\%$
Spiegazione. $(24-23)/23\approx4.3\%$; $4.2\%$ divide per $24$. Gurobi trova $23$ e chiude il gap a $0\%$.
Nelle euristiche basate sulla programmazione lineare intera (MIP) si indicano con $\tilde{\vet x}$ una soluzione ottima del rilassamento lineare e con $\bar{\vet x}$ la soluzione incumbent. Che cos'è l'incumbent?
La soluzione del rilassamento lineare arrotondata
Il bound duale corrente del branch-and-bound
La prima soluzione frazionaria trovata dal simplesso
La migliore soluzione ammissibile intera trovata finora
Spiegazione. L'incumbent è un bound primale: le euristiche di miglioramento (RINS, local branching, proximity search) partono da $\bar{\vet x}$ e cercano una soluzione migliore vicina.
Quale vantaggio hanno le euristiche basate sulla programmazione lineare intera (MIP) rispetto alle euristiche specifiche di un problema?
Sono sempre più veloci delle euristiche costruttive
Garantiscono sempre l'ottimo in tempo polinomiale
Usano solo il modello, quindi si applicano a ogni problema formulato, e il rilassamento dà anche un bound duale
Non hanno bisogno di un modello del problema
Spiegazione. Lavorano su variabili e vincoli del modello, non sulla struttura del problema; il rilassamento lineare (e il branch-and-bound del solutore) dà l'altro lato del gap.
Sulle istanze di riferimento dello zaino, del bin packing, del TSP e di $P\,||\,C_{\max}$, il valore del rilassamento lineare arrotondato nel verso del bound (per difetto nel massimo, per eccesso nel minimo) coincide con il valore ottimo. Che cosa significa per le euristiche MIP?
Le euristiche sono inutili, perché il rilassamento è già intero
I rilassamenti sono forti: trovare una buona soluzione è la parte difficile, e il bound arrotondato può dimostrarne l'ottimalità
Il rilassamento non serve, perché è sempre debole
Le istanze sono sbagliate, perché un rilassamento non è mai esatto
Spiegazione. Quando il bound è già stretto, il problema pratico è trovare una soluzione intera di quel valore: è la situazione tipica in cui le euristiche MIP sono utili.
Nell'euristica di arrotondamento si arrotonda la soluzione del rilassamento lineare all'intero più vicino. Perché per lo zaino 0-1 ($\max\sum p_jx_j$, un solo vincolo $\sum w_jx_j\le c$, pesi non negativi) arrotondare per difetto è sempre ammissibile?
Abbassare le $x_j$ non aumenta mai il peso, quindi il vincolo resta soddisfatto
Perché l'oggetto critico ha sempre $x_s=0$
Perché il rilassamento ha sempre soluzione intera
Perché arrotondare per difetto dà sempre la soluzione ottima
Spiegazione. Con coefficienti non negativi in un vincolo di tipo $\le$, ridurre le variabili mantiene l'ammissibilità; nel bin packing e in $P\,||\,C_{\max}$ i vincoli di assegnamento sono uguaglianze e l'arrotondamento fallisce.
Lo zaino 0-1 con $c=9$ ha rilassamento lineare $\tilde x=(1,1,0{,}25,0)$ (oggetti per efficienza non crescente, pesi $w=(5,4,4,3)$). Che cosa danno l'arrotondamento all'intero più vicino e quello per difetto?
$(1,1,1,0)$, di peso $13$: inammissibile
$(1,1,0,1)$, di peso $12$: inammissibile
$(0,0,0,0)$: si perde tutto
Entrambi $(1,1,0,0)$, di peso $9$: ammissibile
Spiegazione. $0{,}25$ si arrotonda a $0$ in entrambi i casi, e le variabili intere restano: il punto $(1,1,0,0)$ pesa $5+4=9\le c$.
Nel diving si fissa una variabile frazionaria alla volta e si risolve di nuovo il rilassamento lineare. Che differenza c'è fra fractional diving e guided diving?
Fractional esplora tutto l'albero; guided un solo cammino
Fractional usa l'incumbent; guided usa solo il rilassamento
Fractional fissa la variabile meno frazionaria al suo intero più vicino; guided fissa quella più vicina al valore nell'incumbent, a quel valore
Fractional fissa la variabile più frazionaria a $1$; guided fissa una variabile a caso
Spiegazione. Entrambi percorrono un solo cammino nell'albero di branch-and-bound; guided diving usa una soluzione nota per scegliere la direzione.
Nel diving su $P\,||\,C_{\max}$ il valore del rilassamento lineare resta uguale per molti fissaggi successivi. Perché?
Perché il diving non risolve più il rilassamento dopo il primo fissaggio
Il rilassamento ha moltissime soluzioni ottime: fissare una variabile sposta il punto su un'altra di valore uguale
Perché il makespan è una variabile intera
Perché ogni fissaggio rende il rilassamento inammissibile
Spiegazione. Il rilassamento divide i lavori fra le macchine e vale $\sum_j t_j/m$ in molti modi: il suo valore non dice nulla sulla qualità del cammino finché i fissaggi non vincolano i carichi.
La feasibility pump alterna la proiezione di un punto intero sulla regione del rilassamento lineare (un LP che minimizza la distanza $\Delta$) e l'arrotondamento della proiezione. Qual è il suo scopo?
Trovare una prima soluzione ammissibile; la qualità è compito dei metodi di miglioramento
Migliorare un incumbent già noto
Trovare la soluzione ottima con una sola proiezione
Calcolare un bound duale migliore del rilassamento
Spiegazione. La pompa ignora quasi del tutto l'obiettivo: cerca un punto intero e ammissibile. Le euristiche come RINS o proximity search partono poi da quella soluzione.
Nella feasibility pump, la distanza fra un punto binario arrotondato $\hat{\vet x}$ e un punto $\vet x$ del rilassamento è $\Delta(\vet x,\hat{\vet x})=\sum_{j:\hat x_j=0}x_j+\sum_{j:\hat x_j=1}(1-x_j)$. Quanto vale per $\hat{\vet x}=(1,0,1)$ e $\vet x=(0{,}8,\ 0{,}3,\ 0{,}5)$?
$1{,}6$
$0{,}4$
$0{,}7$
$1$
Spiegazione. $(1-0{,}8)+0{,}3+(1-0{,}5)=0{,}2+0{,}3+0{,}5=1$. Se $\Delta=0$ il punto del rilassamento è intero e la pompa ha trovato una soluzione ammissibile.
Nel local branching per lo zaino 0-1 si risolve il sotto-MIP con il vincolo $\Delta(\vet x,\bar{\vet x})\le k$, dove $\Delta$ conta le componenti binarie diverse dall'incumbent $\bar{\vet x}$. A quale intorno della ricerca locale corrisponde con $k=1$?
A tutto lo spazio $\{0,1\}^n$
A nessun intorno: il sotto-MIP è vuoto
All'intorno flip, che aggiunge o toglie un oggetto
All'intorno swap, che scambia un oggetto dentro con uno fuori
Spiegazione. Una sola componente diversa vuol dire cambiare un oggetto; con $k=2$ si ottengono anche gli swap. Il solutore esplora l'intorno in modo esatto.
Nella proximity search, per un problema di minimo con obiettivo a valori interi, si risolve un sotto-MIP con il vincolo $f(\vet x)\le f(\bar{\vet x})-\theta$, con $\theta=1$, minimizzando la distanza dall'incumbent $\bar{\vet x}$. Che cosa si conclude se il sotto-MIP è inammissibile?
L'incumbent è inammissibile
L'incumbent è ottimo: nessuna soluzione ha valore almeno $1$ più basso
Bisogna aumentare $\theta$ per trovare una soluzione
Il rilassamento lineare è illimitato
Spiegazione. Con valori interi, una soluzione migliore avrebbe $f(\vet x)\le f(\bar{\vet x})-1$; se non esiste, $\bar{\vet x}$ è ottimo. La prova viene dal solutore, che dimostra l'inammissibilità con i suoi bound.
Nel relax-and-fix per il lot sizing, le variabili di setup $y_t$ si dividono in blocchi di periodi consecutivi. Come procede il metodo?
Risolve un MIP con il primo blocco binario e gli altri rilassati, fissa il primo blocco, poi passa al blocco successivo
Risolve ogni blocco come un problema indipendente, senza le scorte
Risolve il rilassamento lineare una volta e arrotonda tutti i blocchi insieme
Fissa tutti i setup a $1$ e ottimizza le quantità
Spiegazione. Ogni sotto-MIP ha pochi binari; le decisioni dei blocchi già fissati restano, e quelle future sono solo rilassate. Fix-and-optimize migliora poi la soluzione liberando un blocco alla volta.
Nel lot sizing con capacità, perché nelle euristiche MIP le decisioni difficili sono solo le $m$ variabili di setup $y_t$?
Perché le quantità prodotte sono sempre uguali alle domande
Perché le scorte sono sempre nulle in un piano ottimo
Perché il rilassamento lineare è esatto anche con i setup frazionari
Fissati i setup, il resto è un LP con matrice di rete e dati interi, che ha una soluzione ottima intera
Spiegazione. Con $y$ fissato restano i vincoli di bilancio e di capacità, una struttura di flusso: il simplesso dà quantità intere. Il rilassamento con $y$ frazionari è invece debole.
I solutori MIP moderni, come Gurobi, eseguono molte euristiche durante il branch-and-bound e accettano una soluzione iniziale (MIP start). A che cosa serve fornire un MIP start?
Garantisce che il solutore restituisca proprio quella soluzione
Disattiva le euristiche interne del solutore
Dà subito un incumbent: il solutore pota i nodi con bound peggiore e parte con un gap finito
Sostituisce il rilassamento lineare alla radice
Spiegazione. Un buon incumbent iniziale permette di potare per bound fin dall'inizio; il solutore può comunque trovarne di migliori.
Si confrontano le euristiche interne di un solutore MIP su una singola istanza e si osserva che una impostazione dei parametri trova prima la soluzione ottima. Che cosa se ne può concludere?
Che quell'impostazione è la migliore per ogni istanza
Poco: i risultati dipendono da istanza, versione del solutore e macchina, e una sola istanza non dimostra nulla
Che le altre impostazioni sono sbagliate
Che il solutore è esatto solo con quell'impostazione
Spiegazione. Come per ogni euristica, i confronti richiedono molte istanze e condizioni uguali; il tempo per trovare l'ottimo varia molto da un'istanza all'altra.
Le euristiche costruttive, la ricerca locale e le metaeuristiche danno solo un bound primale. Che cosa aggiungono le euristiche MIP eseguite dentro un solutore?
Un bound duale dal rilassamento e dal branch-and-bound, quindi un gap e a volte la prova di ottimalità
Un tempo di calcolo polinomiale garantito
Una garanzia di approssimazione costante
Soluzioni sempre migliori di quelle delle metaeuristiche
Spiegazione. Con il modello arriva il suo rilassamento: per lo zaino di riferimento $\lfloor 17{,}75\rfloor=17$, e una soluzione di valore $17$ è quindi ottima.
Per uno zaino 0-1 con profitti interi, il rilassamento lineare vale $17{,}75$ e un'euristica MIP trova una soluzione di valore $17$. Che cosa si può concludere?
La soluzione dista $0{,}75$ dall'ottimo
Serve un'altra euristica per sapere se è ottima
L'ottimo è $18$, l'arrotondamento per eccesso del rilassamento
La soluzione è ottima, perché $\lfloor 17{,}75\rfloor=17$ è un upper bound
Spiegazione. Con profitti interi ogni soluzione ha valore intero e al più $17{,}75$, quindi al più $17$: la soluzione trovata raggiunge il bound.
Nel modello del bin packing usato dalle euristiche MIP ci sono $m$ contenitori disponibili, con variabili $x_{jb}$ e $y_b$. Quale valore di $m$ è sempre valido, e quale si usa sull'istanza di riferimento con $n=6$ oggetti?
$m=1$, perché i contenitori si aggiungono durante la ricerca
$m=2n$, per avere margine; sull'istanza $m=12$
$m=n$, sempre valido: un contenitore per oggetto; sull'istanza si usa $m=6$
$m=\lceil\sum_j w_j/c\rceil$, sempre valido; sull'istanza $m=3$
Spiegazione. Con $m=n$ c'è sempre una soluzione (un oggetto per contenitore). Il bound sul peso è un lower bound: se fosse minore dell'ottimo, il modello non avrebbe soluzioni.
Nel modello di $P\,||\,C_{\max}$ con variabili binarie $x_{jh}$ (lavoro $j$ sulla macchina $h$), la distanza fra due assegnamenti ammissibili è $\Delta(\vet x,\bar{\vet x})=\sum_{(j,h):\bar x_{jh}=1}(1-x_{jh})+\sum_{(j,h):\bar x_{jh}=0}x_{jh}$. Se $r$ lavori cambiano macchina, quanto vale $\Delta$, e perché?
$r^2$: ogni coppia di lavori spostati conta una volta
$2r$: ogni lavoro spostato lascia uno $0$ dove $\bar x$ ha $1$ e mette un $1$ dove $\bar x$ ha $0$
$r$: ogni lavoro spostato cambia una componente
$rm$: ogni lavoro spostato cambia tutte le sue $m$ componenti
Spiegazione. Un lavoro sulla stessa macchina contribuisce $0$; uno spostato dalla macchina $h$ alla $h'$ contribuisce $1$ per $h$ e $1$ per $h'$. Per questo $\Delta\le 2$ è l'intorno move della ricerca locale.
Un'euristica basata sulla PLI (matheuristica) per un problema con un modello MIP, che cosa usa per cercare una soluzione ammissibile, a differenza delle metaeuristiche?
Il rilassamento lineare del modello e un solver MIP
Solo mosse di ricerca locale
Solo una costruzione greedy
Una popolazione di soluzioni
Spiegazione. Le matheuristiche (rounding, diving, feasibility pump, RINS, local branching, ...) sfruttano il modello; le metaeuristiche manipolano solo soluzioni.
Nel modello PLI di $P\,||\,C_{\max}$ con variabili binarie $x_{jh}$ (lavoro $j$ sulla macchina $h$) e $C_{\max}$, quale variabile è continua, e che valore assume dato l'assegnamento?
Tutte le $x_{jh}$; $C_{\max}$ è intera
Nessuna: il modello è puramente binario
Solo $C_{\max}$; vale la media dei carichi
Solo $C_{\max}$; vale il carico massimo $\max_h\sum_jt_jx_{jh}$
Spiegazione. I vincoli $C_{\max}\ge\sum_jt_jx_{jh}$ per ogni macchina e la minimizzazione portano $C_{\max}$ al carico massimo.
RINS, local branching e proximity search risolvono un sotto-MIP a partire da una soluzione incumbent $\bar{\vet x}$, con il vincolo di cutoff $f(\vet x)\le f(\bar{\vet x})-\theta$ (problema di minimo). Perché si può porre $\theta=1$ sulle istanze del capitolo?
Perché il cutoff è facoltativo
Perché $\theta$ deve essere sempre $1$
Perché i valori obiettivo sono interi: una soluzione migliore vale almeno $1$ in meno
Perché il sotto-MIP ha una sola variabile
Spiegazione. Con obiettivo intero, migliorare significa scendere almeno di $1$; il cutoff esclude le soluzioni che non migliorano l'incumbent.
Nel modello $\mathrm{ILP}_{\mathrm{KP}}$ dello zaino 0/1 ($\max\sum_jp_jx_j$, $\sum_jw_jx_j\le c$, $x_j\in\{0,1\}$), perché arrotondare per difetto una soluzione del rilassamento lineare dà sempre una soluzione ammissibile?
Perché l'arrotondamento per eccesso è inammissibile
Diminuire le variabili non aumenta il peso, e i pesi sono non negativi: il vincolo $\le c$ resta soddisfatto
Non è vero: può superare la capacità
Perché il rilassamento lineare ha sempre soluzione intera
Spiegazione. Con vincoli di tipo $\le$ a coefficienti non negativi, arrotondare per difetto è sicuro; nel KP la soluzione arrotondata toglie solo l'oggetto critico.
Il modello $\mathrm{ILP}_{\mathrm{TSP}}^{\mathrm{DFJ}}$ usa le variabili di arco $x_{ij}$, i vincoli di grado e i vincoli di eliminazione dei sottogiri. Perché arrotondare una soluzione frazionaria del rilassamento raramente dà un giro?
Il vettore arrotondato può violare i vincoli di grado o formare sottogiri: l'ammissibilità del TSP non si conserva arrotondando
Perché il rilassamento del DFJ è sempre intero
Perché le distanze sono intere
Perché il TSP non ha vincoli
Spiegazione. A differenza del KP, i vincoli di uguaglianza e di connessione del TSP si rompono facilmente; servono euristiche MIP più strutturate (diving, feasibility pump, sotto-MIP).
Su un'istanza dello zaino 0/1 ($c=9$, $p=(6,5,8,9,6,7)$, $w=(2,3,6,7,5,9)$) il rilassamento lineare vale $\frac{49}{3}$ e l'ottimo $15$. La soluzione del rilassamento è intera?
Sì: il rilassamento dello zaino è sempre intero
Sì, e coincide con l'ottimo
No, perché tutte le variabili sono frazionarie
No: l'oggetto critico $3$ è preso per $\frac23$, e il gap con l'ottimo è $\frac{49}{3}-15=\frac43$
Spiegazione. La soluzione di Dantzig ha al più una variabile frazionaria, qui $x_3=\frac46=\frac23$; le euristiche MIP partono da questa soluzione per trovare soluzioni intere.
Local branching per $P\,||\,C_{\max}$ (variabili binarie $x_{jh}$) aggiunge il vincolo $\Delta(\vet x,\bar{\vet x})\le 2$, con $\bar{\vet x}$ l'incumbent. Quali assegnamenti restano ammissibili per il sotto-MIP?
Solo l'incumbent $\bar{\vet x}$
Quelli che scambiano due lavori
Quelli che spostano al più un lavoro
Quelli che spostano al più due lavori
Spiegazione. Per due assegnamenti $\Delta=2r$, con $r$ il numero di lavori su macchine diverse: $\Delta\le2$ vuol dire $r\le1$, cioè l'intorno move. Uno scambio sposta due lavori ($\Delta=4$).
Relax-and-fix risolve una sequenza di MIP: le variabili del blocco corrente sono intere, quelle dei blocchi precedenti fissate, quelle dei successivi rilassate. Quale affermazione vale?
Ha bisogno di una soluzione ammissibile di partenza
Può finire senza soluzione: non rivede le fissazioni
Trova sempre una soluzione ottima del MIP
Risolve solo problemi di programmazione lineare
Spiegazione. Le variabili fissate nei primi blocchi non cambiano più: una scelta sbagliata può rendere non ammissibili i blocchi successivi (o dare una soluzione non ottima). Parte dal rilassamento, non da un incumbent.
La feasibility pump alterna un arrotondamento e un problema lineare che minimizza la distanza $\Delta(\vet x,\bar{\vet x})$ dal punto arrotondato $\bar{\vet x}$. Quando si ferma con successo?
Quando la soluzione del problema lineare è intera
Quando la distanza aumenta fra due iterazioni
Subito dopo il primo arrotondamento
Quando il problema lineare non è ammissibile
Spiegazione. Distanza nulla vuol dire che il punto ammissibile per il rilassamento coincide con un punto intero: è una soluzione ammissibile del MIP. Il metodo cerca l'ammissibilità, non l'ottimo.
Il diving fissa a ogni passo una variabile frazionaria e risolve di nuovo il rilassamento lineare. Quale esito è possibile?
Trova sempre una soluzione ammissibile
Dimostra l'ottimalità della soluzione
Non fissa mai una variabile a $0$
Il rilassamento diventa non ammissibile
Spiegazione. Il diving è un tuffo in un solo ramo dell'albero, senza tornare indietro: una sequenza di fissazioni può svuotare la regione ammissibile. Non dà un bound per dimostrare l'ottimo.
Problema di minimo con obiettivo intero: un'euristica MIP si ferma con l'incumbent di valore $18$ e il rilassamento lineare vale $17$. Che cosa si conclude?
Il valore ottimo è $17$
Il gap è nullo: $18$ è ottimo
Il valore ottimo è $17$ o $18$
Il valore ottimo è $18$
Spiegazione. $17\le z(I)\le18$ e $z(I)$ è intero: resta il dubbio fra i due valori. Il gap è $\frac{18-17}{17}\approx5{,}9\%$; per chiuderlo serve un bound migliore o la prova dell'ottimo.
Arrotondare per difetto una soluzione del rilassamento lineare dà una soluzione ammissibile per lo zaino 0/1. Per quale modello invece non lo garantisce?
Lo zaino 0/1 con capacità grande
Il bin packing, con $\sum_bx_{jb}=1$ per ogni oggetto
Lo zaino 0/1 con dati interi
Ogni modello con vincoli $\le$ a coefficienti non negativi
Spiegazione. Con vincoli $\le$, coefficienti e termini noti non negativi, diminuire le variabili non viola nulla. Nel bin packing un oggetto frazionato in due contenitori, arrotondato per difetto, non è più assegnato.
RINS fissa le variabili che hanno lo stesso valore nell'incumbent $\bar{\vet x}$ e nella soluzione $\tilde{\vet x}$ del rilassamento, e risolve il sotto-MIP sulle altre. Che cosa le serve?
Un incumbent e una soluzione del rilassamento
Solo la soluzione del rilassamento
Un bound duale uguale all'incumbent
Una soluzione del rilassamento intera
Spiegazione. Il confronto fra $\bar{\vet x}$ e $\tilde{\vet x}$ richiede tutte e due; se $\tilde{\vet x}$ fosse intera il problema sarebbe già risolto, e un bound uguale all'incumbent lo dimostrerebbe ottimo.
Che cosa usa, per definizione, un'euristica basata sulla PLI (matheuristic)?
Un intorno definito sulle permutazioni
Una popolazione di soluzioni da incrociare
Solo regole costruttive di tipo greedy
Il rilassamento lineare del modello e un solver MIP
Spiegazione. Un'euristica MIP lavora sul modello del problema, attraverso il suo rilassamento lineare e un solver MIP; le euristiche costruttive, la ricerca locale e le metaeuristiche lavorano su una rappresentazione delle soluzioni.
Local branching con il vincolo $\Delta(\vet x,\bar{\vet x})\le k$ esplora le soluzioni vicine all'incumbent. Che cosa succede se $k$ è troppo piccolo?
La soluzione trovata non è ammissibile
Serve un rilassamento più forte
Il sotto-MIP può non contenere soluzioni migliori
Il sotto-MIP diventa grande come il MIP
Spiegazione. Con $k$ piccolo il sotto-MIP è facile ma l'intorno è piccolo: può contenere solo soluzioni non migliori dell'incumbent. Con $k$ grande si avvicina al MIP intero, che è difficile.
Una soluzione euristica passata al solver come MIP start a che cosa serve nel branch-and-bound?
Riduce il numero delle variabili
Dà subito un incumbent per potare i nodi
Dà un bound duale migliore
Rafforza il rilassamento lineare
Spiegazione. Il MIP start è un bound primale: i nodi con bound del rilassamento non migliore dell'incumbent si potano. Il bound duale viene dai rilassamenti, non dalle soluzioni ammissibili.
Per variabili binarie la distanza $\Delta(\vet x,\bar{\vet x})=\sum_j|x_j-\bar x_j|$ da un punto $\bar{\vet x}\in\{0,1\}^n$ si scrive in modo lineare come:
Spiegazione. Se $\bar x_j=0$ allora $|x_j-0|=x_j$, se $\bar x_j=1$ allora $|x_j-1|=1-x_j$ (con $0\le x_j\le1$); la somma dei prodotti conta invece gli accordi, $n-\Delta$. È la forma usata dalla feasibility pump, dal local branching e dalla proximity search.
La proximity search sostituisce l'obiettivo con la distanza $\Delta(\vet x,\bar{\vet x})$ e aggiunge $f(\vet x)\le f(\bar{\vet x})-\theta$. Perché le serve un incumbent?
Serve a ottenere un bound duale del problema
Il vincolo e la distanza usano $\bar{\vet x}$
Serve a risolvere il rilassamento lineare
Serve a fissare variabili come in RINS
Spiegazione. Sia il nuovo obiettivo sia il vincolo di miglioramento dipendono dall'incumbent $\bar{\vet x}$: senza una soluzione ammissibile il metodo non parte. Non fissa variabili e non dà bound duali.
Fix-and-optimize migliora una soluzione riottimizzando un blocco di variabili alla volta, con le altre fissate. Che cosa le serve che a relax-and-fix non serve?
Una soluzione ammissibile di partenza
Il rilassamento lineare del modello intero
Un solver MIP per risolvere i sotto-problemi
Una funzione obiettivo a valori tutti interi
Spiegazione. Fix-and-optimize fissa le variabili fuori dal blocco ai valori di una soluzione ammissibile, che quindi deve esistere; relax-and-fix parte dal rilassamento e costruisce la soluzione blocco per blocco.
Per lo zaino 0/1 arrotondare per difetto la soluzione del rilassamento dà una soluzione ammissibile. Perché l'arrotondamento all'intero più vicino $\lfloor x_j+\frac12\rfloor$ non lo garantisce?
La soluzione del rilassamento può essere intera
I profitti possono non essere interi
Cambia il segno della funzione obiettivo
Arrotondare per eccesso può superare la capacità
Spiegazione. Una variabile con $x_j\ge\frac12$ va a $1$ e il peso totale può superare $c$. Arrotondare per difetto solo diminuisce il peso, quindi resta ammissibile.
L'esperimento con i parametri delle euristiche di Gurobi usa un limite sul lavoro (work limit) invece che sul tempo. Perché?
Con il limite sul lavoro si trova l'ottimo
Il limite sul lavoro spegne le euristiche
Il lavoro è deterministico: corse riproducibili
Il limite sul tempo non esiste in gurobipy
Spiegazione. Il tempo dipende dal calcolatore e dal carico, il lavoro misurato dal solver no: con un solo thread le corse si ripetono uguali. Il limite non cambia che cosa fanno le euristiche.
Zaino 0/1: incumbent $\bar{\vet x}=(1,0,1,0)$ e soluzione del rilassamento $\tilde{\vet x}=(1,\frac14,1,0)$. Quali variabili restano libere nel sotto-MIP di RINS?
Solo $x_2$
$x_2$ e $x_4$
Tutte tranne $x_1$
Nessuna
Spiegazione. RINS fissa le variabili con lo stesso valore in $\bar{\vet x}$ e $\tilde{\vet x}$: $x_1=1$, $x_3=1$, $x_4=0$. Resta libera solo $x_2$, frazionaria nel rilassamento.
Local branching per lo zaino 0/1 con il vincolo $\Delta(\vet x,\bar{\vet x})\le1$. Quali soluzioni esplora il sotto-MIP?
Solo i vettori con un oggetto in più
Tutte le soluzioni ammissibili
I vettori che differiscono in due variabili
$\bar{\vet x}$ e i vettori a distanza $1$
Spiegazione. $\Delta\le1$ permette di cambiare al più una variabile: è l'intorno flip della ricerca locale (togliere o aggiungere un oggetto), più l'incumbent stesso.
Proximity search, problema di minimo: ogni sotto-MIP chiede $f(\vet x)\le f(\bar{\vet x})-\theta$. Di quanto migliora l'incumbent un'iterazione riuscita?
Fino al valore ottimo
Di al più $\theta$
Di almeno $\theta$
Di esattamente $1$
Spiegazione. La nuova soluzione soddisfa il vincolo di miglioramento, quindi vale al più $f(\bar{\vet x})-\theta$: il miglioramento è almeno $\theta$, e può essere maggiore.
Durante il diving di un problema di massimo, come cambia il valore del rilassamento lineare a ogni fissazione?
Aumenta di almeno $1$
Non aumenta mai
Non diminuisce mai
Resta sempre uguale
Spiegazione. Fissare una variabile aggiunge un vincolo al rilassamento: la regione si restringe e il valore ottimo di un problema di massimo non può crescere.
Relax-and-fix con un solo blocco che contiene tutte le variabili intere: che cosa risolve?
Il MIP intero, all'ottimo
Solo il rilassamento lineare
Un problema non ammissibile
Un sotto-MIP con le variabili fissate
Spiegazione. Con un blocco solo non c'è niente da rilassare né da fissare: il primo e unico sotto-problema è il MIP stesso. I blocchi servono a rendere i sotto-problemi più piccoli.
Perché fix-and-optimize non peggiora mai la soluzione corrente?
Perché risolve ogni volta il MIP intero
Perché rilassa i blocchi successivi
Perché accetta peggioramenti con una probabilità
La soluzione corrente è ammissibile per ogni sotto-MIP
Spiegazione. Le variabili fuori dal blocco sono fissate ai valori della soluzione corrente, che resta ammissibile per il sotto-MIP: l'ottimo del sotto-MIP è almeno buono quanto lei.
Che cosa deve soddisfare una soluzione passata al solver come MIP start per diventare subito l'incumbent?
Avere tutte le variabili a $0$
Avere valore uguale al bound duale
Essere ammissibile per il modello
Essere ottima per il rilassamento
Spiegazione. Il solver controlla il MIP start: se è ammissibile diventa l'incumbent (bound primale) e serve a potare; un punto non ammissibile non dà un bound primale.
In quale caso RINS non può dare una soluzione diversa dall'incumbent?
Se $\bar{\vet x}$ e $\tilde{\vet x}$ coincidono
Se il rilassamento ha una variabile frazionaria
Se l'incumbent è migliore del rilassamento
Se il problema è di massimo
Spiegazione. Se le due soluzioni coincidono, RINS fissa tutte le variabili intere ai valori dell'incumbent: il sotto-MIP non ha altre soluzioni (e $\tilde{\vet x}$ intera dimostra l'ottimo).
Come si scelgono i blocchi di variabili in fix-and-optimize?
Un solo blocco con tutte le variabili
Un blocco per ogni vincolo
A caso, ogni volta diversi
Piccoli, con sotto-MIP veloci
Spiegazione. Ogni blocco dà un sotto-MIP che il solver deve risolvere in fretta, ma un blocco troppo piccolo migliora poco: la scelta bilancia le due cose (per esempio, una finestra di periodi nel lot sizing).
Il diving può finire in un rilassamento non ammissibile. Perché non può tornare indietro come il branch-and-bound?
Perché il solver non lo permette
Perché non usa il rilassamento lineare
Segue un solo ramo, senza esplorare l'albero
Perché le variabili fissate sono continue
Spiegazione. Il diving è un'euristica: scende lungo un solo ramo dell'albero fissando variabili. Varianti con un piccolo backtracking esistono, ma il diving puro si ferma senza soluzione.
Domande generate (14)
Ogni generatore crea a ogni avvio un'istanza nuova, con numeri diversi: qui alcuni esempi.
1. Algoritmi euristici: definizioni (2)
Esempio 1 · eh-g-heur-gap · livello media · dispensa
TSP simmetrico con $5$ città e distanze $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 9 & 10 & 13 & 14\\ 2 & 9 & - & 3 & 13 & 10\\ 3 & 10 & 3 & - & 10 & 14\\ 4 & 13 & 13 & 10 & - & 2\\ 5 & 14 & 10 & 14 & 2 & -\end{array}$. Il nearest neighbour dalla città $1$ (ogni volta la città non visitata più vicina, a parità l'indice minore, poi ritorno in $1$) dà il giro $\mathscr{A}(I)$; il bound $\mathrm{LB}=\left\lceil\frac12\sum_i(a_i+b_i)\right\rceil$ usa le due distanze minime $a_i,b_i$ di ogni città. Quanto vale il gap $\frac{\mathscr{A}(I)-\mathrm{LB}}{\mathrm{LB}}$?
$\frac{2}{19}$
$4$
$\frac{2}{17}$
$\frac{19}{17}$
Spiegazione. $\mathscr{A}(I)=38$ e $\mathrm{LB}=34$: gap $\frac{2}{17}$. L'errore relativo del giro rispetto all'ottimo non supera questo valore.
Esempio 2 · eh-g-heur-gap · livello media · dispensa
TSP simmetrico con $5$ città e distanze $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 7 & 13 & 6 & 3\\ 2 & 7 & - & 7 & 14 & 13\\ 3 & 13 & 7 & - & 11 & 14\\ 4 & 6 & 14 & 11 & - & 12\\ 5 & 3 & 13 & 14 & 12 & -\end{array}$. Il nearest neighbour dalla città $1$ (ogni volta la città non visitata più vicina, a parità l'indice minore, poi ritorno in $1$) dà il giro $\mathscr{A}(I)$; il bound $\mathrm{LB}=\left\lceil\frac12\sum_i(a_i+b_i)\right\rceil$ usa le due distanze minime $a_i,b_i$ di ogni città. Quanto vale il gap $\frac{\mathscr{A}(I)-\mathrm{LB}}{\mathrm{LB}}$?
$\frac{3}{37}$
$\frac{3}{40}$
$\frac{40}{37}$
$3$
Spiegazione. $\mathscr{A}(I)=40$ e $\mathrm{LB}=37$: gap $\frac{3}{37}$. L'errore relativo del giro rispetto all'ottimo non supera questo valore.
Esempio 1 · eh-g-heur-flip · livello facile · dispensa
Zaino 0-1 con capacità $c=13$ e oggetti $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 9 & 4 & 10 & 8 & 6\\ w_j & 5 & 2 & 6 & 6 & 5\end{array}$. La soluzione corrente è $x=(1,0,0,1,0)$; l'intorno flip contiene le soluzioni ammissibili ottenute cambiando una sola componente di $x$ (aggiungere o togliere un oggetto). Quanto vale il miglior vicino?
$27$
$22$
$21$
$17$
Spiegazione. La soluzione corrente vale $17$ e pesa $11$; fra i vicini ammissibili il migliore vale $21$. Ignorando la capacità si arriverebbe a $27$, ma quel vicino non è ammissibile.
Esempio 2 · eh-g-heur-flip · livello facile · dispensa
Zaino 0-1 con capacità $c=10$ e oggetti $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 4 & 12 & 3 & 3 & 9\\ w_j & 2 & 6 & 6 & 4 & 3\end{array}$. La soluzione corrente è $x=(0,0,0,1,1)$; l'intorno flip contiene le soluzioni ammissibili ottenute cambiando una sola componente di $x$ (aggiungere o togliere un oggetto). Quanto vale il miglior vicino?
$16$
$12$
$17$
$24$
Spiegazione. La soluzione corrente vale $12$ e pesa $7$; fra i vicini ammissibili il migliore vale $16$. Ignorando la capacità si arriverebbe a $24$, ma quel vicino non è ammissibile.
2. Euristiche costruttive (5)
Esempio 1 · eh-g-bpp-ffd · livello facile · dispensa
Bin packing (BPP: oggetti in contenitori di capacità $c$, minimizzando i contenitori) con $c=11$ e pesi $w=(6,8,8,2,8,6,6)$ (oggetti $1,\dots,7$). L'ordinamento per peso non crescente rompe i pari merito con l'indice minore; i contenitori sono numerati nell'ordine di apertura. Quale vettore $bin$ (contenitore di ogni oggetto, nella numerazione originale) produce Best Fit Decreasing (BFD)?
$bin=(1,2,3,1,4,5,6)$
$bin=(4,1,2,4,3,5,6)$
$bin=(4,1,2,6,3,5,6)$
$bin=(4,1,2,1,3,5,6)$
Spiegazione. Prima si ordinano gli oggetti per peso non crescente ($2,3,5,1,6,7,4$), poi si applica Best Fit: $bin=(4,1,2,1,3,5,6)$, $6$ contenitori. Errori tipici: dimenticare l'ordinamento o usare l'altra regola di scelta.
Esempio 2 · eh-g-bpp-ffd · livello facile · dispensa
Bin packing (BPP: oggetti in contenitori di capacità $c$, minimizzando i contenitori) con $c=11$ e pesi $w=(8,4,2,5,8,8,7)$ (oggetti $1,\dots,7$). L'ordinamento per peso non crescente rompe i pari merito con l'indice minore; i contenitori sono numerati nell'ordine di apertura. Quale vettore $bin$ (contenitore di ogni oggetto, nella numerazione originale) produce Best Fit Decreasing (BFD)?
$bin=(1,4,1,5,2,3,4)$
$bin=(1,5,5,5,2,3,4)$
$bin=(1,2,1,2,3,4,5)$
$bin=(1,5,4,5,2,3,4)$
Spiegazione. Prima si ordinano gli oggetti per peso non crescente ($1,5,6,7,4,2,3$), poi si applica Best Fit: $bin=(1,4,1,5,2,3,4)$, $5$ contenitori. Errori tipici: dimenticare l'ordinamento o usare l'altra regola di scelta.
Esempio 1 · eh-g-vcp-gc · livello facile · dispensa
Grafo $G=(V,E)$ con $V=\{1,\dots,6\}$ e $E=\{\{1,3\},\{1,5\},\{2,3\},\{2,4\},\{2,5\},\{2,6\},\{4,5\},\{4,6\},\{5,6\}\}$. La colorazione greedy $GC$ esamina i vertici nell'ordine della lista $\lambda=(2,1,5,3,6,4)$ e dà a ciascuno il colore (intero $\ge 1$) più piccolo non usato dai vicini già colorati. Quale colorazione $col=(col[1],\dots,col[6])$ restituisce?
$col=(1,1,2,3,2,4)$
$col=(2,4,1,1,3,2)$
$col=(1,1,2,2,3,4)$
$col=(1,1,2,4,2,3)$
Spiegazione. Si esaminano i vertici nell'ordine di $\lambda$ e si dà a ognuno il colore più piccolo non usato dai vicini già colorati: $col=(1,1,2,4,2,3)$. L'ordine conta: con la lista $(1,\dots,6)$ si ottiene $(1,1,2,2,3,4)$.
Esempio 2 · eh-g-vcp-gc · livello facile · dispensa
Grafo $G=(V,E)$ con $V=\{1,\dots,6\}$ e $E=\{\{1,2\},\{1,3\},\{2,3\},\{2,5\},\{2,6\},\{4,5\},\{4,6\}\}$. La colorazione greedy $GC$ esamina i vertici nell'ordine della lista $\lambda=(6,3,2,4,5,1)$ e dà a ciascuno il colore (intero $\ge 1$) più piccolo non usato dai vicini già colorati. Quale colorazione $col=(col[1],\dots,col[6])$ restituisce?
$col=(1,2,3,2,1,1)$
$col=(1,2,3,1,3,3)$
$col=(3,2,1,2,1,1)$
$col=(2,1,3,1,2,2)$
Spiegazione. Si esaminano i vertici nell'ordine di $\lambda$ e si dà a ognuno il colore più piccolo non usato dai vicini già colorati: $col=(3,2,1,2,1,1)$. L'ordine conta: con la lista $(1,\dots,6)$ si ottiene $(1,2,3,1,3,3)$.
Esempio 1 · eh-g-vcp-dsatur · livello facile · dispensa
Grafo $G=(V,E)$ con $V=\{1,\dots,6\}$ e $E=\{\{1,2\},\{1,3\},\{2,3\},\{2,6\},\{3,4\},\{4,5\},\{4,6\}\}$. $DSATUR$ colora a ogni passo il vertice non colorato di grado di saturazione massimo (numero di colori diversi fra i vicini già colorati), con il colore più piccolo libero; pari merito: più vicini non colorati, poi indice minimo. In quale ordine colora i vertici?
$(2,3,1,4,5,6)$
$(2,3,4,1,6,5)$
$(1,2,3,4,6,5)$
$(2,3,1,4,6,5)$
Spiegazione. A ogni passo si sceglie il vertice non colorato con più colori diversi fra i vicini: ordine $(2,3,1,4,5,6)$, con $3$ colori. Il grado di spareggio è quello verso i vertici non ancora colorati, aggiornato a ogni passo.
Esempio 2 · eh-g-vcp-dsatur · livello facile · dispensa
Grafo $G=(V,E)$ con $V=\{1,\dots,6\}$ e $E=\{\{1,5\},\{2,4\},\{2,5\},\{2,6\},\{3,4\},\{3,5\},\{4,6\}\}$. $DSATUR$ colora a ogni passo il vertice non colorato di grado di saturazione massimo (numero di colori diversi fra i vicini già colorati), con il colore più piccolo libero; pari merito: più vicini non colorati, poi indice minimo. In quale ordine colora i vertici?
$(1,5,2,3,4,6)$
$(2,4,6,5,1,3)$
$(2,4,5,3,6,1)$
$(2,4,6,5,3,1)$
Spiegazione. A ogni passo si sceglie il vertice non colorato con più colori diversi fra i vicini: ordine $(2,4,6,5,1,3)$, con $3$ colori. Il grado di spareggio è quello verso i vertici non ancora colorati, aggiornato a ogni passo.
Esempio 1 · eh-g-tsp-nn · livello facile · dispensa
TSP simmetrico (giro più corto che visita tutte le città) con le distanze $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 4 & 4 & 2 & 3\\ 2 & 4 & - & 5 & 7 & 3\\ 3 & 4 & 5 & - & 6 & 7\\ 4 & 2 & 7 & 6 & - & 9\\ 5 & 3 & 3 & 7 & 9 & -\end{array}$. L'euristica $NN$ (nearest neighbour) parte dalla città $1$, va ogni volta alla città non visitata più vicina (pari merito: indice minore) e alla fine torna alla partenza. Qual è la lunghezza del giro?
$20$
$16$
$19$
$27$
Spiegazione. $NN$ visita $(1,4,3,2,5)$ e torna in $1$: lunghezza $19$. Errore tipico: dimenticare l'arco di ritorno (si otterrebbe $16$).
Esempio 2 · eh-g-tsp-nn · livello facile · dispensa
TSP simmetrico (giro più corto che visita tutte le città) con le distanze $\begin{array}{c|ccccc} d_{ij} & 1 & 2 & 3 & 4 & 5\\ \hline 1 & - & 11 & 10 & 3 & 12\\ 2 & 11 & - & 12 & 9 & 9\\ 3 & 10 & 12 & - & 4 & 9\\ 4 & 3 & 9 & 4 & - & 7\\ 5 & 12 & 9 & 9 & 7 & -\end{array}$. L'euristica $NN$ (nearest neighbour) parte dalla città $1$, va ogni volta alla città non visitata più vicina (pari merito: indice minore) e alla fine torna alla partenza. Qual è la lunghezza del giro?
$25$
$40$
$46$
$36$
Spiegazione. $NN$ visita $(1,4,3,5,2)$ e torna in $1$: lunghezza $36$. Errore tipico: dimenticare l'arco di ritorno (si otterrebbe $25$).
Esempio 1 · eh-g-pcmax-lpt · livello facile · dispensa
Scheduling $P\,||\,C_{\max}$: $m=3$ macchine identiche, tempi di lavorazione $t=(2,4,6,3,5,5,7)$, si minimizza il makespan (carico massimo). $LPT$ ordina i lavori per tempo non crescente e assegna ciascuno alla macchina di carico minimo (pari merito: indice minore). Qual è il makespan della soluzione di $LPT$?
$14$
$11$
$13$
$12$
Spiegazione. $LPT$ ordina i lavori per tempo non crescente e assegna ciascuno a una macchina di carico minimo: makespan $12$. $LIST$ nell'ordine dato dà $13$; il lower bound $\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}$ vale $11$.
Esempio 2 · eh-g-pcmax-lpt · livello facile · dispensa
Scheduling $P\,||\,C_{\max}$: $m=3$ macchine identiche, tempi di lavorazione $t=(7,9,8,7,8,8,3)$, si minimizza il makespan (carico massimo). $LPT$ ordina i lavori per tempo non crescente e assegna ciascuno alla macchina di carico minimo (pari merito: indice minore). Qual è il makespan della soluzione di $LPT$?
$18$
$17$
$20$
$19$
Spiegazione. $LPT$ ordina i lavori per tempo non crescente e assegna ciascuno a una macchina di carico minimo: makespan $18$. $LIST$ nell'ordine dato dà $17$; il lower bound $\max\{\max_j t_j,\lceil\sum_j t_j/m\rceil\}$ vale $17$.
3. Ricerca locale (4)
Esempio 1 · eh-g-tsp-2opt · livello media · dispensa
TSP simmetrico con le distanze $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 8 & 8 & 10 & 11 & 3\\ 2 & 8 & - & 10 & 8 & 8 & 11\\ 3 & 8 & 10 & - & 2 & 11 & 4\\ 4 & 10 & 8 & 2 & - & 4 & 2\\ 5 & 11 & 8 & 11 & 4 & - & 3\\ 6 & 3 & 11 & 4 & 2 & 3 & -\end{array}$. Il giro corrente è $\sigma=(1,6,5,2,4,3)$, di lunghezza $32$. Una mossa 2-opt toglie due lati non adiacenti del giro e ricollega i due cammini nell'altro modo possibile; con la regola best improvement si applica la mossa che riduce di più la lunghezza. Qual è la lunghezza del giro dopo un'iterazione?
$32$
$31$
$26$
$33$
Spiegazione. Per ogni mossa $\Delta=d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}$; la migliore ha $\Delta=-1$ (posizioni $i=1$, $j=4$), quindi $32-1=31$. La prima mossa migliorante ($\Delta=-1$) è quella del first improvement.
Esempio 2 · eh-g-tsp-2opt · livello media · dispensa
TSP simmetrico con le distanze $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 6 & 11 & 5 & 3 & 6\\ 2 & 6 & - & 11 & 10 & 9 & 12\\ 3 & 11 & 11 & - & 10 & 9 & 11\\ 4 & 5 & 10 & 10 & - & 10 & 3\\ 5 & 3 & 9 & 9 & 10 & - & 12\\ 6 & 6 & 12 & 11 & 3 & 12 & -\end{array}$. Il giro corrente è $\sigma=(1,3,2,5,4,6)$, di lunghezza $50$. Una mossa 2-opt toglie due lati non adiacenti del giro e ricollega i due cammini nell'altro modo possibile; con la regola best improvement si applica la mossa che riduce di più la lunghezza. Qual è la lunghezza del giro dopo un'iterazione?
$40$
$42$
$45$
$58$
Spiegazione. Per ogni mossa $\Delta=d_{u_1u_2}+d_{v_1v_2}-d_{u_1v_1}-d_{u_2v_2}$; la migliore ha $\Delta=-8$ (posizioni $i=1$, $j=4$), quindi $50-8=42$. La prima mossa migliorante ($\Delta=-5$) è quella del first improvement.
Esempio 1 · eh-g-pcmax-move · livello facile · dispensa
Scheduling $P\,||\,C_{\max}$ (minimizzare il makespan, il carico massimo) con $m=3$ macchine, tempi $t=(5,9,2,9,5,8)$ e assegnamento corrente $\mathrm{mach}=(3,2,1,3,3,1)$ ($\mathrm{mach}_j$ è la macchina del lavoro $j$; carichi $(10,9,19)$). L'intorno move sposta un lavoro $j$ su un'altra macchina $h$; best improvement sceglie la mossa che riduce di più il makespan (mosse esaminate per $j=1,\dots,n$ e $h=1,\dots,m$; a parità si tiene la prima). Quale mossa sceglie?
lavoro $1$ sulla macchina $2$
lavoro $1$ sulla macchina $1$
lavoro $4$ sulla macchina $2$
lavoro $2$ sulla macchina $1$
Spiegazione. La variazione del makespan della mossa scelta è $-5$, la più negativa (makespan da $19$ a $14$). La prima mossa migliorante (first improvement) ha variazione $-4$; spostare un lavoro da una macchina non critica non riduce il makespan.
Esempio 2 · eh-g-pcmax-move · livello facile · dispensa
Scheduling $P\,||\,C_{\max}$ (minimizzare il makespan, il carico massimo) con $m=3$ macchine, tempi $t=(3,6,3,8,1,3)$ e assegnamento corrente $\mathrm{mach}=(1,3,2,3,3,1)$ ($\mathrm{mach}_j$ è la macchina del lavoro $j$; carichi $(6,3,15)$). L'intorno move sposta un lavoro $j$ su un'altra macchina $h$; best improvement sceglie la mossa che riduce di più il makespan (mosse esaminate per $j=1,\dots,n$ e $h=1,\dots,m$; a parità si tiene la prima). Quale mossa sceglie?
lavoro $1$ sulla macchina $2$
lavoro $2$ sulla macchina $1$
lavoro $4$ sulla macchina $2$
lavoro $2$ sulla macchina $2$
Spiegazione. La variazione del makespan della mossa scelta è $-6$, la più negativa (makespan da $15$ a $9$). La prima mossa migliorante (first improvement) ha variazione $-3$; spostare un lavoro da una macchina non critica non riduce il makespan.
Esempio 1 · eh-g-pcmax-descent · livello complessa · dispensa
$P\,||\,C_{\max}$ con $m=3$ macchine e lavori di durata $t=(2,6,5,7,7,9,4)$; la soluzione di partenza assegna i lavori alle macchine $(1,1,2,1,1,1,1)$. Si applica la ricerca locale con l'intorno move (un lavoro passa a un'altra macchina) e l'obiettivo ausiliario $\sum_hL_h^2$ da minimizzare ($L_h$ = carico della macchina $h$), con la regola best improvement: a ogni iterazione si applica la mossa che diminuisce di più $\sum_hL_h^2$ (pari merito: lavoro di indice minore, poi macchina di indice minore), finché nessuna mossa lo diminuisce. Qual è il makespan finale e quante mosse si applicano?
makespan finale $16$, dopo $3$ mosse
makespan finale $35$, dopo $0$ mosse
makespan finale $14$, dopo $10$ mosse
makespan finale $15$, dopo $3$ mosse
Spiegazione. Carichi iniziali $(35,5,0)$, makespan $35$. Spostare il lavoro $j$ dalla macchina $a$ alla $b$ cambia $\sum_hL_h^2$ di $2t_j(L_b-L_a+t_j)$; la discesa applica $3$ mosse e si ferma con makespan $15$. Con first improvement la discesa sarebbe diversa ($10$ mosse, makespan $14$).
Esempio 2 · eh-g-pcmax-descent · livello complessa · dispensa
$P\,||\,C_{\max}$ con $m=3$ macchine e lavori di durata $t=(4,8,2,4,3,9,2)$; la soluzione di partenza assegna i lavori alle macchine $(2,3,3,1,3,3,3)$. Si applica la ricerca locale con l'intorno move (un lavoro passa a un'altra macchina) e l'obiettivo ausiliario $\sum_hL_h^2$ da minimizzare ($L_h$ = carico della macchina $h$), con la regola best improvement: a ogni iterazione si applica la mossa che diminuisce di più $\sum_hL_h^2$ (pari merito: lavoro di indice minore, poi macchina di indice minore), finché nessuna mossa lo diminuisce. Qual è il makespan finale e quante mosse si applicano?
makespan finale $24$, dopo $0$ mosse
makespan finale $13$, dopo $3$ mosse
makespan finale $12$, dopo $3$ mosse
makespan finale $12$, dopo $6$ mosse
Spiegazione. Carichi iniziali $(4,4,24)$, makespan $24$. Spostare il lavoro $j$ dalla macchina $a$ alla $b$ cambia $\sum_hL_h^2$ di $2t_j(L_b-L_a+t_j)$; la discesa applica $3$ mosse e si ferma con makespan $12$. Con first improvement la discesa sarebbe diversa ($6$ mosse, makespan $12$).
Esempio 1 · eh-g-tsp-nn2opt · livello complessa · dispensa
TSP con $6$ città e distanze simmetriche $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 6 & 6 & 8 & 8 & 1\\ 2 & 6 & - & 8 & 6 & 6 & 8\\ 3 & 6 & 8 & - & 1 & 8 & 2\\ 4 & 8 & 6 & 1 & - & 3 & 1\\ 5 & 8 & 6 & 8 & 3 & - & 1\\ 6 & 1 & 8 & 2 & 1 & 1 & -\end{array}$. Si costruisce il giro nearest neighbour dalla città $1$ (pareggi: città di indice minore), scritto come sequenza $(t_1,\dots,t_6)$ con $t_1=1$. Poi si applica 2-opt con la regola first improvement: si esaminano le coppie di posizioni $(i,j)$ con $i=1,\dots,5$ e $j=i+2,\dots,6$ (esclusa $(1,6)$); la mossa toglie i lati $\{t_i,t_{i+1}\}$ e $\{t_j,t_{j+1}\}$ (con $t_7=t_1$), aggiunge $\{t_i,t_j\}$ e $\{t_{i+1},t_{j+1}\}$ invertendo il tratto $t_{i+1},\dots,t_j$, e si applica appena accorcia il giro; dopo ogni mossa l'esame riparte da $(1,3)$. Qual è la lunghezza del giro finale e quante mosse si applicano?
lunghezza finale $21$, dopo $3$ mosse
lunghezza finale $21$, dopo $2$ mosse
lunghezza finale $22$, dopo $2$ mosse
lunghezza finale $25$, dopo $0$ mosse
Spiegazione. Nearest neighbour dà $(1,6,4,3,2,5)$, lunghezza $25$. 2-opt applica $2$ mosse e si ferma nell'ottimo locale $(1,6,5,2,4,3)$, lunghezza $21$.
Esempio 2 · eh-g-tsp-nn2opt · livello complessa · dispensa
TSP con $6$ città e distanze simmetriche $\begin{array}{c|cccccc} d_{ij} & 1 & 2 & 3 & 4 & 5 & 6\\ \hline 1 & - & 8 & 7 & 1 & 7 & 3\\ 2 & 8 & - & 1 & 2 & 9 & 8\\ 3 & 7 & 1 & - & 8 & 1 & 8\\ 4 & 1 & 2 & 8 & - & 4 & 2\\ 5 & 7 & 9 & 1 & 4 & - & 9\\ 6 & 3 & 8 & 8 & 2 & 9 & -\end{array}$. Si costruisce il giro nearest neighbour dalla città $1$ (pareggi: città di indice minore), scritto come sequenza $(t_1,\dots,t_6)$ con $t_1=1$. Poi si applica 2-opt con la regola first improvement: si esaminano le coppie di posizioni $(i,j)$ con $i=1,\dots,5$ e $j=i+2,\dots,6$ (esclusa $(1,6)$); la mossa toglie i lati $\{t_i,t_{i+1}\}$ e $\{t_j,t_{j+1}\}$ (con $t_7=t_1$), aggiunge $\{t_i,t_j\}$ e $\{t_{i+1},t_{j+1}\}$ invertendo il tratto $t_{i+1},\dots,t_j$, e si applica appena accorcia il giro; dopo ogni mossa l'esame riparte da $(1,3)$. Qual è la lunghezza del giro finale e quante mosse si applicano?
lunghezza finale $17$, dopo $1$ mosse
lunghezza finale $16$, dopo $1$ mosse
lunghezza finale $17$, dopo $0$ mosse
lunghezza finale $16$, dopo $2$ mosse
Spiegazione. Nearest neighbour dà $(1,4,2,3,5,6)$, lunghezza $17$. 2-opt applica $1$ mosse e si ferma nell'ottimo locale $(1,5,3,2,4,6)$, lunghezza $16$.
4. Metaeuristiche (2)
Esempio 1 · eh-g-sa-prob · livello facile · dispensa
Nel simulated annealing per un problema di minimo, alla temperatura $T=7$ si propone un vicino che peggiora l'obiettivo di $\delta=10$. Con la regola di Metropolis, con quale probabilità è accettato?
$e^{-\frac{7}{10}}$
$e^{-\frac{10}{7}}$
$e^{-70}$
$1$
Spiegazione. Un peggioramento $\delta>0$ è accettato con probabilità $e^{-\delta/T}=e^{-\frac{10}{7}}$; un miglioramento sarebbe accettato con probabilità $1$.
Esempio 2 · eh-g-sa-prob · livello facile · dispensa
Nel simulated annealing per un problema di minimo, alla temperatura $T=9$ si propone un vicino che peggiora l'obiettivo di $\delta=5$. Con la regola di Metropolis, con quale probabilità è accettato?
$e^{-45}$
$1$
$e^{-\frac{5}{9}}$
$e^{-\frac{9}{5}}$
Spiegazione. Un peggioramento $\delta>0$ è accettato con probabilità $e^{-\delta/T}=e^{-\frac{5}{9}}$; un miglioramento sarebbe accettato con probabilità $1$.
Esempio 1 · eh-g-ga-cross · livello facile · dispensa
Algoritmo genetico per lo zaino 0-1 con codifica binaria ($x_j=1$ se l'oggetto $j$ è scelto). Il crossover a un punto con taglio $cut=2$ prende i geni $1,\dots,cut$ dal primo genitore e i geni $cut+1,\dots,n$ dal secondo. Genitori $(1,1,0,1,1,1,0)$ e $(1,1,1,1,0,0,0)$: quale figlio si ottiene?
$(1,1,0,1,0,0,0)$
$(1,1,1,1,0,0,0)$
$(1,1,1,1,1,1,0)$
$(1,1,0,1,1,1,0)$
Spiegazione. I primi $2$ geni vengono da $(1,1,0,1,1,1,0)$ e gli altri da $(1,1,1,1,0,0,0)$: $(1,1,1,1,0,0,0)$. Il figlio può superare la capacità e allora va riparato.
Esempio 2 · eh-g-ga-cross · livello facile · dispensa
Algoritmo genetico per lo zaino 0-1 con codifica binaria ($x_j=1$ se l'oggetto $j$ è scelto). Il crossover a un punto con taglio $cut=5$ prende i geni $1,\dots,cut$ dal primo genitore e i geni $cut+1,\dots,n$ dal secondo. Genitori $(1,0,0,0,1,0,0)$ e $(1,1,0,1,1,1,0)$: quale figlio si ottiene?
$(1,1,0,1,1,1,0)$
$(1,0,0,0,1,1,0)$
$(1,1,0,1,1,0,0)$
$(1,0,0,0,1,0,0)$
Spiegazione. I primi $5$ geni vengono da $(1,0,0,0,1,0,0)$ e gli altri da $(1,1,0,1,1,1,0)$: $(1,0,0,0,1,1,0)$. Il figlio può superare la capacità e allora va riparato.
5. Euristiche MIP per i problemi classici (1)
Esempio 1 · eh-g-kp-round · livello facile · dispensa
Zaino 0/1 con capacità $c=12$ e oggetti già ordinati per efficienza $p_j/w_j$ non crescente: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 8 & 18 & 21 & 11 & 3\\ w_j & 2 & 5 & 6 & 8 & 3\end{array}$. La soluzione ottima del rilassamento lineare di $\mathrm{ILP}_{\mathrm{KP}}$ è $\tilde{\vet x}=(1,1,\frac{5}{6},0,0)$. Quanto vale il profitto della soluzione $\lfloor\tilde{\vet x}\rfloor$ ottenuta arrotondando per difetto?
$47$
$29$
$26$
$\frac{87}{2}$
Spiegazione. Arrotondando per difetto si tengono gli oggetti $1,\dots,2$ e si toglie l'oggetto frazionario $3$: profitto $26$, ammissibile perché il peso solo diminuisce. $\frac{87}{2}$ è il valore del rilassamento; il greedy, che continua dopo l'oggetto che non entra, può fare di più.
Esempio 2 · eh-g-kp-round · livello facile · dispensa
Zaino 0/1 con capacità $c=19$ e oggetti già ordinati per efficienza $p_j/w_j$ non crescente: $\begin{array}{c|ccccc}j & 1 & 2 & 3 & 4 & 5\\ \hline p_j & 11 & 26 & 16 & 5 & 3\\ w_j & 3 & 8 & 7 & 3 & 2\end{array}$. La soluzione ottima del rilassamento lineare di $\mathrm{ILP}_{\mathrm{KP}}$ è $\tilde{\vet x}=(1,1,1,\frac{1}{3},0)$. Quanto vale il profitto della soluzione $\lfloor\tilde{\vet x}\rfloor$ ottenuta arrotondando per difetto?
$55$
$58$
$53$
$\frac{164}{3}$
Spiegazione. Arrotondando per difetto si tengono gli oggetti $1,\dots,3$ e si toglie l'oggetto frazionario $4$: profitto $53$, ammissibile perché il peso solo diminuisce. $\frac{164}{3}$ è il valore del rilassamento; il greedy, che continua dopo l'oggetto che non entra, può fare di più.