Discrete Modelling, 7.5 Credits

Contents

The course consists of two parts.

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.

Expected learning outcomes

For a passing grade, the student must be able to

Knowledge and understanding

• account for the theory of discrete modelling
• account for SAT formulations and their connection to complexity theory and problem reduction

Skills

• formulate an integer model and a SAT-model for a given problem situation
• formulate a graph model for certain problem types
• perform simple reductions from one problem type to another
• account for the modelling of a concrete problem orally and in written form
• generate scenarios for testing models

Judgement and approach

• assess appropriateness and efficiency for different model formulations
• assess the possibility of exact solutions and approximations of solutions for different instances of the types of problems treated in the course
• independently find literature and assess its relevance and usefulness

Required Knowledge

The course requires 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 equivalent to Swedish upper secondary course English 5/A. Where the language of instruction is Swedish, applicants must prove proficiency in Swedish to the level required for basic eligibility for higher studies.
 

Form of instruction

The teaching on part 1 is in the form of lectures, problem solving sessions and seminars. The teaching on part 2 is in the form of introductory lectures, supervision of laborations and seminar treatment of lab report drafts.

Examination modes

Part 1 is examined by written or oral accounts of modelling a given problem, and by a written exam on modelling theory.
Part 2 is examined by written lab reports (U/G).
On part 1, one of the following grades is assigned: Fail (U), Pass (3), Pass with merit (4) or Pass with distinction (5). On part 2, one of the following grades is assigned: Fail (U) or Pass (G). For the whole course, one of the following grades is assigned: Fail (U), Pass (3), Pass with merit (4) or Pass with distinction (5). In order to receive a passing grade on the course, all parts must be completed with a passing grade. The course grade constitutes a summary of the results on all examination and is assigned only when all mandatory examination has been completed. A student who has received a passing grade on a test is not allowed to retake the test in order to receive a higher grade.

A student who has not received a passing grade after participating in two tests has the right to be assigned another examiner, unless there are certain circumstances prohibiting this (see the Higher Education Ordinance, chapter 6, 22§). A request to be assigned another examiner should be adressed to the head of department for the department of mathematics and mathematical statistics. The possibility of being examined based on the current version of the syllabus is guaranteed for at least two years following the student's first participation in the course.

Credit transfer
All students have the right to have their previous education or equivalent, and  their working life experience evaluated for possible consideration in the corresponding education at Umeå university. Application forms should be adressed to Student services/Degree evaluation office. More information regarding credit transfer can be found on the student web pages of Umeå university, http://www.student.umu.se, and in the Higher Education Ordinance (chapter 6). If denied, the application can be appealed (as per the Higher Education Ordinance, chapter 12) to Överklagandenämnden för högskolan. This includes partially denied applications.