Branch and cut

Branch and cut[1] 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.[2] 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 cut and branch.

## Contents

* 1 Algorithm
* 1.1 Pseudocode
* 2 Branching strategies
* 3 References
* 4 External links

## Algorithm

This description assumes the ILP is a maximization problem.

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 may be used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution. These inequalities may be added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional".

At this point, the branch and bound part of the algorithm is started. The problem is split into multiple (usually two) versions. The new linear programs are then solved using the simplex method and the process repeats. During the branch and bound process, non-integral solutions to LP relaxations serve as upper bounds and integral solutions serve as lower bounds. A node can be pruned if an upper bound is lower than an existing lower bound. Further, when solving the LP relaxations, additional cutting planes may be generated, 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.

The algorithm is summarized below.

1. Add the initial ILP to [math]\displaystyle{ L }[/math], the list of active problems
2. Set [math]\displaystyle{ x^* = \text{null} }[/math] and [math]\displaystyle{ v^* = -\infty }[/math]
3. while [math]\displaystyle{ L }[/math] is not empty
1. Select and remove (de-queue) a problem from [math]\displaystyle{ L }[/math]
2. Solve the LP relaxation of the problem.
3. If the solution is infeasible, go back to 3 (while). Otherwise denote the solution by [math]\displaystyle{ x }[/math] with objective value [math]\displaystyle{ v }[/math].
4. If [math]\displaystyle{ v\le v^* }[/math], go back to 3.
5. If [math]\displaystyle{ x }[/math] is integer, set [math]\displaystyle{ v^*\leftarrow v, x^* \leftarrow x }[/math] and go back to 3.
6. If desired, search for cutting planes that are violated by [math]\displaystyle{ x }[/math]. If any are found, add them to the LP relaxation and return to 3.2.
7. Branch to partition the problem into new problems with restricted feasible regions. Add these problem to [math]\displaystyle{ L }[/math] and go back to 3
4. return [math]\displaystyle{ x^* }[/math]

### Pseudocode

In C++-like pseudocode, this could be written:

// ILP branch and cut solution pseudocode, assuming objective is to be maximized
ILP_solution branch_and_cut_ILP(IntegerLinearProgram initial_problem) {
queue active_list; // L, above
active_list.enqueue(initial_problem); // step 1
// step 2
ILP_solution optimal_solution; // this will hold x* above
double best_objective = -std::numeric_limits<double>::infinity; // will hold v* above
while (!active_list.empty()) { // step 3 above
LinearProgram& curr_prob = active_list.dequeue(); // step 3.1
do { // steps 3.2-3.7
RelaxedLinearProgram& relaxed_prob = LP_relax(curr_prob); // step 3.2
LP_solution curr_relaxed_soln = LP_solve(relaxed_prob); // this is x above
bool cutting_planes_found = false;
if (!curr_relaxed_soln.is_feasible()) { // step 3.3
continue; // try another solution; continues at step 3

double current_objective_value = curr_relaxed_soln.value(); // v above
if (current_objective_value <= best_objective) { // step 3.4
continue; // try another solution; continues at step 3

if (curr_relaxed_soln.is_integer()) { // step 3.5
best_objective = current_objective_value;
optimal_solution = cast_as_ILP_solution(curr_relaxed_soln);
continue; // continues at step 3

// current relaxed solution isn't integral
if (hunting_for_cutting_planes) { // step 3.6
violated_cutting_planes = search_for_violated_cutting_planes(curr_relaxed_soln);
if (!violated_cutting_planes.empty()) { // step 3.6
cutting_planes_found = true; // will continue at step 3.2
for (auto&& cutting_plane : violated_cutting_planes) {
active_list.enqueue(LP_relax(curr_prob, cutting_plane));

continue; // continues at step 3.2

// step 3.7: either violated cutting planes not found, or we weren't looking for them
auto&& branched_problems = branch_partition(curr_prob);
for (auto&& branch : branched_problems) {
active_list.enqueue(branch);

continue; // continues at step 3
} while (hunting_for_cutting_planes /* parameter of the algorithm; see 3.6 */
&& cutting_planes_found);
// end step 3.2 do-while loop
} // end step 3 while loop
return optimal_solution; // step 4

In the above pseudocode, the functions `LP_relax`, `LP_solve` and `branch_partition` called as subroutines must be provided as applicable to the problem. For example, `LP_solve` could call the simplex algorithm. Branching strategies for `branch_partition` are discussed below.

## 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 all involve what is called branching on a variable.[3] Branching on a variable involves choosing a variable, [math]\displaystyle{ x_i }[/math], with a fractional value, [math]\displaystyle{ x_i' }[/math], in the optimal solution to the current LP relaxation and then adding the constraints [math]\displaystyle{ x_i \le \left\lfloor x_i' \right\rfloor }[/math] and [math]\displaystyle{ x_i \ge \left\lceil x_i' \right\rceil }[/math]

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]\displaystyle{ 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 considering 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 branching is relatively uninformative and then switching to pseudo cost branching later when there is enough branching history for pseudo cost to be informative.

## References

1. ↑ Padberg, Manfred; Rinaldi, Giovanni (1991). "A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems" (in en). SIAM Review 33 (1): 60–100. doi:10.1137/1033004. ISSN 0036-1445.
2. ↑ John E., Mitchell (2002). "Branch-and-Cut Algorithms for Combinatorial Optimization Problems". Handbook of Applied Optimization: 65–77. http://eaton.math.rpi.edu/faculty/Mitchell/papers/bc_hao.pdf.
3. ↑ Achterberg, Tobias; Koch, Thorsten; Martin, Alexander (2005). "Branching rules revisited" (in en). Operations Research Letters 33 (1): 42–54. doi:10.1016/j.orl.2004.04.002.

## External links

* Mixed Integer Programming
* SCIP: framework for branch-cut-and-price and a mixed integer programming solver
* ABACUS – A Branch-And-CUt System – open source software
* COIN-OR Cbc – open source software on GitHub

* v
* t
* e

Optimization: Algorithms, methods, and heuristics

Unconstrained nonlinear

| … functions|

* Golden-section search
* Interpolation methods
* Line search
* Nelder–Mead method
* Successive parabolic interpolation

|

… and gradients|

| Convergence|

* Trust region
* Wolfe conditions

|

Quasi–Newton|

* Berndt–Hall–Hall–Hausman
* Broyden–Fletcher–Goldfarb–Shanno and L-BFGS
* Davidon–Fletcher–Powell
* Symmetric rank-one (SR1)

Other methods|

* Gauss–Newton
* Gradient
* Levenberg–Marquardt
* Conjugate gradient
* Truncated Newton

… and Hessians|

* Newton's method

Constrained nonlinear

| General|

* Barrier methods
* Penalty methods

|

Differentiable|

* Augmented Lagrangian methods
* Sequential quadratic programming
* Successive linear programming

Convex optimization

| Convex
minimization|

* Cutting-plane method
* Reduced gradient (Frank–Wolfe)
* Subgradient method

|

Linear and
quadratic|

| Interior point|

* Affine scaling
* Ellipsoid algorithm of Khachiyan
* Projective algorithm of Karmarkar

|

Basis-exchange|

* Simplex algorithm of Dantzig
* Revised simplex algorithm
* Criss-cross algorithm
* Principal pivoting algorithm of Lemke

Combinatorial

| Paradigms|

* Approximation algorithm
* Dynamic programming
* Greedy algorithm
* Integer programming
* Branch and bound/cut

|

Graph
algorithms|

| Minimum
spanning tree|

* Borůvka
* Prim
* Kruskal

|

* Bellman–Ford
* Dijkstra
* Floyd–Warshall

Network flows|

* Dinic
* Edmonds–Karp
* Ford–Fulkerson
* Push–relabel maximum flow

Metaheuristics

* Evolutionary algorithm
* Hill climbing
* Local search
* Simulated annealing
* Tabu search

* Software

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Branch and cut. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Branch_and_cut&oldid=74108"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template