La separazione, o generazione di tagli validi, è una tecnica classica per risolvere problemi di programmazione lineare intera con algoritmi del tipo branch and cut.
Dalla tesi di Giuseppe Andreello, curata dal prof. Matteo Fischetti, possiamo imparare molte cose. Di seguito il sommario della tesi.
Dalla tesi di Giuseppe Andreello, curata dal prof. Matteo Fischetti, possiamo imparare molte cose. Di seguito il sommario della tesi.
Sommario
Problema considerato L'oggetto di questo lavoro di tesi `e stato testare l'efficacia dei tagli 0-1/2 usando Ilog CPLEX8, un ambiente per la programmazione lineare intera.
Come è stato risolto E' stata studiata una strategia di applicazione del separatore e di selezione dei tagli generati sulla base delle loro caratteristiche geometriche. Una implementazione in C++ di queste nuove funzionalità è stata affiancata all'implementazione originale, in C, della procedura di separazione.
Risultati principali I tagli 0-1/2 sono particolarmente efficaci per le versioni “lp” dei problemi di “satisfiability” e “maximum satisfiability”, la cui struttura è di tipo combinatorio. Più in generale si riescono a generare facilmente e sembrano essere utili per problemi la cui formulazione lp ha un numero di vincoli molto maggiore del numero di variabili. Nel caso opposto, invece, si generano con molta difficoltà e influenzano poco la soluzione del problema.
Significato dei risultati I tagli 0-1/2 sono utili in casi abbastanza semplici da individuare.
Inoltre, si è dimostrata molto efficace la selezione dei tagli da aggiungere alla formulazione sulla base delle loro proprietà geometriche.
Commenti