10/15/2018 Branch and cut - optimization

Branch and cut

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

Contents
1 Introduction
2 Algorithm
2.1 Problem Statement
2.2 Algorithm Process
2.3 Generating Cutting Planes
2.3.1 example
3 Example
3.1 Comparison
4 Conclusion
5 Reference

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

https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&printable=yes 1/6
10/15/2018 Branch and cut - optimization

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

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.
https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&printable=yes 2/6
10/15/2018 Branch and cut - optimization

finally we have the valid inequality:

Example
The integer programming problem

Sub-problems generated by branching on X1

Add a cut to P2

https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&printable=yes 3/6
10/15/2018 Branch and cut - optimization

Comparison

https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&printable=yes 4/6
10/15/2018 Branch and cut - optimization

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

https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&printable=yes 5/6
10/15/2018 Branch and cut - optimization

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

Retrieved from "https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&oldid=1049"

This page was last modified on 8 June 2014, at 23:14.

https://optimization.mccormick.northwestern.edu/index.php?title=Branch_and_cut&printable=yes 6/6