Jump to content

User:Bmears11/mysandbox/Integer Linear Programming/branch and cut

From Wikipedia, the free encyclopedia
< User:Bmears11 | mysandbox | Integer Linear Programming
This is an old revision of this page, as edited by Bmears11 (talk | contribs) at 17:39, 11 December 2012. The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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.

Branching Strategies

An important step in the branch and cut algorithm is the branching step. At this step, there are a variety of branching heuristics that can be used. The branching strategies described below are all involve what is called branching on a variable. Branching on a variable involves choosing a variable Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "http://localhost:6011/en.wikipedia.org/v1/":): {\displaystyle x_i</math with a fractional value, <math>x_i'} , in the optimal solution to the current LP relaxation and then adding the constraints and

  • Most Infeasible Branching This branching strategy chooses the variable with the fractional part closest to 0.5.
  • Pseudo Cost Branching The basic idea of this strategy is to keep track for each variable <math>x_i</math the change in the objective function when this variable was previously chosen as the variable to branch on. The strategy then chooses the variable that is predicted to have the most change on the objective function based on past changes when it was chosen as the branching variable. Note that pseudo cost branching is initially uninformative in the search since few variables have been branched on.
  • Strong Branching Strong branching involves testing which of the candidate variable gives the best improvement to the objective function before actually branching on them. Full strong branching tests all candidate variables and can be computationally expensive. The computational cost can be reduced by only considered a subset of the candidate variables and not solving each of the corresponding LP relaxations to completion.

There are also a large number of variations of these branching strategies, such as using strong branching early on when pseudo cost branchinis relatively uninformative and then switching to pseudo cost branching later when there is enough branching history for pseudo cost to be informative.

Retrieved from "https://en.wikipedia.org/w/index.php?title=User:Bmears11/mysandbox/Integer_Linear_Programming/branch_and_cut&oldid=527565705"