Branch and cut
- Branch and cut
-
Branch and cut est une méthode d'optimisation combinatoire pour résoudre des problèmes d'optimisation linéaire en nombres entiers. Cette méthode utilise la méthode de séparation et évaluation et la méthode des plans sécants.
Le principe[1] est de résoudre la relaxation continue du programme linéaire en nombres entiers à l'aide de l'algorithme du simplexe. Lorsqu'une solution optimale est trouvée, et que l'une des variables qu'on souhaite entières a une valeur non entière, on utilise un algorithme de plan sécant pour trouver une contrainte linéaire satisfaite par toutes les valeurs entières de la solution mais violée par la valeur fractionnaire. Si une telle contrainte est trouvée, alors elle est ajoutée au programme linéaire de sorte que la résolution de ce programme donne une solution avec moins de valeurs non entières. On répéte ce procédé jusqu'à ce qu'une solution entière soit trouvée (qui est alors optimale) ou jusqu'à ce qu'aucun plan sécant ne puisse être trouvé.
À ce moment, la partie séparation et évaluation de l'algorithme commence. Le problème est scindé en deux sous-problèmes, l'un en rajoutant la contrainte que la variable est supérieure ou égale à la partie entière par excès de la solution intermédiaire, et l'autre en rajoutant la contrainte que la variable est inférieure ou égale à sa partie entière usuelle (par défaut). Ces deux nouveaux programmes linéaires sont résolus avec l'algorithme du simplexe et on itère la procédure présentée précédemment.
Voir aussi
Références
- ↑ George Nemhauser und Laurence Wolsey: Integer and Combinatorial Optimization. Wiley Interscience, 1988, ISBN 0-471-35943-2.
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Branch and cut de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Branch and Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… … Deutsch Wikipedia
Branch-and-Cut — bzw. Verzweigung und Schnitt bezeichnet in der kombinatorischen Optimierung, einem Teilgebiet der diskreten Mathematik, ein Verfahren zur Lösung ganzzahliger linearer Optimierungsprobleme. Das Verfahren besteht aus der Kombination von… … Deutsch Wikipedia
Branch and cut — (sometimes written as branch and cut ) is a method of combinatorial optimization for solving integer linear programs, that is, linear programming problems where some or all the unknowns are restricted to integer values. The method is a hybrid of… … Wikipedia
Branch and Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen … Deutsch Wikipedia
Branch and bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen … Deutsch Wikipedia
Branch-and-Bound — (Verzweigung und Schranke) ist eine im Bereich Operations Research häufig verwendete mathematische Methode, deren Ziel darin besteht, für ein gegebenes ganzzahliges Optimierungsproblem eine beste Lösung zu finden. Branch and Bound führt auf einen … Deutsch Wikipedia
Branch and price — est une méthode d optimisation combinatoire pour résoudre des problèmes d optimisation linéaire en nombres entiers. Cette méthode combine l algorithme du branch and bound classique avec une génération de colonnes à chaque nœud de l arbre.… … Wikipédia en Français
Cut Bank, Montana — See also: Cut Bank Creek and Cut bank Cut Bank, Montana City La … Wikipedia
cut — {{Roman}}I.{{/Roman}} noun 1 hole/opening made by cutting ADJECTIVE ▪ clean, neat ▪ little, small ▪ long ▪ straight … Collocations dictionary
cut off — I verb 1. make a break in (Freq. 8) We interrupt the program for the following messages • Syn: ↑interrupt, ↑disrupt, ↑break up • Derivationally related forms: ↑disruption … Useful english dictionary
