Bound primali e duali

Parte 1 · Modelli e bound · Capitolo 2 · Dispensa, volume 1 (PDF) · Esercizi: Bound primali e duali · App: Punti interi e rilassamento lineare

Prerequisiti

• Da questo modulo, il capitolo «Programmazione lineare intera»: problemi PLI, soluzioni ammissibili e ottime, enumerazione completa e l'esempio dell'auto.

• Dal modulo Programmazione Lineare, Capitolo 9 «Teoria della dualità»: il problema duale, la dualità debole e la dualità forte.

• Dallo stesso modulo, Capitolo 6 «Algoritmo del simplesso»: un problema LP che ha una soluzione ottima ha un vertice ottimo.

Obiettivi

Alla fine di questo capitolo sarai in grado di:

• ottenere un bound primale (un lower bound) sul valore ottimo da una soluzione ammissibile, anche con un semplice algoritmo euristico;

• costruire il rilassamento lineare di un problema PLI e usarne il valore ottimo come bound duale (un upper bound), arrotondato per difetto quando è lecito;

• calcolare il gap di ottimalità da un bound primale e un bound duale;

• spiegare perché arrotondare una soluzione ottima del rilassamento lineare dà, nel migliore dei casi, una soluzione ammissibile;

• ricavare dai vincoli upper bound sulle variabili, e dire quando servono;

• ottenere un bound duale da moltiplicatori non negativi dei vincoli, e riconoscere nel problema duale il problema dei moltiplicatori migliori.

Dove eravamo

Nel capitolo precedente abbiamo visto che l'enumerazione completa non è praticabile e che servono bound sul valore ottimo da entrambi i lati. Ora li otteniamo: bound primali dalle soluzioni ammissibili e bound duali dai rilassamenti.

2.1 Bound primali e bound duali

Definizione 2.1: bound primale, bound duale e gap di ottimalità

Consideriamo un problema PLI in forma canonica di massimizzazione, con regione ammissibile \(F\) e valore ottimo \(z(\ILP)\).

• Data una soluzione ammissibile \(\bar{\vet x} \in F\), il suo valore \(\LB(\bar{\vet x}) = \sum_{j=1}^n c_j \, \bar{x}_j\) è un bound primale su \(z(\ILP)\).

• Un valore \(\UB\) tale che \(\sum_{j=1}^n c_j \, x_j \le \UB\) per ogni \(\vet x \in F\) è un bound duale su \(z(\ILP)\).

• Dati un bound primale \(\LB \ne 0\) e un bound duale \(\UB\), il gap di ottimalità è

  \[\begin{equation*} \label{gap} \textrm{gap di ottimalità} = \frac{\UB - \LB}{|\LB|} . \tag{2.1} \end{equation*}\]

• In un problema di massimizzazione i bound primali sono lower bound e i bound duali sono upper bound. Un bound primale viene da una sola soluzione ammissibile; un bound duale è un'affermazione su tutte le soluzioni ammissibili insieme.

Per ogni soluzione ammissibile \(\bar{\vet x}\) e ogni bound duale \(\UB\):

\[ \LB(\bar{\vet x}) ~\le~ z(\ILP) ~\le~ \UB . \]

Una soluzione ammissibile è certificata ottima quando il gap di ottimalità è zero.

Definizione 2.2: rilassamento

Dato un problema PLI \(\max \{ \vet c\T \vet x : \vet x \in F \}\), il problema \(\max \{ \vet c\T \vet x : \vet x \in R \}\) è un rilassamento del problema PLI se \(F \subseteq R\). Indichiamo il suo valore ottimo con \(z(R)\).

• Massimizzare su una regione più grande non può dare un valore più piccolo: il valore ottimo di un rilassamento è un bound duale, \(z(\ILP) \le z(R)\).

2.2 Bound primali: soluzioni euristiche

Definizione 2.3: algoritmo euristico

Un algoritmo euristico è un metodo che trova rapidamente soluzioni ammissibili, senza garanzia di ottimalità. Il valore di ogni soluzione che trova è un bound primale.

Una buona soluzione ammissibile è un buon bound primale.

Esempio 2.1: bound primale

Per la soluzione ammissibile \((2,2)\) dell'esempio dell'auto otteniamo \(\LB = 3 \cdot 2 + 2 \cdot 2 = 10\), quindi \(z(\ILP) \ge 10\).

Definizione 2.4: parte intera di un numero

Dato \(y \in \R\), la parte intera di \(y\) è \(\lfloor y \rfloor = \max \{ q \in \Z : q \le y \}\).

Esempio 2.2: due algoritmi euristici per l'esempio dell'auto

• L'euristica a una variabile porta una sola variabile al suo valore massimo, con l'altra uguale a \(0\), e tiene la migliore delle due soluzioni.

  1. Solo \(x_1\) (\(x_2 = 0\)): \(\bar{x}_1 = \min\{\lfloor \frac{45}{10} \rfloor, \lfloor \frac{49}{4} \rfloor\} = \min\{4, 12\} = 4\), quindi \(\bar{\vet x} = (4,0)\) e \(\LB = 12\).

  2. Solo \(x_2\) (\(x_1 = 0\)): \(\bar{x}_2 = \min\{\lfloor \frac{45}{4} \rfloor, \lfloor \frac{49}{14} \rfloor\} = \min\{11, 3\} = 3\), quindi \(\bar{\vet x} = (0,3)\) e \(\LB = 6\).

• L'euristica a due fasi porta prima una variabile al suo valore massimo, e poi l'altra al suo valore massimo con i termini noti residui. Tiene la migliore delle due soluzioni.

  1. Prima \(x_1\): \(\bar{x}_1 = 4\) usa \(40\) e \(16\), e lascia \(5\) e \(33\). Poi \(\bar{x}_2 = \min\{\lfloor \frac{5}{4} \rfloor, \lfloor \frac{33}{14} \rfloor\} = \min\{1, 2\} = 1\), quindi \(\bar{\vet x} = (4,1)\) e \(\LB = 14\).

  2. Prima \(x_2\): \(\bar{x}_2 = 3\) usa \(12\) e \(42\), e lascia \(33\) e \(7\). Poi \(\bar{x}_1 = \min\{\lfloor \frac{33}{10} \rfloor, \lfloor \frac{7}{4} \rfloor\} = \min\{3, 1\} = 1\), quindi \(\bar{\vet x} = (1,3)\) e \(\LB = 9\).

Euristica	Ordine	\(\bar{x}_1\)	\(\bar{x}_2\)	\(\LB\)
a una variabile	\(x_1\)	\(4\)	\(0\)	\(12\)
a una variabile	\(x_2\)	\(0\)	\(3\)	\(6\)
a due fasi	prima \(x_1\)	\(4\)	\(1\)	\(14\)
a due fasi	prima \(x_2\)	\(1\)	\(3\)	\(9\)

• L'euristica a due fasi dà un bound primale migliore, ma richiede più calcoli. Questo compromesso tra la qualità della soluzione e lo sforzo di calcolo è tipico degli algoritmi euristici.

• Qui il bound primale migliore è \(\LB = 14\), in \((4,1)\). Un bound primale da solo non certifica l'ottimalità: serve un bound duale.

2.3 Il rilassamento lineare

Definizione 2.5: rilassamento lineare

Il rilassamento lineare (rilassamento lineare) di un problema PLI in forma canonica di massimizzazione è il problema LP che si ottiene sostituendo i vincoli di integralità \(x_j \in \Z_{\ge 0}\) con i vincoli di non negatività \(x_j \ge 0\), per ogni \(j \in \{1,2,\dots,n\}\):

\[\begin{align*} && \max \;\;{\sum_{j =1}^n c_j \, x_j} \label{ObjFunc_LP} \tag{2.2a}\\[2ex] && \text{soggetto a} \quad {\sum_{j =1}^n a_{ij} \, x_j} &\leq b_i, & \forall i \in \{1,2,\dots,m\}, \label{Cons_LP} \tag{2.2b}\\[2ex] &&x_j &\ge 0, & \forall j \in \{1,2,\dots,n\}. \label{non_negativity_LP} \tag{2.2c} \end{align*}\]

• Indichiamo con \(z(\LP)\) il valore ottimo del rilassamento lineare, e con \(\tilde{\vet x}(\LP)\) una sua soluzione ottima. Scriviamo sempre l'argomento, perché nello stesso esempio \(\tilde{\vet x}(\ILP)\) e \(\tilde{\vet x}(\LP)\) sono punti diversi.

Proposizione 2.6: upper bound dal rilassamento lineare

Ogni soluzione ammissibile del problema PLI è ammissibile per il suo rilassamento lineare, quindi

\[\begin{equation*} z(\ILP) \le z(\LP). \label{LP_BOUND} \tag{2.3} \end{equation*}\]

Inoltre, se una soluzione ottima del rilassamento lineare è intera, allora è una soluzione ottima del problema PLI.

Dimostrazione

La regione ammissibile \(F\) del problema PLI è contenuta nel poliedro del rilassamento lineare, e la funzione obiettivo è la stessa. Il massimo su un insieme più grande non è minore del massimo su un suo sottoinsieme. Se \(\tilde{\vet x}(\LP)\) è intera, appartiene a \(F\) e ha valore \(z(\LP) \ge z(\ILP)\): è ottima per il problema PLI. □

• Il valore di una soluzione ammissibile può essere un intero, ed è al più \(z(\LP)\): allora è al più il più grande intero che non supera \(z(\LP)\).

Osservazione 2.7: arrotondare l'upper bound

Se tutte le variabili sono intere e tutti i costi \(c_j\) sono interi, allora

\[\begin{equation*} z(\ILP) \le \lfloor z(\LP) \rfloor. \label{LP_BOUND_2} \tag{2.4} \end{equation*}\]

In tutti gli altri casi il bound \(\lfloor z(\LP) \rfloor\) non è valido.

• In questo modulo tutti i problemi PLI hanno dati interi, quindi il bound \(\eqref{LP_BOUND_2}\) vale sempre. In un problema MIP con una variabile continua il valore di una soluzione ammissibile non è necessariamente intero, e il bound non si può arrotondare.

Esempio 2.3: il rilassamento lineare dell'esempio dell'auto

• Il rilassamento lineare dell'esempio dell'auto ha la soluzione ottima

  \[ \tilde{x}_1 = \frac{7}{2}, \quad \tilde{x}_2 = \frac{5}{2}, \qquad z(\LP) = \frac{31}{2}, \]

  che è frazionaria: non è ammissibile per il problema PLI.

• Poiché i costi sono interi, abbiamo l'upper bound \(\lfloor z(\LP) \rfloor = 15\). Insieme al bound primale \(14\) della soluzione ammissibile \((4,1)\) dell'Esempio 2.2:

  \[ 14 ~\le~ z(\ILP) ~\le~ 15. \]

Il rilassamento lineare dell'esempio dell'auto: la regione ammissibile (rossa), i suoi \(16\) punti interi (neri) e la soluzione ottima \((\frac{7}{2},\frac{5}{2})\) del rilassamento lineare (blu), con la retta obiettivo \(3\,x_1 + 2\,x_2 = \frac{31}{2}\) che vi passa (tratteggiata). La linea grigia tratteggiata è la retta obiettivo della soluzione ottima del problema PLI.

• Il valore ottimo è \(14\) o \(15\). Con \(\UB = 15\) e \(\LB = 14\) il gap di ottimalità \(\eqref{gap}\) è \(\frac{1}{14} \approx 7.1\%\): la soluzione \((4,1)\) non è ancora certificata ottima.

2.4 Arrotondare la soluzione del rilassamento lineare

Di solito si ottengono soluzioni ammissibili del problema PLI arrotondando una soluzione ottima del rilassamento lineare. Ma nessuna tecnica di arrotondamento garantisce di trovare una soluzione ottima del problema PLI.

Esempio 2.4: arrotondamento nell'esempio dell'auto

• La soluzione ottima del rilassamento lineare è \(\tilde{\vet x}(\LP) = (\frac{7}{2},\frac{5}{2})\). Arrotondando all'intero più vicino si ottiene \((4,3)\), che è inammissibile: \(10 \cdot 4 + 4 \cdot 3 = 52 > 45\).

• Arrotondando per difetto entrambe le componenti si ottiene la soluzione ammissibile \(\bar{\vet x} = (3,2)\), con \(\LB = 3 \cdot 3 + 2 \cdot 2 = 13\). La soluzione ottima del problema PLI è \(\tilde{\vet x}(\ILP) = (4,1)\), con \(z(\ILP) = 14\): l'arrotondamento non dà l'ottimo, e i bound sono \(13 \le z(\ILP) \le 15\).

Esempio 2.5: l'arrotondamento funziona, ma il bound non è stretto

Consideriamo il seguente problema PLI; il suo rilassamento lineare ha \(x_1, x_2 \ge 0\) al posto dei vincoli di integralità:

\[ \begin{array}{rrrrrrr} {\max} & {2}\, {x_1} & {+} & {4}\, {x_2} \\[1ex] \text{soggetto a} & {-}\, {x_1} & {+} & \, {x_2} & {\le} & {2} \\[1ex] & {8}\, {x_1} & {+} & {2}\, {x_2} & {\le} & {19} \\[1ex] & {x_1,} & & {x_2} & {\in} & {\Z_{\ge 0}} \end{array} \]

• La soluzione ottima del rilassamento lineare è \(\tilde{\vet x}(\LP) = (\frac{3}{2},\frac{7}{2})\), con \(z(\LP) = 17\) e \(\lfloor z(\LP) \rfloor = 17\), quindi \(z(\ILP) \le 17\).

• Arrotondando per difetto entrambe le componenti otteniamo la soluzione ammissibile \(\bar{\vet x} = (\lfloor \frac{3}{2} \rfloor, \lfloor \frac{7}{2} \rfloor) = (1,3)\), con \(\LB = 2 \cdot 1 + 4 \cdot 3 = 14\).

• La soluzione ottima del problema PLI è \(\tilde{\vet x}(\ILP) = (1,3)\), con \(z(\ILP) = 14\): la soluzione arrotondata è ottima. Ma i bound \(14 \le z(\ILP) \le 17\) non lo dimostrano.

Il secondo esempio: la regione ammissibile del rilassamento lineare (rossa), i punti interi (neri) e la soluzione ottima del rilassamento lineare (blu), con la retta obiettivo \(2\,x_1 + 4\,x_2 = 17\) (tratteggiata).

Esempio 2.6: l'arrotondamento fallisce

Consideriamo il seguente problema PLI:

\[ \begin{array}{rrrrrrr} {\max} & {25}\, {x_1} & {+} & {16}\, {x_2} \\[1ex] \text{soggetto a} & {50}\, {x_1} & {+} & {31}\, {x_2} & {\le} & {250} \\[1ex] & {-3}\, {x_1} & {+} & {2}\, {x_2} & {\le} & {4} \\[1ex] & {x_1,} & & {x_2} & {\in} & {\Z_{\ge 0}} \end{array} \]

• La soluzione ottima del rilassamento lineare è \(\tilde{\vet x}(\LP) = (\frac{376}{193}, \frac{950}{193}) \approx (1.94, 4.92)\), con \(z(\LP) = \frac{24600}{193} \approx 127.46\). Quindi \(z(\ILP) \le \lfloor z(\LP) \rfloor = 127\).

• Arrotondando all'intero più vicino si ottiene \((2,5)\), che è inammissibile: \(50 \cdot 2 + 31 \cdot 5 = 255 > 250\). Arrotondando \(\tilde{x}_1\) per eccesso e \(\tilde{x}_2\) per difetto si ottiene la soluzione ammissibile \(\bar{\vet x} = (2,4)\), con \(\LB = 25 \cdot 2 + 16 \cdot 4 = 114\).

• La soluzione ottima del problema PLI è \(\tilde{\vet x}(\ILP) = (5,0)\), con \(z(\ILP) = 125\). È lontana da \(\tilde{\vet x}(\LP)\), e nessun arrotondamento di \(\tilde{\vet x}(\LP)\) la trova.

Il terzo esempio: i punti interi (neri) sono lontani dalla soluzione ottima \((\frac{376}{193},\frac{950}{193})\) del rilassamento lineare (blu). La soluzione ottima del problema PLI è \((5,0)\) (cerchio blu). La linea tratteggiata è la retta obiettivo \(25\,x_1 + 16\,x_2 = \frac{24600}{193}\).

Le soluzioni ottime del problema PLI possono essere molto lontane dalle soluzioni ottime del rilassamento lineare. Il valore del rilassamento lineare, invece, è spesso un buon bound: qui \(125 \le z(\LP) \approx 127.46\).

2.5 Upper bound sulle variabili

Proposizione 2.8: upper bound sulle variabili

Sia \(\sum_{j=1}^n a_{ij} \, x_j \le b_i\) un vincolo con \(a_{ij} \ge 0\) per ogni \(j\). Allora ogni soluzione ammissibile del problema PLI soddisfa

\[\begin{equation*} \label{vub} x_j \le \left\lfloor \frac{b_i}{a_{ij}} \right\rfloor, \qquad \forall j \textrm{ tale che } a_{ij} > 0. \tag{2.5} \end{equation*}\]

Dimostrazione

Poiché tutte le variabili e tutti i coefficienti sono non negativi, \(a_{ij} \, x_j \le \sum_{k=1}^n a_{ik} \, x_k \le b_i\), quindi \(x_j \le \frac{b_i}{a_{ij}}\). La variabile è intera, quindi non supera la parte intera di \(\frac{b_i}{a_{ij}}\). □

• Se più vincoli danno un bound su \(x_j\), teniamo il più piccolo. I bound tagliano parti del poliedro del rilassamento lineare, e nessun punto intero.

Gli upper bound sulle variabili migliorano il rilassamento lineare solo se ne tagliano la soluzione ottima.

Esempio 2.7: upper bound sulle variabili dell'esempio dell'auto

Entrambi i vincoli dell'esempio dell'auto hanno coefficienti non negativi:

\[\begin{align*} x_1 &\le \min \left\{ \left\lfloor \tfrac{45}{10} \right\rfloor, \left\lfloor \tfrac{49}{4} \right\rfloor \right\} = \min\{4, 12\} = 4,\\ x_2 &\le \min \left\{ \left\lfloor \tfrac{45}{4} \right\rfloor, \left\lfloor \tfrac{49}{14} \right\rfloor \right\} = \min\{11, 3\} = 3. \end{align*}\]

• Le disuguaglianze \(x_1 \le 4\) e \(x_2 \le 3\) sono soddisfatte da tutti i punti interi dell'esempio dell'auto, e si possono aggiungere al modello. Tagliano due regioni del poliedro, e nessun punto intero.

Gli upper bound sulle variabili \(x_1 \le 4\) e \(x_2 \le 3\) (verdi) tagliano le due regioni grigie del rilassamento lineare (rosso) e nessun punto intero. La soluzione ottima del rilassamento lineare (blu) non viene tagliata.

• La soluzione ottima del rilassamento lineare, \((\frac{7}{2},\frac{5}{2})\), soddisfa entrambe le disuguaglianze. Non viene tagliata, quindi il valore ottimo del rilassamento lineare non cambia, e l'upper bound resta \(15\).

Esempio 2.8: upper bound che tagliano l'ottimo del rilassamento lineare

• Consideriamo la funzione obiettivo \(x_1 - x_2\) sui vincoli dell'esempio dell'auto, la cui soluzione ottima del problema PLI è \((4,0)\) con \(z(\ILP) = 4\). Prima dei bound, la soluzione ottima del rilassamento lineare è \((\frac{9}{2},0)\) con \(z(\LP) = \frac{9}{2}\); dopo \(x_1 \le 4\) è \((4,0)\) con \(z(\LP) = 4\), che è intera e quindi ottima.

L'obiettivo \(x_1 - x_2\): l'upper bound sulla variabile \(x_1 \le 4\) (verde) taglia il triangolo grigio e la soluzione ottima \((\frac{9}{2},0)\) del rilassamento lineare (cerchio blu). La nuova soluzione ottima \((4,0)\) (blu) è intera. La linea tratteggiata è \(x_1 - x_2 = \frac{9}{2}\).

• Il valore del rilassamento lineare migliora da \(\frac{9}{2}\) a \(4\). Il bound arrotondato \(\lfloor \frac{9}{2} \rfloor = 4\) valeva già \(4\): una formulazione migliore non migliora sempre il bound arrotondato.

2.6 Bound duali

• Un bound duale si può ottenere anche senza risolvere il rilassamento lineare, combinando i vincoli con moltiplicatori non negativi \(\pi_i\), uno per ciascun vincolo.

Definizione 2.9: problema duale del rilassamento lineare

Il problema duale D(LP) del rilassamento lineare (2.2) è il seguente problema LP, con valore ottimo \(z(\mathrm{D(LP)})\):

\[\begin{align*} && \min \;\;{\sum_{i =1}^m b_i \, \pi_i} \label{ObjFunc_D} \tag{2.6a}\\[2ex] && \text{soggetto a} \quad {\sum_{i =1}^m a_{ij} \, \pi_i} &\geq c_j, & \forall j \in \{1,2,\dots,n\}, \label{Cons_D} \tag{2.6b}\\[2ex] &&\pi_i &\ge 0, & \forall i \in \{1,2,\dots,m\}. \label{non_negativity_D} \tag{2.6c} \end{align*}\]

• Moltiplicando il vincolo \(i\) per \(\pi_i \ge 0\) e sommando, otteniamo una disuguaglianza i cui coefficienti sono almeno pari ai costi, per \(\eqref{Cons_D}\). I moltiplicatori devono essere non negativi: un moltiplicatore negativo invertirebbe la disuguaglianza.

Proposizione 2.10: bound duali

Per ogni soluzione ammissibile \(\bar{\vet \pi}\) del problema duale (2.6),

\[ z(\ILP) ~\le~ z(\LP) ~\le~ \sum_{i=1}^m b_i \, \bar{\pi}_i . \]

Per la dualità forte, \(z(\mathrm{D(LP)}) = z(\LP)\): i moltiplicatori migliori danno esattamente il valore del rilassamento lineare.

Dimostrazione

Sia \(\vet x\) ammissibile per il rilassamento lineare. Moltiplicando il vincolo \(i\) per \(\bar{\pi}_i \ge 0\) e sommando, \(\sum_{j=1}^n \big( \sum_{i=1}^m a_{ij} \, \bar{\pi}_i \big) x_j \le \sum_{i=1}^m b_i \, \bar{\pi}_i\). Per \(\eqref{Cons_D}\) e \(x_j \ge 0\), il membro sinistro è almeno \(\sum_{j=1}^n c_j \, x_j\). Quindi \(\sum_{j=1}^n c_j \, x_j \le \sum_{i=1}^m b_i \, \bar{\pi}_i\) per ogni \(\vet x\) ammissibile. □

Ogni soluzione ammissibile del problema duale è il certificato di un upper bound, trovato senza risolvere il rilassamento lineare. Il certificato migliore è una soluzione duale ottima, e ha lo stesso valore del rilassamento lineare.

Esempio 2.9: moltiplicatori per l'esempio dell'auto

• Una soluzione ammissibile del rilassamento lineare non dà un bound duale: il suo valore non è né un lower bound né un upper bound su \(z(\ILP)\).

\((x_1, x_2)\)	ammissibile per il rilassamento lineare	intera	\(3\,x_1 + 2\,x_2\)
\((4, \frac{5}{4})\)	sì	no	\(\frac{29}{2} > 14\)
\((2, \frac{5}{2})\)	sì	no	\(11 < 14\)

• Moltiplicando il primo vincolo dell'esempio dell'auto per \(\frac{3}{4}\) otteniamo

  \[ \frac{15}{2}\,x_1 + 3\,x_2 \le \frac{135}{4}. \]

  Poiché \(x_1, x_2 \ge 0\) e i coefficienti \(\frac{15}{2}\) e \(3\) sono almeno pari ai costi \(3\) e \(2\), abbiamo \(3\,x_1 + 2\,x_2 \le \frac{15}{2}\,x_1 + 3\,x_2 \le \frac{135}{4}\): un upper bound pari a \(\frac{135}{4}\).

• Con i moltiplicatori \(\pi_1, \pi_2 \ge 0\) dei due vincoli, i coefficienti della somma devono essere almeno pari ai costi:

  \[\begin{align*} (10\,\pi_1 + 4\,\pi_2)\,x_1 + (4\,\pi_1 + 14\,\pi_2)\,x_2 &\le 45\,\pi_1 + 49\,\pi_2,\\ 10\,\pi_1 + 4\,\pi_2 \ge 3, \qquad 4\,\pi_1 + 14\,\pi_2 &\ge 2. \end{align*}\]

\((\pi_1, \pi_2)\)	moltiplicatori validi	upper bound \(45\,\pi_1 + 49\,\pi_2\)
\((\frac{3}{4}, 0)\)	sì	\(\frac{135}{4}\)
\((0, \frac{3}{4})\)	sì	\(\frac{147}{4}\)
\((\frac{1}{5}, \frac{1}{4})\)	sì	\(\frac{85}{4}\)
\((\frac{1}{2}, 0)\)	sì	\(\frac{45}{2}\)
\((\frac{1}{5}, 0)\)	no: \(10 \cdot \frac{1}{5} = 2 < 3\)	–

• I moltiplicatori migliori, con il valore più piccolo di \(45\,\pi_1 + 49\,\pi_2\), risolvono il problema duale (2.6) dell'esempio dell'auto:

\[ \begin{array}{rrrrrrr} {\min} & {45}\, {\pi_1} & {+} & {49}\, {\pi_2} \\[1ex] \text{soggetto a} & {10}\, {\pi_1} & {+} & {4}\, {\pi_2} & {\ge} & {3} \\[1ex] & {4}\, {\pi_1} & {+} & {14}\, {\pi_2} & {\ge} & {2} \\[1ex] & {\pi_1,} & & {\pi_2} & {\ge} & {0} \end{array} \]

Esempio 2.10: soluzione duale ottima dell'esempio dell'auto

La soluzione ottima del problema duale dell'Esempio 2.9 è \(\tilde{\vet \pi}(\mathrm{D(LP)}) = (\frac{17}{62},\frac{2}{31})\), e

\[ z(\mathrm{D(LP)}) = 45 \cdot \frac{17}{62} + 49 \cdot \frac{2}{31} = \frac{765}{62} + \frac{98}{31} = \frac{31}{2} = z(\LP). \]

Gli altri due vertici della regione ammissibile duale danno i bound \(\frac{45}{2}\) e \(\frac{147}{4}\).

La regione ammissibile del problema LP duale (rossa, illimitata) e la sua soluzione ottima \((\frac{17}{62},\frac{2}{31})\) (blu), con la retta obiettivo \(45\,\pi_1 + 49\,\pi_2 = \frac{31}{2}\) (tratteggiata). Gli altri vertici (neri) danno i bound \(\frac{45}{2}\) e \(\frac{147}{4}\).

2.6.1 Riepilogo della notazione

• Problema PLI: soluzione ottima \(\tilde{\vet x}(\ILP)\), valore ottimo \(z(\ILP)\).

• Bound primale: soluzione ammissibile \(\bar{\vet x}\) con \(\LB(\bar{\vet x}) = \sum_{j} c_j \, \bar{x}_j \le z(\ILP)\).

• Rilassamento lineare: soluzione ottima \(\tilde{\vet x}(\LP)\), valore ottimo \(z(\LP)\), upper bound \(z(\ILP) \le z(\LP)\).

• Problema duale: soluzione ottima \(\tilde{\vet \pi}(\mathrm{D(LP)})\), valore ottimo \(z(\mathrm{D(LP)}) = z(\LP)\), e \(z(\ILP) \le \sum_i b_i \, \bar{\pi}_i\) per ogni soluzione duale ammissibile \(\bar{\vet \pi}\).

2.7 Errori tipici

Attenzione

• Prendere una soluzione euristica per ottima. Una soluzione ammissibile dà solo un bound primale. Senza un bound duale dello stesso valore non c'è alcun certificato di ottimalità.

• Arrotondare il bound quando non è lecito. Il bound \(\lfloor z(\LP) \rfloor\) richiede che tutte le variabili e tutti i costi siano interi. In un problema MIP il bound è \(z(\LP)\).

• Arrotondare la soluzione e chiamarla ottima. Una soluzione arrotondata è, nel migliore dei casi, ammissibile, e in generale non ottima. Può anche essere inammissibile, come il punto intero più vicino \((2,5)\) dell'Esempio 2.6.

• Usare come bound il valore di una soluzione ammissibile del rilassamento lineare. Solo il valore ottimo del rilassamento lineare, o il valore di una soluzione duale ammissibile, è un upper bound.

• Moltiplicatori con segno negativo. I moltiplicatori dei vincoli \(\le\) devono essere non negativi, e i coefficienti combinati devono essere almeno pari ai costi.

• Ricavare un bound su una variabile da un vincolo con coefficienti negativi. La dimostrazione di \(\eqref{vub}\) richiede che tutti i coefficienti siano non negativi.

• Credere che una formulazione più forte migliori sempre il bound. I bound \(x_1 \le 4\) e \(x_2 \le 3\) lasciano invariato il bound \(15\) dell'esempio dell'auto.

2.8 In sintesi

In sintesi

• Ogni soluzione ammissibile è un bound primale (un lower bound) su \(z(\ILP)\), e gli algoritmi euristici trovano rapidamente buone soluzioni ammissibili.

• Il rilassamento lineare elimina l'integralità, quindi \(z(\ILP) \le z(\LP)\); con variabili intere e costi interi questo bound duale (un upper bound) si può arrotondare per difetto a \(\lfloor z(\LP) \rfloor\).

• Bound primale e bound duale definiscono il gap di ottimalità; l'ottimalità è certificata quando il gap è zero.

• Arrotondare una soluzione ottima del rilassamento lineare dà, nel migliore dei casi, una soluzione ammissibile, mai un certificato.

• Gli upper bound sulle variabili \(x_j \le \lfloor b_i / a_{ij} \rfloor\) vengono da vincoli con coefficienti non negativi, e servono solo se tagliano l'ottimo del rilassamento lineare.

• I moltiplicatori non negativi dei vincoli danno bound duali; i migliori risolvono il problema duale, il cui valore ottimo è \(z(\LP)\).

Cruscotto dell'esempio dell'auto. I bound su \(z(\ILP)\) trovati finora in questo modulo (bound primale: lower bound; bound duale: upper bound):

Capitolo	Lower bound	Upper bound	Da
Bound primali e bound duali	\(14\)	\(15\)	soluzione euristica \((4, 1)\), e \(\lfloor z(\LP) \rfloor\) con \(z(\LP) = \tfrac{31}{2}\)

---

Esercizi su questo capitolo: Bound primali e duali

Laboratorio interattivo

Le idee del capitolo, da toccare con mano: muovi i cursori e trascina i punti. Ogni app si apre anche a tutta pagina nel laboratorio interattivo: Punti interi e rilassamento lineare.