Branch and cut (original) (raw)
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 Schnittebenenverfahren und Branch-and-Bound.
| Property | Value |
|---|---|
| dbo:abstract | 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 Schnittebenenverfahren und Branch-and-Bound. (de) Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called branch and cut. (en) 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 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. (fr) 분기 절단법(分岐切斷法, 分岐絶斷法, Branch and cut)은 조합 최적화에서 정수 계획법을 푸는 방법 중 하나이다. 정수 계획법이란 선형 계획법에서 모든 미지수가 정수로 제한된 경우를 말한다. 이 방법은 분기 한정법과 을 합친 방법이다. (ko) 分支切割法是用于解决整数线性问题（ILPs），即部分或全部未知数为整数值的线性规划（LP）的问题的组合优化方法。该方法在的基础上，使用以收紧线性规划松弛。如果切割平面仅用来收紧初始的 LP 松弛，则改称为切割分支法。 (zh) |
| dbo:wikiPageExternalLink | https://software.cs.uni-koeln.de/abacus/ http://scip.zib.de https://github.com/coin-or/Cbc https://web.archive.org/web/20050901073653/http:/www.cs.sandia.gov/opt/survey/mip.html |
| dbo:wikiPageID | 3237914 (xsd:integer) |
| dbo:wikiPageLength | 9440 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1123396658 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Branch_and_bound dbr:Cutting-plane_method dbc:Combinatorial_optimization dbr:GitHub dbr:Combinatorial_optimization dbr:C++ dbc:Optimization_algorithms_and_methods dbr:Linear_programming dbr:Linear_programming_relaxation dbr:While_loop dbr:Integer dbr:Simplex_algorithm dbr:Pseudocode dbr:Integer_linear_program dbr:Feasible_solution dbr:Revised_simplex_algorithm dbr:Search_tree_pruning dbr:Cutting_plane |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Reflist dbt:Optimization_algorithms |
| dcterms:subject | dbc:Combinatorial_optimization dbc:Optimization_algorithms_and_methods |
| gold:hypernym | dbr:Method |
| rdf:type | dbo:Software |
| rdfs:comment | 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 Schnittebenenverfahren und Branch-and-Bound. (de) Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called branch and cut. (en) 분기 절단법(分岐切斷法, 分岐絶斷法, Branch and cut)은 조합 최적화에서 정수 계획법을 푸는 방법 중 하나이다. 정수 계획법이란 선형 계획법에서 모든 미지수가 정수로 제한된 경우를 말한다. 이 방법은 분기 한정법과 을 합친 방법이다. (ko) 分支切割法是用于解决整数线性问题（ILPs），即部分或全部未知数为整数值的线性规划（LP）的问题的组合优化方法。该方法在的基础上，使用以收紧线性规划松弛。如果切割平面仅用来收紧初始的 LP 松弛，则改称为切割分支法。 (zh) 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. (fr) |
| rdfs:label | Branch-and-Cut (de) Branch and cut (en) Branch and cut (fr) 분기 절단법 (ko) 分支切割法 (zh) |
| owl:sameAs | freebase:Branch and cut wikidata:Branch and cut dbpedia-de:Branch and cut dbpedia-fa:Branch and cut dbpedia-fr:Branch and cut dbpedia-ko:Branch and cut dbpedia-zh:Branch and cut https://global.dbpedia.org/id/4cxSG |
| prov:wasDerivedFrom | wikipedia-en:Branch_and_cut?oldid=1123396658&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Branch_and_cut |
| is dbo:wikiPageWikiLink of | dbr:Protein_design dbr:List_of_algorithms dbr:M._Grazia_Speranza dbr:Branch_and_bound dbr:Arc_routing dbr:Cutting-plane_method dbr:Integer_programming dbr:Kuratowski's_theorem dbr:Computational_science dbr:Branch_and_price dbr:Combinatorial_optimization dbr:Zuse_Institute_Berlin dbr:COIN-OR dbr:Travelling_salesman_problem dbr:Václav_Chvátal dbr:Linear_programming dbr:Linear_programming_relaxation dbr:Planarization |
| is foaf:primaryTopic of | wikipedia-en:Branch_and_cut |