Syllabus for |
|
| TDA206 - Discrete optimization |
| |
| Syllabus adopted 2013-02-09 by Head of Programme (or corresponding) |
| Owner: MPALG |
|
|
7,5 Credits |
| Grading: TH - Five, Four, Three, Not passed |
| Education cycle: Second-cycle |
|
Major subject: Computer Science and Engineering, Information Technology
|
|
Department: 37 - COMPUTER SCIENCE AND ENGINEERING
|
Teaching language: English
Open for exchange students
Block schedule:
A
| Course module |
|
Credit distribution |
|
Examination dates |
|
Sp1 |
Sp2 |
Sp3 |
Sp4 |
Summer course |
No Sp |
| 0101 |
Examination |
7,5 c |
Grading: TH |
|
|
|
7,5 c
|
|
|
|
|
Contact examiner |
In programs
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)
TKITE SOFTWARE ENGINEERING, Year 3 (elective)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Year 1 (compulsory elective)
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 2 (elective)
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory elective)
Examiner:
Professor
Devdatt Dubhashi
Bitr professor
Peter Damaschke
Course evaluation:
http://document.chalmers.se/doc/b3fc18d1-2fb4-4df9-a2b8-6d3680908bbd
Go to Course Homepage
Eligibility:
For single subject courses within Chalmers programmes the same eligibility requirements apply, as to the programme(s) that the course is part of.
Course specific prerequisites
Mathematics (including Discrete mathematics and Linear algebra), Programming, Algorithms and/or data structures.
Aim
The topic of the course is the theory and practice of optimization problems over discrete structures, and has strong connections to Optimization Theory (linear programming), Computer Science (algorithms and complexity), and Operational Research. Problems of this kind arise in many different contexts including transportation, telecommunications, industrial planning, finance, bioinformatics, hardware design and cryptology.
A characteristic property of these problems are that they are difficult to solve. The course intends to develop the skill of modelling real problems and to use mathematical and algorithmic tools to solve them, optimally or heuristically.
Learning outcomes (after completion of the course the student should be able to)
- identify optimization problems in various application domains,
- formulate them in exact mathematical models that capture the essentials
of the real problems but are still manageable by computational methods,
- assess which problem class a given problem belongs to,
- apply linear programming, related generic methods, and additional
heuristics, to computational problems,
- explain the geometry of linear programming,
- dualize optimization problems and use the dual forms to obtain bounds,
- work with the scientific literature in the field.
Content
modelling, linear programs and integer linear programs, polytopes, duality in
optimization, branch-and-bound and other heuristics, some special graph
algorithms
Organisation
Lectures and homework assignments.
Literature
See separate literature list.
Examination
Assignments and home exam. Grading scale U, 3, 4 or 5.