Complexity and Operations Research Methods

On completion of this course, students shall be able to:

• represent a practical problem as a linear programming problem
• represent a practical problem as an integer programming problem
• implement algorithms that solve linear and integer programming problems
• classify problems into different forms of complexity according to the computational resources required to arrive at an exact solution,
• identify and implement approximate (heuristic and stochastic) solution methods for attacking computationally intractable problems.

The course will give a firm understanding of tractable problems and how to empirically estimate the computational resources (storage and time) required by an algorithm. Classic algorithms such as simplex method and big M method will be introduced to solve tractable problems. In addition, intractable problems such as integer programming problems are also introduced. The students will explore how classical solution methods such as linear programming and dynamic programming break down in intractable cases. The course will introduce advanced algorithms to solve intractable problems. Students study alternative solution methods such as stochastic and heuristic approximation methods such as tabu search, branch and bound, relaxation, genetic algorithms and simulated annealing.

Individual project. For assessment, students must actively participate in at least two thirds of the timetabled laboratories.

Lectures and compulsory laboratories. At each laboratory, the student receives an assignment, and feedback on this assignment is provided at the end of each laboratory.

The Swedish grades U–VG.