Learning Outcomes
On completion of the course, students will be able to:
1. critically analyse and formulate practical problems within the class of general operations research problems, and situate them in a structured decision framework
2. design and justify formulations of practical problems, such as linear or integer programming models, while taking into account model assumptions and limitations
3. develop, implement, and evaluate algorithms for solving linear and integer programming problems, and analyse their computational efficiency
4. classify computational problems into complexity classes based on the computational resources that are required to obtain exact solutions, and discuss the implications for applications
5. design, implement, and evaluate heuristic and meta-heuristic approximation methods for addressing computationally intractable problems, and assess their performance relative to exact methods
6. analyse and quantify the complexity of complex dynamical systems, characterise their key properties, and distinguish them from random and chaotic systems.
1. critically analyse and formulate practical problems within the class of general operations research problems, and situate them in a structured decision framework
2. design and justify formulations of practical problems, such as linear or integer programming models, while taking into account model assumptions and limitations
3. develop, implement, and evaluate algorithms for solving linear and integer programming problems, and analyse their computational efficiency
4. classify computational problems into complexity classes based on the computational resources that are required to obtain exact solutions, and discuss the implications for applications
5. design, implement, and evaluate heuristic and meta-heuristic approximation methods for addressing computationally intractable problems, and assess their performance relative to exact methods
6. analyse and quantify the complexity of complex dynamical systems, characterise their key properties, and distinguish them from random and chaotic systems.
Course Content
The course covers the formulation and solution of linear programming problems that are computationally feasible, as well as how to empirically estimate computational resources in terms of storage, memory, and time requirements for various algorithms. For this class of problem, the Simplex method is introduced along with its properties. The course also addresses computationally intractable problems, such as integer programming problems, with a focus on why exact algorithms fail and what implications this has on practical applications. Approximation methods, including heuristic and meta-heuristic approaches, such as genetic algorithms, are introduced and analysed as alternatives in cases of intractability. The course also includes an overview of complex dynamic systems, with particular emphasis on describing, quantifying, and distinguishing their behaviour from random and chaotic systems. Duality in linear programming is discussed as well as how various algorithmic methods relate to classical operations research applications, such as stopping rules, network flows, game theory, scheduling, and process planning. The applications are used to contextualise decision problems and illustrate the models and methods included in the course.
Assessment
• Written report on an individual project
• Seminar
• Seminar
Grades
The Swedish grades U–G.
Prerequisites
- To be admitted, applicants must meet the general entry requirements for doctoral studies. Persons who have not been admitted to a doctoral programme at Dalarna University are admitted to the course depending on space availability.
Other Information
Replaces FMI2223.