DeGroote School of Business

Course Description

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

Winter 2019

Code Section Outline
Q774 C01 Outline

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.

You can request outlines from earlier semesters. Outlines for current (and future) courses will be posted here as they become available.
This field is for validation purposes and should be left unchanged.