Branch and cut

Branch and cut

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 branch and bound and cutting plane methods.

The method solves the linear program without the integer constraint using the regular simplex algorithm. When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a cutting plane algorithm is used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution. If such an inequality is found, it is added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional". This process is repeated until either an integer solution is found (which is then known to be optimal) or until no more cutting planes are found.

At this point, the branch and bound part of the algorithm is started. The problem is split into two versions, one with the additional constraint that the variable is greater than or equal to the next integer greater than the intermediate result, and one where this variable is less than or equal to the next lesser integer. In this way new variables are introduced in the basis according to the number of basic variables that are non-integers in the intermediate solution but which are integers according to the original constraints. The new linear programs are then solved using the simplex method and the process repeats until a solution satisfying all the integer constraints is found. During the branch and bound process, further cutting planes can be separated, which may be either "global cuts", i.e., valid for all feasible integer solutions, or "local cuts", meaning that they are satisfied by all solutions fulfilling the side constraints from the currently considered branch and bound subtree.

External links

* [http://www.cs.sandia.gov/opt/survey/mip.html Mixed Integer Programming]
* [http://branchandcut.org/faq.htm BranchAndCut.org FAQ]
* [http://www.informatik.uni-koeln.de/abacus/ ABACUS - A Branch-And-CUt System] - open source software
* [https://projects.coin-or.org/Cbc/ COIN-OR Cbc] - open source software


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • 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 — 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… …   Wikipédia en Français

  • 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

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”