Q774 - Combinatorial Optimization: Complexity and Heuristics
The first part of the course will focus on solvable network flow problems such as assignment, transportation, transshipment, shortest path, max flow and minimum spanning tree problems. Well known algorithms (such as Dijkstra, Bellman-Ford and Augmenting path algorithm) will be discussed as well as general methodology such as lifting procedures polyhedral theory (strong valid inequalities). The second part will focus on complexity theory and heuristic methods and covers NP-Completeness, Approximation algorithms, local and random search, and metaheuristics (such as Ant colony, genetic algorithms, simulated annealing and tabu search). GAMS and a general purpose programming language (e.g., C, Matlab or Python) will be used in a computational project.
- Prerequisite: Q773 or permission of the instructor
Course Offerings Archive Submission Form
If you need an outline from an earlier semester, please use this form to contact us. Outlines for current and future courses will be posted here on the website as they become available.