|Class Hours - Lab Hours||3 - 0|
Introduction to graph theory for networks. Network Flow Problems, flow composition. Minimum cost flow, multicommodity flows, network flow algorithms. Discrete network optimization problems. Shortest path problems, label setting/correcting, auctions. Maximum flow, minimum cut, Ford-Fulkerson algorithm, price-based algorithms. Minimum Cost Flow Problems, dual problem, Simplex. Problems with integral constraints, Lagrange relaxation. Approximation algorithms for NP-hard problems, performance bounds, scheduling examples. Travelling salesman, Steiner tree. Geometric problems. Online algorithms. Monte Carlo methods. Taboo search, genetic algorithms, simulated annealing.