DM817: Network Programming: Theory and Applications (10 ECTS)

STADS: 15005701

Level
Master's level course

Teaching period
The course is offered in the autumn semester.
To be announced.

Teacher responsible
Email: jbj@imada.sdu.dk

Additional teachers
maddaloni@imada.sdu.dk

Timetable
Show entire timetable
Show personal time table for this course.

Comment:
Ubegrænset deltagerantal. 3. + 4. kvartal.

Prerequisites:
None

Academic preconditions:
Knowledge about algorithms, data structures and complexity corresponding to e.g. DM507 and DM508.

Course introduction
To introduce the theory of flows in networks and generalizations of flows as well as applications of this theory to an array of important problems. This includes methods for solving flow problems, modeling and solution of problems (including graph problems, scheduling problems etc.) as flow problems, applications to practical optimization problems as well as generalizations of flows in networks such as submodular flows. Network flows is probably the most relevant graphtheoretic topic for practical applications. A large number of practical problems can be formulated and solved effeciently as a flow problem. It is an explicit goal of the course to enable the students to use this powerful tool both in theory and in practice.

Expected learning outcome
At the end of the course the student is able to

• make a generalized flow formulation from a given problem description in words.
• give an account for algorithms from the course in which flow algorithms form a component of the algorithm. This includes problems such as augmenting the edge-connectivity of a graph, matching in bipartite graphs, scheduling algorithms etc.
• apply the theory from the course to practical optimization problems such as flow problems, transportation problems, , matching problems, simple scheduling problems, orientation problems etc.
• give an account for the algorithms treated in the course and apply these to problems resempling those treated in the course.

Subject overview
Shortest paths (min cost) flows, project planning, scheduling, linear and integer programming, lagrange-relaxation, convex cost flows, submodular flows, graph connectivity, matching in graphs, Steiner trees in graphs, primal-dual algorithms.

Literature

• Meddeles ved kursets start..

Website
This course uses e-learn (blackboard).

Prerequisites for participating in the exam
None

Assessment and marking:
Project assignment, Danish 7 mark scale, External examiner.

The re-exam may differ from the ordinary exam.

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

Forelæsninger 40, Eksaminatorier 26
Educational activities

Language
This course is taught in Danish or English, depending on the lecturer. However, if international students participate, the teaching language will always be English.

Course enrollment
See deadline of enrolment.

Tuition fees for single courses
See fees for single courses.