My Site
  • Home
  • Curriculum
  • Timetable
  • Opportunities
  • Application
  • About
  • Contact
This information is indicative and can be subject to change. 
​

Advanced combinatorial optimization

Teacher:  Alexandre Skoda

E-mail:  askoda@univ-paris1.fr
ECTS: 2.5
Evaluation:   written exam
Previsional Place and time:  9  sessions (2h per session)

Prerequisites:  basic concepts in Graph theory (Path, trees, greedy algorithm), and in Linear programming (simplex method).
Aim of the course: Solving practical optimization problems often requires finding integer valued solutions. In the first part, we present modelizations requiring the introduction of integer variables. In particular, we will solve a problem on networks using a linear programming approach. In a second part we will review three general types of methods used to solve integer programs. Finally, we will end with an introduction to the analysis of algorithms.
 Syllabus: 
  1. Introduction to integer linear programs
  2. Methods
    1. Branch and bound methods.
    2.  Dynamic programming.
    3.  Cutting plane methods.
  3. Computational complexity:
    1.  P, NP classes.
    2. Cook's Theorem.
    3. Examples of NP-complete problems.
 
References:
  •  V. Chvatal, Linear Programming, Freeman, 1983.
  • M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-completeness, Freeman, 1979.
  •  A. Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985.
Powered by Create your own unique website with customizable templates.
  • Home
  • Curriculum
  • Timetable
  • Opportunities
  • Application
  • About
  • Contact