Aller au menu Aller au contenu
Une voie, plusieurs choix
Informatique et Mathématiques appliquées
Une voie, plusieurs choix

> Formation > Cursus ingénieur

Combinatorial optimization - 4MMOC6

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In
  • Number of hours

    • Lectures : 16.5
    • Tutorials : 16.5
    • Laboratory works : -
    • Projects : -
    • Internship : -
    • Written tests : -
    ECTS : 3.0
  • Officials : Zoltan SZIGETI

Goals

In the first year operations research course we studied some optimization algorithms on graphs, namely the shortest path problem in some particular cases and the minimum spanning tree problem. In this course we will go ahead and see more such algorithms: maximum flow problem, min cost flow problems, maximum cardinality or weight matching problem, and shortest path problems in the general case. We will also see many nice min-max or max-min theorems. This course put an emphasis in modelling and in algorithmics.

Content

1. Maximum flow in a network : Ford and Fulkerson algorithm, preflow algorithms
2. Min cost flow problem : flow simplex algorithm, primal dual algorithm.
3. Shortest path problems general algorithm and finding of negative length cycles..
4. Maximum matching algorithm. The Edmonds-Gallai theorem.
5. Modeling real world problems as flow problems.
6. Some min-max theorems arising from network flow problems

Prerequisites

Linear programming (useful), elementary graph theory, seen in first year operations research course.

Tests

Written exam (3 h) (E)

N1=E1
N2=E2

Calendar

The course exists in the following branches:

  • Curriculum - Math. Modelling, Image & Simulation - Semester 7
see the course schedule for 2020-2021

Additional Information

Course ID : 4MMOC6
Course language(s): FR

The course is attached to the following structures:

You can find this course among all other courses.

Bibliography

Linear programming by Vacek Chvatal, (editeur Freeman)
Network flows by Ahuja, Magnati and Orlin (editeur Prentice Hall)

A+Augmenter la taille du texteA-Réduire la taille du texteImprimer le documentEnvoyer cette page par mail cet article Facebook Twitter Linked In

Date of update January 15, 2017

Université Grenoble Alpes