Generazione di colonne

Generazione di colonne o generazione di colonne ritardate è un algoritmo efficiente per risolvere programmi lineari di grandi dimensioni.

L’idea generale è che molti programmi lineari sono troppo grandi per considerare tutte le variabili in modo esplicito. La premessa è che la maggior parte delle variabili sarà non di base e assumerà un valore pari a zero nella soluzione ottimale. Per questo motivo, solo un sottoinsieme di variabili deve essere considerato in teoria quando si risolve il problema. La generazione di colonne sfrutta questa idea per generare solo le variabili che hanno il potenziale per migliorare la funzione oggettiva, ovvero trovare variabili con costi ridotti negativi (assumendo senza perdita di generalità che il problema sia un problema di minimizzazione).

Il problema da risolvere è diviso in due problemi: il problema principale e il sottoproblema. Il problema principale è il problema originale con solo un sottoinsieme di variabili considerato. Il sottoproblema è un nuovo problema creato per identificare una nuova variabile. La funzione oggettiva del sottoproblema è il costo ridotto della nuova variabile rispetto alle variabili duali attuali e i vincoli richiedono che la variabile obbedisca ai vincoli naturali.

Il processo funziona come segue. Il problema principale è risolto—da questa soluzione, siamo in grado di ottenere prezzi doppi per ciascuno dei vincoli nel problema principale. Questa informazione viene quindi utilizzata nella funzione obiettivo del sottoproblema. Il sottoproblema è risolto. Se il valore oggettivo del sottoproblema è negativo, è stata identificata una variabile con costo negativo ridotto. Questa variabile viene quindi aggiunta al problema principale e il problema principale viene risolto nuovamente. La risoluzione del problema principale genererà una nuova serie di valori doppi e il processo viene ripetuto fino a quando non vengono identificate variabili negative di costo ridotto. Il sottoproblema restituisce una soluzione con costi ridotti non negativi, possiamo concludere che la soluzione al problema principale è ottimale.

In molti casi, ciò consente di risolvere programmi lineari di grandi dimensioni che erano stati precedentemente considerati intrattabili. L’esempio classico di un problema in cui questo viene utilizzato con successo è il problema delle scorte di taglio. Una tecnica particolare nella programmazione lineare che utilizza questo tipo di approccio è l’algoritmo di decomposizione di Dantzig–Wolfe. Inoltre, la generazione di colonne è stata applicata a molti problemi come la pianificazione dell’equipaggio, il routing del veicolo e il problema p-mediano capacitato.

Questo articolo relativo alla matematica applicata è uno stub. Puoi aiutare Wikipedia espandendolo.