Bachelor course

The course is offered in the spring semester.

Marco Chiarandini, Lektor,

Tlf.: 6550 4031 Email: marco@imada.sdu.dk

Group | Type | Day | Time | Classroom | Weeks | Comment |
---|---|---|---|---|---|---|

Common | I | Monday | 10-12 | U91 | 8,10 | |

Common | I | Monday | 10-12 | U20 | 11 | |

Common | I | Monday | 08-10 | U55 | 12 | |

Common | I | Monday | 10-12 | U140 | 17,19 | |

Common | I | Wednesday | 14-16 | U166 | 7 | |

Common | I | Wednesday | 14-16 | U55 | 14 | |

Common | I | Wednesday | 10-12 | U23 | 15-20 | |

Common | I | Wednesday | 14-16 | U23 | 22 | DM559 |

Common | I | Thursday | 10-12 | U23 | 5,8-12,14-16,18,20 | |

Common | I | Thursday | 08-10 | U23 | 6-7 | |

Common | I | Thursday | 14-16 | U140 | 21 | |

Common | I | Friday | 10-12 | U173 | 5 | |

Common | I | Friday | 10-12 | U43 | 6 | |

H1 | TE | Monday | 08-10 | U143 | 7-11,16 | |

H1 | TE | Wednesday | 14-16 | U154 | 18-21 | |

H1 | TE | Thursday | 08-10 | U23 | 12 | TH1H2 DM559 |

H1 | TL | Friday | 10-12 | IMADA ComputerLab | 14,16 | |

H1 | TE | Friday | 08-10 | U143 | 14 | |

H1 | TE | Friday | 10-12 | U143 | 21 | |

H2 | TE | Tuesday | 14-16 | U141 | 21 | |

H2 | TL | Wednesday | 16-18 | IMADA ComputerLab | 14 | |

H2 | TL | Wednesday | 14-16 | IMADA ComputerLab | 16 | |

H2 | TE | Thursday | 12-14 | U31 | 7 | |

H2 | TE | Thursday | 12-14 | U17 | 8,10 | |

H2 | TE | Thursday | 12-14 | U154 | 9 | |

H2 | TE | Thursday | 12-14 | U64 | 11 | |

H2 | TE | Thursday | 14-16 | U154 | 14 | |

H2 | TE | Thursday | 12-14 | U143 | 16,18,20 | |

H2 | TE | Friday | 10-12 | U144 | 19 | |

H2 | TE | Friday | 12-14 | U145 | 21 | |

M1 | TE | Tuesday | 12-14 | U64 | 12,15,17-21 | |

M1 | TE | Wednesday | 10-12 | U8 | 21 | |

M1 | TL | Friday | 08-10 | IMADA ComputerLab | 14,16 |

Show personal time table for this course.

Ubegrænset deltagerantal. Fælles undervisning med DM545, Lineær- og heltalsprogrammering fra uge 12.

None

Students taking the course are expected to:

- Have knowledge of the content of the course: DM507, "Algorithms and Data Structures"
- Be able to program

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 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 work first with the elements of linear algebra that are relevant for computer science and especially for linear and integer programming, then with the basics of linear programming and duality theory, and finally, with the main solution techniques, such as the simplex method, branch and bound and cutting planes. Besides giving skills in mathematical modeling, the course has also the goal of giving to the students experience with practical applications and with a mathematical software system for finding numerical solutions to the applications proposed.

The course builds on the knowledge acquired in the course DM507, "Algorithms and Data Structures" and gives an academic basis for doing a bachelor thesis project and other theoretical or practical oriented study-activities as well as for studying elective courses with elements of optimization that can be chosen as part of the degree.

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 computer science problems with the application of methods and modeling formalisms from the core areas of computer science and its mathematical support disciplines
- Give skills to take and justify computer science decisions
- 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 the computer science field

The learning objective of the course is that the student demonstrates the ability to:

- make calculations in matrix algebra.
- solve systems of linear equations both manually and with the computer.
- apply linear algebra to solve practical problems that resemble those treated in the course.
- 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.

The following main topics are contained in the course:

- Matrix algebra
- Systems of linear equations and Gauss elimination
- Rank of matrices, matrix inversion
- Vector spaces, linear transformations
- 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

- Meddeles ved kursets start.

This course uses e-learn (blackboard).

- Mandatory assignments. Is evaluated internal on a pass/fail basis by the teacher.

- 4 hours written exam. Evaluated by external censorship by the Danish 7-mark scale.

The teaching method is based on three phase model.

Intro phase: 46 hours

Skills training phase: 50 hours, hereof:

- Tutorials: 42 hours

- Laboratory exercises: 8 hours

- Reading from text books
- Solving homeworks
- Applying acquired knowledge to practical projects

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.

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

The course is co-read with: DM545 in the second half of the semester.

See deadline of enrolment.

See fees for single courses.