Optimization 3, 7.5 credits

Contents

The course consists of two parts.
 
Part 1 (6.0 hp): Mathematical theory of integer programming. In this part the general theory of integer programming is treated. The emphasis is placed on properties of integer programs and techniques for solving them. Methods covered include cutting planes, branch and bound and dynamic programming. Different families of cutting planes are studied and used both for solving and providing stronger formulations of integer programs. Heuristics for finding improved upper and lower bounds of the objective function are covered, for example greedy methods and LP and Lagrange relaxation. The concepts convex hull and total unimodularity are treated. Introductory complexity theory is presented with examples of problems from different complexity classes and how polynomial reduction can be used between different problems.
 
Part 2 (1.5 hp): Lab assignements. 
In this part of the course a selected technique for solving an integer program is implemented.

Expected learning outcomes

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

• account for som heuristic methods in integer optimization
• account for the theory of cutting planes
• account for and give examples of the complexity classes P, NP, NPC and NP-hard

Skills

• apply branch and bound and cutting plane methods
• apply heuristics to bound the objective function
• perform simple reductions between different problems
• using computer aid to attack integer problems by the techniques treated in the course

Judgement and approach

• gauge the complexity of integer problems
• select appropriate techniques for attacking integer problems.

Required Knowledge

A course in linear programming, minimum 7,5 ECTS credits and basic programming courses, at least 15 ECTS credits. Proficiency in English equivalent to Swedish upper secondary course English A (IELTS (Academic) with a minimum overall score of 5.5 and no individual score below 5.0. TOEFL PBT (Paper-based Test) with a minimum total score of 530 and a minimum TWE score of 4. TOEFL iBT (Internet-based Test) with a minimum total score of 72 and a minimum score of 17 on the Writing Section). 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 conducted through lectures and problem solving sessions. The teaching on part 2 is conducted through laborations and seminars. 

Examination modes

The examination of part 1 is in the form of a written test.The examination of part 2 is in the form of seminars and written lab reports.