Glossario · approach
Generazione di Colonne
Metodo di ottimizzazione su larga scala che genera decisioni candidate (colonne) a richiesta invece di enumerarle tutte in anticipo.
Column GenerationGenerazione Ritardata di Colonne
La generazione di colonne (column generation) è il metodo utilizzato quando elencare tutte le decisioni possibili (per esempio ogni schema di taglio, ogni rotta veicolo) è impraticabile. Parte da un insieme iniziale piccolo, risolve il problema e poi chiede matematicamente 'esiste una nuova decisione che migliorerebbe la soluzione?' aggiungendola se la risposta è sì. Sviluppato da Gilmore e Gomory nel 1961 per il Cutting Stock, oggi è il cavallo da tiro per problemi su larga scala come vehicle routing (VRP), crew scheduling e assegnazione del traffico aereo.
Örnek
Una sartoria ha in teoria milioni di possibili schemi di taglio. La generazione di colonne non li enumera — scopre uno per uno gli schemi che migliorano la soluzione e fornisce una soluzione quasi ottima in tempi pratici.