Generazione di colonne - Column generation

La generazione di colonne o la generazione di colonne ritardata è un algoritmo efficiente per la risoluzione di programmi lineari di grandi dimensioni .

L'idea generale è che molti programmi lineari sono troppo grandi per considerare esplicitamente tutte le variabili. La premessa è che la maggior parte delle variabili sarà non di base e assumerà un valore zero nella soluzione ottima. 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 obiettivo, cioè per trovare variabili con costo ridotto negativo (assumendo senza perdita di generalità che il problema sia un problema di minimizzazione).

Il problema da risolvere è suddiviso 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 obiettivo del sottoproblema è il costo ridotto della nuova variabile rispetto alle attuali variabili duali, ei vincoli richiedono che la variabile obbedisca ai vincoli presenti in natura.

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

In molti casi, ciò consente di risolvere programmi lineari di grandi dimensioni che in precedenza erano stati considerati intrattabili. Il classico esempio di un problema in cui questo viene utilizzato con successo è il problema del taglio stock . 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 percorso dei veicoli e il problema della mediana p capacitata .