Review of linear programming, computational complexity and graph theory. Shortest path problems: algorithm for acyclic graphs, Dijkstra\'s algorithm, Floyd-Warshall\'s algorithm. Max flow problem: Ford-Fulkerson\'s and Edmonds-Karp\'s algorithms. Matching problems. Assignment problem: Hungarian algorithm. Min cost flow problems: network simplex algorithm. Minimum spanning trees. The traveling salesperson problem (TSP): formulations and solution approaches.
Formulation of optimization problems having network structure.
Dipartimento di Ingegneria dell'Informazione e Scienze Matematiche - Via Roma, 56 53100 SIENA - Italy
