Search course

Use the search function to find more information about the study programmes and courses available at Chalmers. When there is a course homepage, a house symbol is shown that leads to this page.

Graduate courses

Departments' graduate courses for PhD-students.

​​​​
​​

Syllabus for

Academic year
TDA206 - Discrete optimization
 
Syllabus adopted 2014-02-25 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

The course is full
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,5c Grading: TH   7,5c   Contact examiner

In programs

TKITE SOFTWARE ENGINEERING, Year 3 (elective)
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 1 (compulsory elective)
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 2 (elective)
MPCAS COMPLEX ADAPTIVE SYSTEMS, MSC PROGR, Year 2 (elective)
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Year 1 (compulsory elective)
MPCSN COMPUTER SYSTEMS AND NETWORKS, MSC PROGR, Year 1 (elective)

Examiner:

Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



  Go to Course Homepage

Eligibility:


In order to be eligible for a second cycle course the applicant needs to fulfil the general and specific entry requirements of the programme that owns the course. (If the second cycle course is owned by a first cycle programme, second cycle entry requirements apply.)
Exemption from the eligibility requirement: Applicants enrolled in a programme at Chalmers where the course is included in the study programme are exempted from fulfilling these requirements.

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 
algorithms

Organisation

Lectures and homework assignments.

Literature

See separate literature list.

Examination

Assignments and home exam.


Page manager Published: Thu 04 Feb 2021.