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
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
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.
9. examen écrit
toutes notes autorisées. Pas de calculatrices ou livres, ni ordinateur ou tablette, même avec wifi desactivé.