Problemi di Ottimizzazione Lineare Intera

Programmazione Lineare Intera

Consideriamo problemi del tipo:

Problema PLI

Osservazione

Osservazione

La regione ammissibile di un problema intero non è convessa. In generale possono esservi alcune variabili continue e alcune intere. Si parla in tal caso di PLI mista (che non trattiamo)

Esempio

Esempio Grafico PLI

Se risolviamo il problema senza vincolo di interezza, l’ottimo sarebbe .

Altrimenti:

• Soluzione ottima intera:
• Soluzione arrotondata:

Come è ovvio vedere, non è possibile risolvere il problema intero eliminando il vincolo di interezza e risolvendo il problema continuo approssimando la soluzione.

Bisogna necessariamente risolvere il problema intero.

Relazioni problemi lineari < - > interi

Rilassamento Lineare

Dato un problema PLI (definito sopra), è possibile ottenere un Rilassamento Lineare (RL), o continuo:

• Risulta che , cioè la regione ammissibile del problema di PLI è data dalla soluzione intera del poliedro P.

• Inoltre , cioè la reigone ammissibile del problema PLI è sempre contenuta nel poliedro P.

Si ha che il valore ottimo di (RL) è sempre del valore ottimo di (PLI):

Infine:

Se la soluzione ottima di (RL) è intera è soluzione del problema (PLI).

Involucro Convesso

Dato un insieme discreto, esistono diversi poliedro che lo contengono. Il poliedro più interessante è l’Involucro Convesso (Convex Hull), e cioè il più piccolo insieme convesso che contiene i punti discreti.

L’involucro convesso ha solo vertici interi, si potrebbe quindi risolvere il problema continuo usando l’involucro convesso come insieme dei vincoli:

Il problema da risolvere è detto Rilassamento Convessificato e si ottiene la soluzione intera cercata.

In generale però, non è facile costruire . Servono dei metodi per costruirlo.

Metodo dei piani di taglio (Generico)

Metodo dei piani di taglio

Consideriamo il problema intero di prima:

Taglio

Sia una disuguaglianza verificata , essa si chiama Taglio se non è verificata dalla soluzione ottima del (RL)

Gli algoritmi dei piani di taglio risolvono una successione di problemi continui, ottenuti aggiungendo ogni volta un taglio, fino ad ottenre una soluzione intera.

Schema Generale:

1. Si risolve il (RL), se è intera
2. Si genera un taglio (nuovo vincolo!)
   • Tale che
   • Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
3. Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo

Procedimento ed Efficienza

È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.

A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.

Implementazioni:

Una implementazione è il Metodo dei Tagli di Gomory.

Link to original

Metodo di Gomory (Implementazione piani di taglio)

Metodo dei Tagli di Gomory

Schema Generale:

1. Si risolve il (RL), se è intera
2. Si genera un taglio (nuovo vincolo!)
   • Tale che
   • Significa: Il taglio è verificato da tutti i punti interi, ma non è soddisfatto dall’ottimo del rilassamento continuo.
3. Si risolve il nuovo problema continuo con l’aggiunta del nuovo vincolo

Procedimento ed Efficienza

È un processo molto lungo ed estenuante da fare a mano, per questo in teoria esistono i computer, che possono operare più tagli contemporaneamente per migliorare l’efficienza, ma noi siamo studenti universitari e quindi abbiamo meno diritti delle macchine.

A seconda della scelta del taglio si hanno diversi algoritmi, ma resta comunque l’idea comune di fondo di approssimare l’involucro convesso mediante l’inserimento dei tagli.

Link to original

Metodo di Gomory

Genera il taglio sfruttando la tabella finale del Simplesso del Rilassamento Lineare (RL).

In particolare, usa la riga della tabella associata ad una componente frazionaria della soluzione ottima del (RL).

Sia data la tabella finale della risoluzione del RL:

— WIP

• è frazionario.

non è intero, supponiamo che non sia intero.

Procedimento

Scriviamo la riga esima:

e consideriamo i floor dei coefficienti:

Questo è il taglio di Gomory in forma intera.

Il taglio va aggiunto al rilassamento lineare dopo averlo reso standard. Si aggiunge il vincolo standard:

Come precedentemente detto, la convergenza è lenta. I primi tagli risultano più efficaci, ma lo sono meno continuando ad iterare l’algoritmo.

Se si opera un taglio alla volta e ci sono più valori frazionari si sceglie sempre la riga con indice minore, oppure quella con termine noto che ha la parte frazionaria maggiore.

Esempio (Grafico, lungo)

EH, VOLEVI! wip.

Link to original