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.
| Attributes | Values |
|---|
| rdf:type
| |
| rdfs:label
| - Branch-and-Cut (de)
- Branch and cut (en)
- Branch and cut (fr)
- 분기 절단법 (ko)
- 分支切割法 (zh)
|
| 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)
|
| dcterms:subject
| |
| Wikipage page ID
| |
| Wikipage revision ID
| |
| Link from a Wikipage to another Wikipage
| |
| Link from a Wikipage to an external page
| |
| sameAs
| |
| dbp:wikiPageUsesTemplate
| |
| has 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)
|
| gold:hypernym
| |
| prov:wasDerivedFrom
| |
| page length (characters) of wiki page
| |
| foaf:isPrimaryTopicOf
| |
| is Link from a Wikipage to another Wikipage
of | |
| is foaf:primaryTopic
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)