DM545: Linear and integer programming
Comment
The Course redeem 15012321 (formerly UVA) students who have previously followed this course offered a final reexam June 2019 on old terms.
The course is co-read with: DM559
The course cannot be chosen by students who: have passed DM559
Entry requirements
Academic preconditions
- 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
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 help
making better decisions. 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.
The aim of the course is to enable
the student to use mathematical modeling for solving practical
optimization problems and to work with a mathematical software system
for finding numerical solutions to the applications proposed. To reach
these goals the course will provide to the student knowledge on the
basics of linear programming and duality theory and on the main solution
techniques for linear and integer programming, such as the simplex
method, branch and bound and cutting planes.
The course builds on
the knowledge acquired in the course DM507, "Algorithms and Data
Structures" and gives an academic basis for doing a bachelor/master
thesis project and other theoretically or practically oriented
study-activities as well as for studying elective courses, that can be
chosen as part of the degrees in Mathematics-Economics, Applied
Mathematics and others.
In relation to the competence profile of the degree it is the explicit focus of the course to:
- Give the competence to handle complex and development-oriented 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 non-specialists 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 and 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
Obligatory tasks in the form of short-answer tests that are made during the course
EKA
Assessment
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
Indicative number of lessons
Teaching Method
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 tasks
Teacher responsible
Timetable
Administrative Unit
Team at Educational Law & Registration
Offered in
Recommended course of study
Profile | Education | Semester | Offer period |
---|---|---|---|
BSc.scient.oecon | BSc in Mathematics-Economics | Bachelor of Science in Mathematics-Economics | Odense | 4 | F20 |
BSc.scient.oecon | BSc in Mathematics-Economics | Bachelor of Science in Mathematics-Economics | Odense | 4 | E20, F21 |