Plan du cours

Les cours 1 à 4 seront assurés par Christoph Dürr et les cours 5 à 8 par Spyros Angelopoulos.

1. Problèmes de satisfaction de contraintes.

Vocabulaire : variables, domaine discret fini, contraintes. Exemples : Sudoku, deux modélisations des mots croisés, n reines. Résolution par retour sur trace : choix variable, choix valeur. vérification en avant.

Expériences avec problème des n reines

2. arc-consistance.

Différentes modélisations : Eternity.

devoir maison 1

Haiku corrigé

3. Programmation linéaire

Définitions. Introduction à AMPL. Installation et premiers pas. Problèmes classiques de flot, coupes, transports, couplage, plus courts chemins.

Trouver une 3-coloration du graphe de Petersen, n reines.

4. Dualité

dualité, conditions complementary slackness. Transformations entre différentes formes de programme linéaire. Modélisation plus court chemin à une source et toutes destinations, problème dual. Techniques de modélisation.

devoir maison2

Voyage voyage corrigé

5. Programmation linéaire à variables entières

Le lemme du rang. Mes sources.

6. Approximations basé sur la programmation linéaire

Couplage, vertex cover, set cover. Mes sources: 1, 2

7. Online algorithms et Programmation Linéaire

The Ski rental problem. Pure and mixed strategies using LPs.

8. Optimization of submodular functions, ski rental with advice.

Nos sources: 1, 2.

9. examen écrit

toutes notes autorisées. Pas de calculatrices ou livres, ni ordinateur ou tablette, même avec wifi desactivé.