# Branch and cut

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

Authors: YenChieh Chou (ChE 345 Spring 2014) Steward: Dajun Yue, Fengqi You

## Introduction

Branch and cut method is a very successful algorithm for solving a variety of integer programming problems, and it also can provide a guarantee of optimality. Many problems involve variables which are not continuous but instead have integer values, and they can be solved by branch-and cut method. This method are exact algorithm consisting of a combination of a cutting plane method and a branch-and-bound algorithm.

## Algorithm

### Problem Statement

the above is a standard mixed-integer linear problem. the x and c are n-vector; b is m-vector; A is a m*n matrix. if p=n, then the problem will become a pure integer linear problem. moreover, we can set the whole variables is equal to 0 or 1, then these variables will be a binary variables. Pure branch-and-bound can be speed up by combining cutting planes at the top of a branch-and-bound tree or at every node of the tree, because cutting planes considerably reduce the size of the tree.

### Algorithm Process

1. Initialzation: Denote the initial LP problem by $ILP^0$ and set the active nodes to be $L={ILP^0}$. set the upper bound to be $z^h$=+∞. select one problem l∈L and set its lower-bound ont he optimal value is $z^l$=-∞.

2. Termination:if L=∅,then the solution x which yielded the incumbent objetive value z is optimal. if the x not exist, then the ILP is infeasible.

3. Problem selection: select and delete a problem $ILP^l$ from L.

4. Relaxation: solve the LPR of $ILP^l$. If the ralaxation is infeasible, set $z^h$=+∞ and go to step 6.

5. Add Cutting Planes: Search for cutting planes, and if any are found, add them to the relazation and return to step 4.

6. Fathoming & Pruning:

(a)If $z^l$≥z, then go to step 2

(b)If $z^l$<z and $x^IR$ is integral feasible, then update z=$z^l$, delete all problem with $z^l$≥z, and go to step 2.

7. Partitioning: let be a partition of the constraint set $S^l$ of problem $ILP^l$. Add problems to L, where $ILP^lj$ is $ILP^l$ with feasible region restricted to $S^lj$ and for j=1,...k is set to the value of $z^l$ for thr parent problem l. Go to step 2.

### Generating Cutting Planes

Try to get better bounds so that more nodes of the branch and bound tree can be fathomed as early as possible. the idea is adding constraints that eliminate fractional solutions to the LP without eliminating any integer solutions. If we add exactly the right inequalities, the every extreme point of the LP will be integer If we add the right inequalities and the IP can be solved by solving the LP. The cutting planes take a weighted combination of the inequalities from the current LPR, and exploiting the fact that variables must be integral. So we also called this method "Chvatal-Gomory Cutting Planes"

#### example

LHS of the inequality is round down, which gives

In any feasible solution to an IP, the LHS must take an integer vaalue, so the Rhs is round down.

finally we have the valid inequality:

## Example

The integer programming problem

Sub-problems generated by branching on X1

### Comparison

We can found that there are only three steps for branch-and-cut method; however, the branch-and-bound method uses 4 steps to solve the same problem. We can prove that using the branch-and-cut method is faster than using the branch-and-bound method

## Conclusion

There are many methods to solve the mixed-integer linear programming. Gomory Cutting Planes is fast, but unreliable. Branch and Bound is reliable but slow. The Branch and cut combine the advantages from these two methods and improve the defects. It has proven to be a very successful approach for solving a wide variety of integer programming problems. We can solve the MILP by taking some cutting planes before apply whole system to the branch and bound, Branch and cut is not only reliable, but faster than branch and bound alone. Finally, we understand that using branch and cut is more efficient than using branch and bound.

## Reference

1. John E. Mitchell,Branch-and-Cut Algorithms for Combinatorial Optimization Problems, 1999

2. Shon Albert,Solving Mixed Integer Linear Programs Using Branch and Cut Algorithm,1999

3. Laurence Wolsey, Integer Programming, John Wiley and Sons, Inc, 1998

4. Jacques Desrosiers,Branch-Price-and-Cut Algorithms,2010