Part 1 (4,5 hp): Theory of discrete modelling. This part of the course treats theory for discrete modelling, from problem formulation and choice of model, via specific model formulation and implementation, to evaluation of appropriateness and effectiveness of the model.
This part of the course starts with general theory for formulating an integer program from a given problem description, and general theory for SAT formulations of optimization and decision problems. In connection to this, complexity theory and the general theory of polynomial reduction from one problem to another. Integer formulations and SAT formulations are then connected to different classes of graph models, in particular network flow problems, matchings, shortest path, graph colouring and the travelling salesman problem. Both exact and heuristic models are studied with regard to effectiveness. Following this, concrete large scale examples of applied discrete modelling are studied, and an introduction to literature search in the area of discrete modelling is given. The theory is concluded with an introduction to simulation using randomized scenarios.
Part 2 (3 hp): Lab assignment. This part of the course treats implementation of discrete models, and comparisons between different formulations as regards computational efficiency. Further, simulation methods for discrete models are implemented.
In a degree, this course may not be included together with another course with a similar content. If unsure, students should ask the Director of Studies in Mathematics and Mathematical Statistics. The course can also be included in the subject area of computational science and engineering.
The information below is only for exchange students
Starts
1 November 2024
Ends
3 December 2024
Study location
Umeå
Language
English
Type of studies
Daytime,
100%
Required Knowledge
The course requires 90 ECTS including 15 ECTS in Computer Programming, a course in Linear Programming, a course in Integer Programming on advanced level and a basic course in Mathematical Statistics or equivalent. Proficiency in English and Swedish equivalent to the level required for basic eligibility for higher studies
Selection
Students applying for courses within a double degree exchange agreement, within the departments own agreements will be given first priority. Then will - in turn - candidates within the departments own agreements, faculty agreements, central exchange agreements and other departmental agreements be selected.
Application code
UMU-A5820
Application
This application round is only intended for nominated exchange students. Information about deadlines can be found in the e-mail instruction that nominated students receive.
The application period is closed.
