Branch and cut
Authors: YenChieh Chou (ChE 345 Spring 2014) Steward: Dajun Yue, Fengqi You
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.
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.
1. Initialzation: Denote the initial LP problem by and set the active nodes to be . set the upper bound to be =+∞. select one problem l∈L and set its lower-bound ont he optimal value is =-∞.
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 from L.
4. Relaxation: solve the LPR of . If the ralaxation is infeasible, set =+∞ 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, then go to step 2
(b)If <z and is integral feasible, then update z=, delete all problem with ≥z, and go to step 2.
7. Partitioning: let be a partition of the constraint set of problem . Add problems to L, where is with feasible region restricted to and for j=1,...k is set to the value of 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"
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:
The integer programming problem
Sub-problems generated by branching on X1
Add a cut to P2
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
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.
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