Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Optimisation combinatoire programmation lineaire et algorithmes

Université Pierre et Marie Curie Optimisation Combinatoire Programmation Linéaire et Algorithmes Pierre Fouilhoux pierre fouilhoux lip fr septembre Avant-propos Table des matières I Modéliser Programmation mathématique Dé nitions Di culté de la PMD Programme linéaire Programme non-linéaire Un puissant outil de modélisation Convexi cation et linéarisation Convexi cation Linéarisation Modélisation par un PLNE Optimisation Combinatoire et modélisations Problèmes d'Optimisation Combinatoire Notations de théorie des graphes Problèmes classiques en optimisation combinatoire Le problème du sac-à-dos Recouvrement pavage et partition Le problème du stable Le problème du voyageur de commerce Le problème de coloration Le problème du ot max Le problème du couplage biparti Exercices Modélisation de petits problèmes Problème de production tiré d'un livre de ereS Problème de transport Combinaison optimale en vitamines Diet Problem TABLE DES MATIÈRES Constitution d'un portefeuille optimal Centres de loisir Diététique avare Problème d'a n ectation quadratique Exercices Linéarisation de la di n érence entre variables Linéarisation d'un quotient Décision en production industrielle Un peu plus dur Verre de spin et Max-Cut II Résoudre Résolution approchée ou exacte Enumération L'explosion combinatoire Cas polynomiaux Solutions approchées et garantie Trouver des solutions réalisables Solution à garantie théorique Solution approchée avec garantie expérimentale Résolution exacte Algorithme de Branchement-Evaluation Illustration par le problème du voyageur de commerce Dé nitions et algorithme de Branch Sous-problèmes évaluation et stérilité E cacité d'un algorithme de branchement Schéma de l'algorithme Programmation dynamique et dominance Branchement pour les PMD et pré-traitement Exercices Représentation graphique Arborescence à compléter Sac-à-dos binaire Evaluation par relaxation Relaxation continue Relaxation lagrangienne TABLE DES MATIÈRES Dé nitions et résultats généraux Dualité lagrangienne Saut de dualité La relaxation lagrangienne Application au problème du voyageur de commerce Points extrêmes et cas polynomiaux Polyèdre et points extrêmes Points extrêmes et polyèdres entiers Totale unimodularité et cas polynomial Totale duale intégralité et min-max Exercices Points fractionnaires du problème du sac-à-dos Un petit exemple non TDI La dualité Flot Max Coupe Min Algorithmes de coupes Coupes et séparation Equivalence Séparation et Optimisation Exemples de séparation de contraintes Contraintes de coupes pour le TSP Contraintes de clique pour le stable Contraintes de cycles impairs pour le stable Algorithmes de coupes et branchements Exercices Séparation des inégalités de cycles pour Max-Cut Inégalités valides et renforcement Contraintes valides et renforcement Somme de Chvàtal exemple du problème du stable max Méthode de Chvátal-Gomory et Lovász-Schrivjer Autres méthodes Reformulation et génération de colonnes Comment obtenir une bonne reformulation Un exemple de reformulation le problème de découpes Première formulation Seconde formulation contenant un nombre exponentiel de variables Algorithme de génération de colonnes Algorithme de génération de colonnes et branchement TABLE DES MATIÈRES Exercices Exercice le problème de multi ot continu Décomposition Introduction Décomposition de Dantzig-Wolfe Formulation de base Réécriture et relaxation de SP Décomposition de Dantzig-Wolfe et génération de colonnes Relaxation Lagrangienne Décomposition de Dantzig-Wolfe appliquée à la coloration Formulation de base Réécriture et relaxation de SP Décomposition de Dantzig-Wolfe et génération de colonnes Relaxation Lagrangienne III Approches Polyédrales pour l'Optimisation Combinatoire Dé nitions et résultats fondamentaux IR Présentation de l'approche polyèdrale