Notes pour le cours OPTIMISATION C-2-24-1 MPRI Vincent JOST

Last updated: 3 nov 2009 !

If you are interested in doing your master thesis in optimisation, contact me. Possible subjects for spring 2010 might be:

Things that you have to know perfectly for the exam

Receipe for dualizing LPs (1 page).pdf [4]
The bipartite matching polytope (4 pages).pdf [1]
The max-flow-min-cut Theorem and an algorithm (14 pages).pdf [1]
Definitions of Integer Linear Progam, Integer polyhedron, cutting planes: (26 pages).pdf [1]
Totally unimodular matrices yield integer optimum solutions
Network matrices are Totally unimodular (1 page).pdf [1]
The principle of Lagrangean relaxation / column generation approach

Things that you may read to have enough background for the course

What is a linear program and it's dual ? (do the exercices please...) (13 pages).pdf [4]
Polyhedral approach to the Travelling Salesman Problem (9 pages).pdf [1]
Some general cuts for mixed integer linear programs (9 pages).pdf [1]

Things that you could read for further knowledge

The above documents are copied from some authors below

I recommand these books and websites for your documentation

	[1]	Alexander Schrijver (2003) Combinatorial Optimization Polyhedra and Efficiency This is the reference book in polyhedral combinatorics.
	[2]	Bernhard Korte and Jens Vygen (2005 third Edition) Combinatorial Optimization Theory and Algorithms This is a great one volume book on the topic.
	[3]	Jiri Matousek and Bernd Gartner (2007) Understanding and using linear programming If you want to learn linear programming efficiently, read this gem.
	[4]	Thomas S. Ferguson www.math.ucla.edu/~tom/LP.pdf A nice freely downloadable 65 pages introduction to linear programming.