Integer Programming, 7.5 Credits

Contents

The course consists of two elements.

Element 1 (6.0 credits): Mathematical theory for integer optimisation.
This element provides specialised knowledge of optimisation. Particular focus is placed on the properties of integer programmes and techniques used to solve these. Methods include dynamic programming, branch-and-bound and cutting planes. Different families of cutting planes are studied and utilised to solve and provide stronger formulations of integer problems. Heuristics for finding good upper and lower bounds of the objective function are discussed, including greedy techniques and linear program or Lagrangian relaxation. The concepts of convex hull and total unimodularity are discussed. An introduction is given to complexity theory, with examples of problems of different complexity classes.
 
Element 2 (1.5 credits): Computer lab work.
In this element, computers are used to implement and apply some technique for integer optimisation.

Expected learning outcomes

For a passing grade, the student must be able to
 
Knowledge and understanding

• account in detail for the theory of integer programming
• account for some heuristics in integer programming
• account in detail for the theory of the cutting plane method
• explain and examplify the notion complexity class

Skills and abilities

• independently solve integer problems
• use computer aid in order to implement and apply techniques for integer optimization
• communicate questions, methods and results in written form 

Judgment and approach

• select suitable techniques in order to attack given integer problems
• critically apply heuristics in order to limit the goal function

Required Knowledge

The course requires 90 ECTS including 15 ECTS in Computer Programming, a course in Linear Algebra and a course in Linear Programming. Proficiency in English and Swedish equivalent to the level required for basic eligibility for higher studies.

Form of instruction

The teaching in element 1 takes the form of lectures and lessons. The teaching in element 2 takes the form of supervised lab work.

Examination modes

Element 1 is assessed through a written examination . Element 2 is assessed through written lab reports. For Element 1, one of the following judgements is awarded: Fail (U), Pass (3), Pass with merit (4), Pass with distinction (5). For Element 2, one of the following judgements is awarded: Fail (U) or Pass (G). For the course as whole, one of the following grades is awarded: Fail (U), Pass (3), Pass with merit (4), Pass with distinction (5). The grade for the whole course is determined by the grade given for Element 1. To pass the whole course, all elements must have been passed. The grade is only set once all compulsory elements have been assessed.

A student who has been awarded a passing grade for the course cannot be reassessed for a higher grade. Students who do not pass a test or examination on the original date are given another date to retake the examination. A student who has sat two examinations for a course or a part of a course, without passing either examination, has the right to have another examiner appointed, provided there are no specific reasons for not doing so (Chapter 6, Section 22, HEO). The request for a new examiner is made to the Head of the Department of Mathematics and Mathematical Statistics. Examinations based on this course syllabus are guaranteed to be offered for two years after the date of the student's first registration for the course.
 
Credit transfers
Students are entitled to an assessment of whether previous education or equivalent knowledge and skills acquired in professional experience can be accredited for equivalent studies at Umeå University. Applications for credit transfers must be sent to Student Services/Degree Evaluation Office. More information on credit transfers can be found on Umeå University's student website, www.student.umu.se, and in the Higher Education Ordinance (Chapter 6). Rejected applications for credit transfers can be appealed (Higher Education Ordinance, Chapter 12) to the Higher Education Appeals Board. This applies regardless of whether the rejection relates to all or parts of the credit transfer application.

Other regulations

In a degree, this course may not be included together with another course with a similar content, such as Optimisation 3 (5MA155). 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.