DM85: Networks and Integer Programming (10 ECTS)

STADS: 1506542

Level


Teaching period

Spring semester

Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

Prerequisites:
None

Academic preconditions:
The content of DM02, MM02 and DM19 must be known.

Course introduction
To provide the students with a solid knowledge of a very important optimization tool, which is applicable everywhere one meets optimization problems of a discrete nature. We will focus on industrial applications such as construction of (telephone) networks, transportation and scheduling problems and production planning. Together with the course DM63 on metaheuristics this course forms a package which will enable the students to formulate and solve a number of important optimization problems. The participants will learn how to formulate network and integer programming problems, as well as use some of the simpler optimization methods for these. They will also obtain experience in using a commercial products, such as ILOGs CPLEX solver, for solving large optimizationproblems. There will be a fair amount of new theory, but both in the project as well as at the oral exam, the main focus will be upon the ability to use the theory and methods on practical problems. The course is highly relevant for students who wish to write their master thesis within the area of applications of optimization and efficient algorithms on industrial problems.

Expected learning outcome


Subject overview
Linear programming on graphs: Resume of topics on linear programming and basic topics on graphs (minimum spanning trees, shortest paths etc), maximum flows and minimum cost flows in networks, weighted matching in graphs. Production planning. Integer programming: Resume of the Branch and Bound technique, Branch and Cut, Lagrange relaxation, column generation techniques. Examples of applications: Project planning, route planning, production planning, construction of networks with specified properties. Working with an optimization package such as ILOG CPLEX.

Literature

Meddeles ved kursets start.

Syllabus
See syllabus.

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Oral exam (30 minutes preparation) and evaluation of project report(s). Each count 50% of the total grade. External examination with marks according to the Danish 13-point marking scale. The projects are evaluated and graded by the teacher only, but the external examinator will have access to the reports during the examination. In order to reduce the work load, projects can be made in groups of up to three persons. At the oral exam there may be questions in the topics of the projects.

Expected working hours
The teaching method is based on three phase model.

Forelæsninger, øvelser og projektarbejde. Der vil være ca. 4 konfrontationstimer per uge. Herudover skal der påregnes en del tid til projektarbejdet.
Educational activities

Language
This course is taught in English, if international students participate. Otherwise the course is taught in Danish.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.