This syllabus is valid: 2015-01-12
and until further notice
Course code: 5MA155
Credit points: 7.5
Education level: Second cycle
Main Field of Study and progress level:
Mathematics: Second cycle, has only first-cycle course/s as entry requirements
Grading scale: TH teknisk betygsskala
Responsible department: Department of Mathematics and Mathematical Statistics
Established by: Faculty Board of Science and Technology, 2015-01-08
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.
