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

STADS: 15005701

Level
Master's level course

Teaching period


Teacher responsible
Email: jbj@imada.sdu.dk

Timetable
There is no timetable available for the chosen semester.

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 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 multicomodity 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
• make a 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, travelling salesman problems, matching problems, simple scheduling problems etc. • give an account for the algorithms treated in the course and apply these to problems resempling those treated in the course. • apply a computer software for solving flow problems and generalizations of flow problems.

Subject overview
Shortest paths (min cost) flows, project planning, scheduling, linear and integer programming, lagrange-relaxation, multicommodity flows, graph connectivity, matching in graphs, Steiner trees in graphs, primal-dual algorithms. The students will also get acquainted with a software package for solving linear and integer programming problems.

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

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 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.