Méthode de l'ellipsoïde

En optimisation mathématique, la méthode de l'ellipsoïde est une méthode itérative utilisée pour minimiser des fonctions convexes. En informatique théorique, cette méthode est connue comme étant le premier algorithme de complexité polynomiale découvert pour résoudre les problèmes d'optimisation linéaire. L'algorithme construit une suite d'ellipsoïdes de plus en plus petits, qui enserrent à chaque étape le minimum de la fonction objectif. Histoire Depuis son invention par George Dantzig en 1947, la méthode du simplexe avait relégué un certain nombre d'heuristiques antérieures pour résoudre les problèmes d'affectation sous contraintes linéaires, en particulier les itérations transposant le problème à une compétition entre deux joueurs. Tout au long des années 1950 et 1960, elle fut appliquée à des problèmes de taille de plus en plus grande jusqu'à ce qu'au début des années 1970, Victor Klee et mettent en évidence l'existence de programmes pour lesquels l'algorithme de Dantz

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Publications associées (1)

Publications associées

Chargement

Personnes associées

Chargement

Unités associées

Chargement

Concepts associés (8)

Concepts associés

Chargement

Cours associés (1)

Cours associés

Chargement

Séances de cours associées (4)

Séances de cours associées

Chargement

Separating stable sets in claw-free graphs via Padberg-Rao and compact linear programs

Yuri Faenza, Gautier Stauffer

In this paper, we provide the first linear programming formulations for the stable set problem in claw-free graphs, together with polynomial time separation routines for those formulations (they are not compact). We then exploit one of those extended formulations and propose a new polytime algorithm for solving the separation problem for the stable set polytope of claw-free graphs. This routine combines a separation algorithm for the matching polytope due to Padberg and Rao and the solution of (moderate size) compact linear programs. Hence, it does not rely on the ellipsoid method and seems to be appropriate to be inserted in branch and cut frameworks for solving real world problems.

2012

Chargement

Optimisation linéaire

thumb|upright=0.5|Optimisation linéaire dans un espace à deux dimensions (x1, x2). La fonction-coût fc est représentée par les lignes de niveau bleues à gauche et par le plan bleu à droite. L'ensemble

Optimisation (mathématiques)

L'optimisation est une branche des mathématiques cherchant à modéliser, à analyser et à résoudre analytiquement ou numériquement les problèmes qui consistent à minimiser ou maximiser une fonction sur

Méthodes de points intérieurs

vignette|Visualisation de la méthode des points intérieur : le chemin reste à l’intérieur du polyèdre. vignette|Visualisation de la méthode du simplexe : le chemin suit les arêtes du polyèdre vignette

CS-450: Advanced algorithms

A first graduate course in algorithms, this course assumes minimal background, but moves rapidly. The objective is to learn the main techniques of algorithm analysis and design, while building a repertory of basic algorithmic solutions to problems in many domains.