Course syllabus adopted 2021-02-26 by Head of Programme (or corresponding).
Overview
- Swedish nameDiskret optimering
- CodeTDA206
- Credits7.5 Credits
- OwnerMPALG
- Education cycleSecond-cycle
- Main field of studyComputer Science and Engineering, Software Engineering
- DepartmentCOMPUTER SCIENCE AND ENGINEERING
- GradingTH - Pass with distinction (5), Pass with credit (4), Pass (3), Fail
Course round 1
- Teaching language English
- Application code 02130
- Maximum participants60 (at least 10% of the seats are reserved for exchange students)
- Block schedule
- Open for exchange studentsYes
Credit distribution
Module | Sp1 | Sp2 | Sp3 | Sp4 | Summer | Not Sp | Examination dates |
|---|---|---|---|---|---|---|---|
| 0101 Examination 7.5 c Grading: TH | 7.5 c |
|
In programmes
- MPALG - COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory elective)
- MPCAS - COMPLEX ADAPTIVE SYSTEMS, MSC PROGR, Year 1 (elective)
- MPCSN - COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)
- MPSYS - SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Year 1 (compulsory elective)
Examiner
Devdatt Dubhashi- Full Professor, Data Science and AI, Computer Science and Engineering
Eligibility
General entry requirements for Master's level (second cycle)Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.
Specific entry requirements
English 6 (or by other approved means with the equivalent proficiency level)Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling the requirements above.
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 and their geometric properties, duality in optimization, branch-and-bound and other heuristics, some special graph algorithmsOrganisation
Lectures and homework assignments.Literature
See separate literature list.Examination including compulsory elements
Written exam.The course examiner may assess individual students in other ways than what is stated above if there are special reasons for doing so, for example if a student has a decision from Chalmers on educational support due to disability.