Search programme

​Use the search function to search amongst programmes at Chalmers. The study programme and the study programme syllabus relating to your studies are generally from the academic year you began your studies.

Syllabus for

Academic year
TDA206 - Discrete optimization
 
Owner: TM
5,0 Credits (ECTS 7,5)
Grading: TH - Five, Four, Three, Not passed
Level: C
Department: 37 - COMPUTER SCIENCE AND ENGINEERING


Teaching language: English

Course module   Credit distribution   Examination dates
Sp1 Sp2 Sp3 Sp4 No Sp
0101 Examination 5,0 c Grading: TH   5,0 c   Contact examiner,    Contact examiner  

In programs

EMMAS MSc PROGR IN ENGINEERING MATHEMATICS, Year 1 (elective)
TTFYA ENGINEERING PHYSICS, Year 4 (elective)
TM Teknisk matematik, Year 2 (elective)
TITEA SOFTWARE ENGINEERING, Year 3 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING - Algorithms, Year 4 (elective)
TDATA COMPUTER SCIENCE AND ENGINEERING, Year 3 (elective)

Examiner:

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 (algo-rithms and comlexity), and Operational Research. Problems of this kind arise in many different con-texts including transportation, telecommunications, industrial planning, finance, bioinformatics, hard-ware 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.

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.

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: Mon 28 Nov 2016.