In questa pagina sono disponibili alcuni codici didattici in C++ che illustrano alcune delle tecniche modellistiche ed algoritmiche sviluppate durante corso per la soluzione di semplici varianti di problemi di ottimizzazione rilevanti in ambito logistico.
Per l'uso di questi codici può essere necessario scaricare solutori generali open-source di problemi di ottimizzazione dai siti dei corrispondenti progetti, come MCFClass oppure COIN OR, oppure Sorsa. I codici sono in C++ "puro" (output su console, input da console o file) e sono provvisti di semplici makefiles Unix; l'uso su altre architetture dovrebbe essere immediato.
una piccola collezione di istanze artificiali oppure prese dai principali repositories (si veda readme.txt).
cwl1: soluzione del rilassamento continuo del problema (sia in versione con flusso splittabile che non splittabile, visto che i due rilassamenti coincidono) mediante riformulazione come Flusso di Costo Minimo ed uso di un solutore MCFClass. Per il caso con flusso splittabile viene inoltre generata una soluzione ammissibile a partire dalla soluzione del rilassamento con una banale euristica di arrotondamento.
cwl2: soluzione del problema (sia in versione con flusso splittabile che non splittabile), o del suo rilassamento continuo, mediante uso di un solutore OsiSolverInterface. Il modello viene costruito lavorando direttamente con sulla matrice dei coefficienti (addRow() e addCol(), sul solutore oppure su un oggetto intermedio CoinModel), e sono disponibili opzioni per l'output del modello su file, eventualmente con "nomi carini per le righe e le colonne".
cwl3: soluzione del problema (sia in versione con flusso splittabile che non splittabile), o del suo rilassamento continuo, mediante uso di un solutore OsiSolverInterface col modello costruito in FlopC++. Questa versione disabilita le disuguaglianze valide nel solutore per mostrarne l'impatto sulle prestazioni.
cwl4: soluzione del rilassamento Lagrangiano del problema: mediante OsiCbcSolverInterface per il caso del flusso non splittabile, e mediante Greedy CUD per quello del flusso splittabile. Determinazione di una soluzione ottima per banale euristica di arrotondamento sulla soluzione del rilassamento continuo, e soluzione (approssimata) del Duale Lagrangiano per ridurre il gap attraverso un semplice metodo del subgradiente.
cwl5: simile al precedente, ma il Duale Lagrangiano viene risolto da un algoritmo dei piani di taglio (decomposizione di Dantzig-Wolfe), in versione aggregata o disaggregata e con "fase 0", il cui master problem è risolto da un OsiSolverInterface. Inoltre, l'euristica di arrotondamento viene effettuata sulla soluzione del "rilassamento convessificato" invece che su quella del rilassamento continuo.
cwl6: simile al precedente, ma il Duale Lagrangiano viene risolto da un algoritmo "Bundle" in versione aggregata con un solutore di master problem (quadratico) specializzato. Inoltre, l'euristica ricalcola in modo ottimo la componente "di flusso" del problema, sia nel caso splittabile che in quello non splittabile, mediante un OsiSolverInterface.
kcover: separazione delle cover inequalities ed analisi del loro impatto sulla valutazione superiore prodotta dal rilassamento continuo. La separazione può essere effettuata in modo esatto mediante un solutore OsiCbcSolverInterface, oppure in modo approssimato mediante la classica euristica Greedy CUD, eventualmente seguita da una semplice ricerca locale (2-scambio).
kdp: soluzione del problema (con pesi interi) attraverso il classico algoritmo pseudo-polinomiale di Programmazione Dinamica, e confronto dei risultati con quelli ottenuti da un OsiCbcSolverInterface.
una piccola collezione di istanze artificiali oppure prese dai principali repositories (si veda readme.txt).
kant: soluzione (si fa per dire) della formulazione di Kantorovich mediante un OsiCbcSolverInterface, con il modello costruito in FlopC++. La formulazione comprende alcune banali tecniche di riduzione della simmetria.
gg: soluzione del rilassamento continuo della formulazione di Gilmore e Gomory del problema mediante generazione di colonne: il problema di pricing (knapsack intero) è risolto mediante un OsiCbcSolverInterface mentre il master problem (con "tripper" iniziali) è risolto mediante un OsiClpSolverInterface. Una banale euristica greedy (Largest Items First) è utilizzata per produrre una valutazione superiore con la quale stimare il gap della formulazione. Al termine la formulazione "congelata" viene risolta mediante solutore PLI per determinare un'altra soluzione euristica.