Complexity and Operations Research Methods for PhD-students

7.5 Credits
Third Cycle
School of Technology and Business Studies
Subject field
Microdata Analysis (MIKRODAT)
Approved, 04 October 2017.
This syllabus is valid from 04 October 2019.

Learning Outcomes

Upon completion of the course, the PhD-student shall be able to:

• frame a practical problem in to the general class of OR problems and within a decision framework,
• represent a practical problem as a linear programming problem,
• represent a practical problem as an integer programming problem,
• implement algorithms to solve linear and integer programming problems,
• classify problems into complexity classes according to the computational resources required to solve them exactly,
• identify and implement approximate (heuristic and stochastic) solution methods for attacking computationally intractable problems.

Course Content

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 prob-lems and duality are also introduced. The students will explore and understand how classical solution methods such as linear programming and dynamic programming break down in intractable cases. The course will introduce advanced algorithms to solve in-tractable problems. Alternative solution methods such as stochastic and heuristic approximation methods. The application of the methods is contextualized by relating them to the classical and general OR problems such as Game Theory, Stopping, Scheduling, and Network Analysis.


Individual project to be reported and an examining seminar.

Forms of Study

Lectures, compulsory laboratories, and independent studies


The Swedish grades U–G.


  • Degree of Master 60 credits in Microdata Analysis