Discrete Modelling, 7.5 Credits

Contents

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.

Expected learning outcomes

For a passing grade, the student must be able to

Knowledge and understanding

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

Skills

• independently formulate integer-, graph- and model and SAT-models for given problem situations
• independently perform 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 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

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

Element 1 is examined by written accounts of modelling a given problem, and by a written exam on modelling theory. Element 2 is examined by written lab reports. On Element 1, one of the following judgements is assigned: Fail (U), Pass (3), Pass with merit (4) or Pass with distinction (5). On Element 2, one of the following judgements 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 students have the possibilty to raise a passed grade to a higher grade through voluntary extra assignments. The bonus points awarded for the extra assignments are only valid on the first two examinations when the course is given.

Deviations from the syllabus examination form can be made for a student who has a decision on pedagogical support due to disability. Individual adaptation of the examination form shall be considered based on the student's needs. The examination form is adapted within the framework of the expected learning outcomes of the course syllabus. At the request of the student, the course coordinator, in consultation with the examiner, must promptly decide on the adapted examination form. The decision shall then be communicated to the student.

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 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.

Other regulations

This course can not be included in a degree together with another course with similar contents. When in doubt, the student should consult the director of study at the department of mathematics and mathematical statistics