Branch and cut

From optimization
Jump to: navigation, search

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

Contents

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

Wiki-2.png


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 Wiki-3.png be a partition of the constraint set S^l of problem ILP^l. Add problems WIKI-4.png to L, where ILP^lj is ILP^l with feasible region restricted to S^lj and Wiki-5.png 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

Wiki-6.png

LHS of the inequality is round down, which gives

Wiki-7.png

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:

WIKI-1.png

Example

The integer programming problem

Wiki-9 2.png

Sub-problems generated by branching on X1

Wiki-10 2.png Wiki-11.png


Wiki-12 2.png Wiki-13.png


Add a cut to P2

Wiki-14 2.png Wiki-15.png


Comparison

Wiki-16.png Wiki-30 4.png

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