Course Code & Number:
Level of Course:
Pre-requisites & Co-requisites:
The fundamental goal of this course is to provide a framework to solve optimization problems with discrete or integer variables. The course aims to teach the modeling, relaxing and bounding techniques. The topics will also include complexity theory, cutting plane algorithms, heuristics and approximation algorithms.
Modeling, relaxing and bounding techniques. Fundamental easy-to-solve problems. Matching and assignment problems. Dynamic programming. Complexity theory. Branch-and-bound method. Meta-heuristics such as tabu search, genetic algorithms and variable neighborhood search. Application examples.
Upon succesful completion of this course, a student will be able to
1. Model optimization problems with discrete or integer variables. (e)
2. Use relaxing and bounding techniques in discrete models (e)
3. Apply heuristic methods and approximation algorithms to find good solutions to integer programming models (a)
4. Use the branch and bound algorithm and the cutting plane algorithm for solving integer programming problems. (e)
5. Analyze the efficiency and complexity of algorithms (b)