Discrete Modelling

Education facts

Code: 5MA174

The course consists of two parts. Module 1 (4.5 ECTS): 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 matchings, the travelling salesman problem. In addition to this, Hamilton cycles, Euler cycles, assignment problems and stable matchings are studied. Both exact and heuristic models are studied with regard to effectiveness. Artificial intelligence is treated by means of an introduction to genetic algorithms, especially for the travelling salesman problem. 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. Module 2 (3 ECTS): Lab assignment. This part of the course treats implementation of discrete models, and comparisons between different formulations as regards computational efficiency. To handle problems where solution to optimality is not feasible, simulation methods for discrete models are implemented. Finally, methods from the broadly construed area of artificial intelligence are treated, such as genetic algorithms and simulated annealing.

Entry requirements

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

Education offerings

Each offering has its own dates and conditions. Closed offerings are retained as history and do not mean that a new application is open.

• Discrete Modelling

  Umeå University

  Start date: 2 November 2026

  End date: 17 January 2027

  Pace of study: 50 %