View source for Branch and cut

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 ===


[[File:wiki-2.png|200px]]


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 <math>ILP^0</math> and set the active nodes to be <math>L={ILP^0}</math>. set the upper bound to be <math>z^h</math>=+{{Unicode|&infin;}}. select one problem l∈L and set its lower-bound ont he optimal value is <math>z^l</math>=-{{Unicode|&infin;}}.

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 <math>ILP^l</math> from L.

4. Relaxation: solve the LPR of <math>ILP^l</math>. If the ralaxation is infeasible, set <math>z^h</math>=+{{Unicode|&infin;}} 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 <math>z^l</math>≥z, then go to step 2

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

7. Partitioning: let [[File:wiki-3.png]] be a partition of the constraint set <math>S^l</math> of problem <math>ILP^l</math>. Add problems [[File:WIKI-4.png]] to L, where <math>ILP^lj</math> is <math>ILP^l</math> with feasible region restricted to <math>S^lj</math> and [[File:wiki-5.png]] for j=1,...k is set to the value of <math>z^l</math> 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 ====
[[File:wiki-6.png|300px]]

LHS of the inequality is round down, which gives 

[[File:wiki-7.png|100px]]

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:

[[File:WIKI-1.png]]

== Example ==
The integer programming problem

[[File:wiki-9_2.png|400px]]

Sub-problems generated by branching on X1

[[File:wiki-10_2.png|300px]]    [[File:wiki-11.png|200px]]


[[File:wiki-12_2.png|300px]]    [[File:wiki-13.png|200px]]

 
Add a cut to P2

[[File:wiki-14_2.png|300px]]    [[File:wiki-15.png|200px]] 


===Comparison===

[[File:wiki-16.png|400px]]      [[File:wiki-30_4.png|550px]]

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