Sök i kursutbudet

Använda sökfunktionen för att hitta i Chalmers utbildningsutbud, både vad gäller kurser och program. När det finns en kurshemsida visas en hus-symbol som leder till denna sida. Tänk på att välja det läsår du vill se information om.
Sök program och utbildningsplaner


Institutionernas kurser för doktorander

​​​​​​​​​​​​​​​​​​​​

Kursplan för

Läsår
TDA206 - Discrete optimization
 
Kursplanen fastställd 2009-02-24 av programansvarig (eller motsvarande)
Ägare: MPALG
7,5 Poäng
Betygskala: TH - Fem, Fyra, Tre, Underkänt
Utbildningsnivå: Avancerad nivå
Huvudområde: Datateknik, Informationsteknik
Institution: 37 - DATA- OCH INFORMATIONSTEKNIK


Undervisningsspråk: Engelska

Modul   Poängfördelning   Tentamensdatum
Lp1 Lp2 Lp3 Lp4 Sommarkurs
0101 Tentamen 7,5 hp Betygskala: TH   7,5 hp   Kontakta examinator

I program

MPSYS SYSTEMS, CONTROL AND MECHATRONICS, MSC PROGR, Årskurs 1 
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Årskurs 2 
MPALG COMPUTER SCIENCE - ALGORITHMS, LANGUAGES AND LOGIC, MSC PROGR, Årskurs 1 
TKITE INFORMATIONSTEKNIK, CIVILINGENJÖR, Årskurs 3 (valbar)

Examinator:

Professor  Devdatt Dubhashi
Bitr professor  Peter Damaschke


Kursutvärdering:

http://document.chalmers.se/doc/1132311269


  Gå till kurshemsida

Behörighet:

För kurser inom Chalmers utbildningsprogram gäller samma behörighetskrav som till de(t) program kursen ingår i.

Kursspecifika förkunskaper

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

Syfte

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.

Lärandemål (efter fullgjord kurs ska studenten kunna)

- 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

Innehåll

* 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.

Litteratur

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.


Sidansvarig Publicerad: må 13 jul 2020.