1.5 Bound primali, bound duali e gap¶
Parte 1 · Problemi di ottimizzazione combinatoria · Capitolo 1 · Capitolo 1: Ottimizzazione combinatoria · Dispensa, volume 1 (PDF) · Slide · Esercizi: Ottimizzazione combinatoria · App: Forza bruta sul problema dello zaino 0/1
- Gli approcci più intelligenti si basano su un'idea semplice: invece di calcolare direttamente \(z(I)\), lo racchiudiamo fra due numeri. Uno viene da una soluzione ammissibile, l'altro da un argomento che vale per tutte le soluzioni ammissibili.
Definizione 1.4: bound primali e duali
Consideriamo un'istanza \(I\) di un problema di ottimizzazione combinatoria con soluzioni ammissibili \(\mathcal F\), funzione obiettivo \(f\) e valore ottimo \(z(I)\).
-
Un bound primale è il valore \(f(\bar S)\) di una soluzione ammissibile \(\bar S \in \mathcal F\).
-
Un bound duale è un numero \(\beta\) tale che
\[ f(S) \le \beta, \qquad \forall S \in \mathcal F \qquad \text{(forma di massimo)}, \]oppure tale che
\[ f(S) \ge \beta, \qquad \forall S \in \mathcal F \qquad \text{(forma di minimo)}. \]
-
Nella forma di massimo un bound primale è un lower bound e un bound duale è un upper bound:
\[ \LB = f(\bar S) \;\le\; z(I) \;\le\; \UB . \] -
Nella forma di minimo i ruoli si scambiano: un bound primale è un upper bound \(\UB = f(\bar S)\) e un bound duale è un lower bound \(\LB\), con \(\LB \le z(I) \le \UB\).
-
I bound primali vengono da soluzioni ammissibili, per esempio trovate da algoritmi euristici; i bound duali vengono da rilassamenti (per esempio il rilassamento lineare) o da argomenti combinatori.
Definizione 1.5: gap
Siano \(\LB \le z(I) \le \UB\) un lower bound e un upper bound di un'istanza \(I\), uno primale e uno duale. Il gap assoluto è \(\UB - \LB\) e, per \(\LB \neq 0\), il gap relativo (o semplicemente gap) è
-
Il denominatore è sempre il lower bound: nella forma di massimo è il valore della soluzione ammissibile, come nel gap di ottimalità del modulo Programmazione lineare intera, Capitolo 2 «Bound primali e duali»; nella forma di minimo è il bound duale.
-
Con questa scelta il gap non è mai minore dell'errore relativo \(|f(\bar S) - z(I)|/z(I)\) della soluzione ammissibile \(\bar S\): un gap del \(5\%\) garantisce una soluzione entro il \(5\%\) dall'ottimo.
-
Se il gap è nullo, la soluzione ammissibile \(\bar S\) è ottima e il bound duale è un certificato della sua ottimalità.
Osservazione 1.6
Se \(f(S) \in \Z\) per ogni \(S \in \mathcal F\), allora nella forma di massimo anche \(\lfloor \beta \rfloor\) è un bound duale, e nella forma di minimo anche \(\lceil \beta \rceil\) è un bound duale.
Dimostrazione
Nella forma di massimo, per ogni \(S \in \mathcal F\) abbiamo \(f(S) \le \beta\) e \(f(S) \in \Z\); il più grande intero non maggiore di \(\beta\) è \(\lfloor \beta \rfloor\), quindi \(f(S) \le \lfloor \beta \rfloor\). La forma di minimo è analoga. □
Esempio 1.4: bound sulla piccola istanza
Consideriamo di nuovo l'istanza dell'Esempio 1.1 (massimizzazione), e supponiamo di non avere enumerato i suoi sottoinsiemi.
-
Bound primale. Partiamo da \(\emptyset\) ed esaminiamo gli elementi per peso non crescente, aggiungendo ciascuno se l'insieme resta ammissibile: \(\{1\}\) è ammissibile, \(\{1,2\}\) no, \(\{1,3\}\) è ammissibile, \(\{1,3,4\}\) no. La soluzione ammissibile \(\bar S = \{1,3\}\) dà \(\LB = 11\).
-
Un primo bound duale. I pesi sono positivi, quindi \(f(S) \le f(\mathscr{U}) = 20\) per ogni \(S \in \mathcal F\).
-
Un bound duale migliore. Nessun sottoinsieme ammissibile contiene sia \(1\) sia \(2\), quindi un sottoinsieme ammissibile prende al più uno dei pesi \(7\) e \(6\):
\[ f(S) \le \max\{7,6\} + 4 + 3 = 14, \qquad \forall S \in \mathcal F . \]Il gap assoluto è \(14-11 = 3\) e il gap relativo è \(\tfrac{3}{11} \approx 27.3\%\).
-
Un bound primale migliore. La soluzione ammissibile \(\{2,3,4\}\) dà \(\LB = 13\): il gap scende a \(\tfrac{1}{13} \approx 7.7\%\).
-
Chiusura del gap. L'unico sottoinsieme ammissibile con \(3\) elementi è \(\{2,3,4\}\), e un sottoinsieme con al più \(2\) elementi ha valore al più \(7+6 = 13\). Quindi \(\UB = 13 = \LB\): il gap è nullo, e questo argomento è un certificato che \(\{2,3,4\}\) è ottima, senza elencare i \(16\) sottoinsiemi.
Se invece un argomento desse il bound duale \(13.5\), anche \(\lfloor 13.5 \rfloor = 13\) sarebbe un bound duale, poiché tutti i valori \(f(S)\) sono interi (Osservazione 1.6).
- Nel resto del corso, ogni capitolo su un problema registra, per le sue istanze, i migliori bound primali e duali trovati fino a quel punto; ogni metodo migliora l'uno o l'altro lato.