DM871: Linear and Integer Programming
Comment
The course cannot be chosen by students who: have passed DM559: Linear and Integer Programming (7,5 ECTS)
Entry requirements
Academic preconditions
Students taking the course are expected to:
 Have knowledge of the content of the course: DM507, "Algorithms and Data Structures" or acquiring this knowledge at the same time as the course runs
 Have knowledge of Linear Algebra
 Be able to program
Course introduction
Linear and Integer programming is a field at the intersection between mathematics and computer science that has seen a huge development in the last 60 years. It provides the tools that are at the core of operations research, the discipline that provides analytical methods to aid decision making. The main focus of linear and integer programming is on resource constrained optimization problems that can be described by means of linear inequalities and a linear objective function. These problems may arise in all contexts of decision making, such as manufacturing, logistics, health care, education, finance, energy supply and many others. The subject of the course therefore has an enormous practical relevance.
 Give the competence to handle complex and developmentoriented situations in academic and work settings
 Give skills to describe, analyze and solve mathematical problems with the application of methods and modeling formalisms from the areas of mathematics and computer science
 Give skills to take and justify decisions on a mathematical basis
 Give skills to describe, formulate and communicate problems and results to either peers and nonspecialists or partners and users
 Give knowledge and understanding of how certain optimization problems can be solved by means of linear and integer programming
 Give knowledge of how to understand and reflect on theories, methods and practices in a specific area of mathematics
Expected learning outcome
The learning objective of the course is that the student demonstrates the ability to:
 formulate a mathematical (linear) model from a given problem description in words.
 derive the dual program of a given linear program.
 apply the simplex method to simple linear programs.
 apply the branch and bound technique to small example problems.
 derive Gomory cuts and apply the cutting plane algorithm in small example problems.
 apply the theory from the course to practical optimization problems such as flows in networks, matching problems, packing problems, simple scheduling problems etc.
 use computer software for solving linear and integer programs.
 think innovative by seeing possibilities for applying theoretical knowledge in the industry.
Content
 Linear programming and the simplex method
 Duality theory
 Integer programming: branch and bound and cutting plane algorithms
 Min cost flow problem and its applications
 Software for solving linear and integer programming problems
Literature
Examination regulations
Exam element a)
Timing
Tests
Compulsory assignments in the form of shortanswer tests that are made during the course.
EKA
Censorship
Grading
Identification
Language
Examination aids
Allowed, a closer description of the exam rules will be posted under 'Course Information' on Blackboard.
ECTS value
Additional information
All tests during the classes must be attended. The schedules will be agreed with the participants.
The examination form for reexamination may be different from the exam form at the regular exam.
Indicative number of lessons
Teaching Method
At the faculty of science, teaching is organized after the threephase model ie. intro, training and study phase.
In the intro phase, concepts, theories and models are introduced and put into perspective. In the training phase, students train their skills through exercises and dig deeper into the subject matter.
Educational activities
 Reading from text books
 Solving homeworks
 Applying acquired knowledge to practical projects
Teacher responsible
Timetable
29 
Monday
13072020

Tuesday
14072020

Wednesday
15072020

Thursday
16072020

Friday
17072020


08  09  
09  10  
10  11  
11  12  
12  13  
13  14  
14  15  
15  16 