# Optimisation and Approximation

## General information

**Lecture times:** Tuesday, 10.15-12.15am.

**Instructor:** Nicolas Bousquet.

**Teaching Assistant:** Johanna Seif and Dewi Sintiari.

**Email:** firstname.lastname@grenoble-inp.fr
## Pre-requisites

Students should know the basics from Calculus and Linear Algebra.

## Content

Lecture notes (which will be updated all along the term) will be provided after each lecture (hopefully shortly after the lecture !). Exercises sessions will also be added.
Note that all the exercises won't be treated during the lectures. The additional exercises are there to give you some material on which you can work on.
### Lectures

Lecture 1: Introduction to optimization.

Lecture 2: Introduction to polytopes.

Lecture 3: Simplex algorithm.

Lecture 4: Simplex algorithm - Initialization and Termination.
Lecture 5: Duality of LP.
Lecture 6: Sensitivity analysis.

### Exercises

TD1: Modelization and Linear Programming.

TD2: Polytopes and simplex algorithm.

TD3 & 4: Simplex algorithm.

## Textbooks

- Understanding and Using Linear Programming, by Jiri Matousek and Bernd Gartner (2006).
- Applied Mathematical Programming by Bradley, Hax, and Magnanti (Addison-Wesley, 1977).
- Linear Programming, Chvatal.
- Approximation algorithms, Vijay Vazirani (2001).
- The Design of Approximation Algorithms David P. Williamson and David B. Shmoys (2010).

If you want to solve your linear programs, you can go there where a solver using the Simplex algorithm is proposed.

**Acknowledgment**

This course is inspired of the courses of Bruce Shepherd and Yori Zwols given in McGill University (Mathematical Programming). Some lectures and exercises are also inspired from the ones given by Alantha Newman in 2016 for this course.

I would also like to thank my TD-men of 2017 Florent BrĂ©hard and Luc Pellissier for the help for the exercises sessions and for their careful reading of the lectures.

If you find any mistake or typo somewhere, fell free to send me an email to tell me ! It will help me to improve the quality of the future lectures...