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 2008-02-21 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

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 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 
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Year 2 
MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR - Automation specialization, Year 1 (elective)

Examiner:

Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke



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

A basic course in Optimization or Operational Research. A basic course in Algorithms is recommended.

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 fields (industrial production, infrastructure, planning and scheduling, economics, data mining, bioinformatics, computer and network design, etc., and even in artificial intelligence)
- 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 (linear, integer, mixed, nonlinear programming, polynomial or NP-hard, approximable or not), find and how to use more information about problem classes and complexity
- apply linear programming and the theory of network flows to suitable applications, understand these topics both formally and geometrically
- distinguish approximation algorithms from heuristics, apply several heuristic approaches (e.g., branch-and-bound) as well as design techniques for approximation algorithms, to concrete problems
- dualize optimization problems (LP dual, Lagrange dual) and use the dual forms, e.g., to obtain bounds
- apply techniques for the design of exact algorithms (dynamic programming, cutting planes, column generation, parameterized algorithms) to concrete problems
- find more information about available software tools (modelling languages, solvers) and use them

Content

* Modelling. Problem classification (linear, integer, mixed-integer and nonlinear programming). Examples and applications.
* Complexity. Decision problems and complexity classes. Basic transformation techniques. Optimization problems.
* Network Flow. Augmenting paths and the Max-Flow Min-Cut Theorem. Ford-Fulkerson algorithm and Preflow-Push algorithms. Min-cost flow.
* Primal Heuristics. TSP: construction and impro-vement methods. Local search: simulated annea-ling, genetic algorithms, tabu search etc. Approximation schemes and performance guarantees.
* Dual Methods. Lagrange multipliers and Lagrange relaxation. Subgradient optimization.
* Optimal Methods. Branch & bound, dynamic programming. Polyhedral combinatoric. Cutting plane methods. Branch & cut. Column generation approaches.
Theoretical and practical assignments. See the course home page for the most up to date information.

Organisation

Lectures and homework assignments.

Literature

Cook, Cunningham, Pulleyblank, Schrijver. Combinatorial Optimization, John Wiley, New York, 1998.

Examination

Passed assignments. Written or oral exam. Grading scale F, 3, 4 or 5.


Page manager Published: Thu 04 Feb 2021.