This document presents the branch and cut method for solving integer programming problems. It begins with an introduction that classifies algorithms for integer programs. It then describes the branch and cut method, which uses both cutting planes and branch and bound. An example problem demonstrates how branch and cut works by solving relaxations, adding cutting planes, and branching. The document concludes that branch and cut combines the advantages of cutting planes and branch and bound to efficiently solve mixed integer linear programs.
This document presents the branch and cut method for solving integer programming problems. It begins with an introduction that classifies algorithms for integer programs. It then describes the branch and cut method, which uses both cutting planes and branch and bound. An example problem demonstrates how branch and cut works by solving relaxations, adding cutting planes, and branching. The document concludes that branch and cut combines the advantages of cutting planes and branch and bound to efficiently solve mixed integer linear programs.
This document presents the branch and cut method for solving integer programming problems. It begins with an introduction that classifies algorithms for integer programs. It then describes the branch and cut method, which uses both cutting planes and branch and bound. An example problem demonstrates how branch and cut works by solving relaxations, adding cutting planes, and branching. The document concludes that branch and cut combines the advantages of cutting planes and branch and bound to efficiently solve mixed integer linear programs.
This document presents the branch and cut method for solving integer programming problems. It begins with an introduction that classifies algorithms for integer programs. It then describes the branch and cut method, which uses both cutting planes and branch and bound. An example problem demonstrates how branch and cut works by solving relaxations, adding cutting planes, and branching. The document concludes that branch and cut combines the advantages of cutting planes and branch and bound to efficiently solve mixed integer linear programs.
Department of Mathematics Branch and Cut Prepared and presented by : Heythem Marhoune Sid Ahmed Benchiha Amina-Zahra Rezazgui Ibtissem Ben Kemache Hanaa Kerim Lilia Benakkouche Sara Chabbi Sara Boutata
Supervised and edited by : Dr. Baha Alzalg
Integer and Combinatorial Optimization (0301973)
Spring 2018 Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 1 / 17 Sommaire
1 Introduction
2 Description of the Branch and Cut Method
3 Example of the Branch and Cut Paradigm
4 Conclusion
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 2 / 17
Introduction
Classification
An integer programming problem is a mathematical optimization or
feasibility program in which some or all of the variables are restricted to be integers which is very difficult to solve. However, there are three different types of algorithms : 1 Exact algorithms. 2 Approximation algorithms. 3 Heuristic algorithms.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 3 / 17
Introduction
Exact Algorithms
Examples of exact algorithms designed and used to solve
combinatorial optimization problems : 1 Cutting Plane Method. 2 Branch and Bound Method. 3 Branch and Cut Method. 4 Dynamic Programming. In this work, we present a method called the Branch and Cut Method.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 4 / 17
Description of the Branch and Cut Method
Description
The Branch and Cut Method is a combinatorial optimization
algorithm for solving IPL. This method uses both the Branch and Bound Method and the Cutting Plane Method. In particular, we augment the formulation of subproblem with additional cuts, in order to improve the bounds obtained from the linear programming relaxations. We illustrate the method with an example.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 5 / 17
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 6 / 17
Example of the Branch and Cut Paradigm
As illustrated in Figure 1. The feasible integer points are marked.
The linear programming relaxation (or LP relaxation) is obtained by ignoring the integrality restrictions and is indicated by the polyhedron contained in the solid lines.
Figure 1 : Two dimensional integer programming problem of our Ex.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 7 / 17
Example of the Branch and Cut Paradigm
The Branch and Cut Method first solves the linear programming 3 5 1 relaxation, giving the point 2 + , 3 + , with value - 33 − . 7 7 7 There is now a choice : Should the LP relaxation be improved by adding a cutting plane, for example, x1 + x2 ≤ 5, or should the problem be divided into two by splitting on a variable ? If the algorithm splits on x1 , two new problems are obtained :
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 8 / 17
Example of the Branch and Cut Paradigm
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 9 / 17
Example of the Branch and Cut Paradigm
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 10 / 17
Example of the Branch and Cut Paradigm
The optimal solution to the original problem will be better than the solutions of these two subproblems. The solution of the linear programming relaxation of (F1 ) is (3, 2), with the optimal value −28. This solution is integral, so it solves (F1 ), and becomes the incumbent best known feasible solution. The LP relaxation of (F2 ) has optimal solution (2, 3.5), with the optimal value −29.5. This point is non-integral, so it does not solve (F2 ), and hence it must be attacked further.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 11 / 17
Example of the Branch and Cut Paradigm
Assume the algorithm uses a cutting plane approach and adds the inequality 2x1 + x2 ≤ 7 to (F2 ). This is a valid inequality, for which it is satisfied by every integral point that is feasible in (F2 ). Further, this inequality is violated by (2, 3.5), so it is a cutting plane. The resulting subproblem is : min −6x1 − 5x2 s.t. 3x1 + x2 ≤ 11 −x1 + 2x2 ≤ 5 (F3 ) x1 ≤ 2 2x1 + x2 ≤ 7 x1 , x2 ≥ 0 and both integers.
The LP relaxation of (F3 ) has the optimal solution (1.8, 3.4) with the optimal value −27.8.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 12 / 17
Example of the Branch and Cut Paradigm
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 13 / 17
Example of the Branch and Cut Paradigm
Notice that the optimal value for this modified relaxation is larger than the value of the incumbent solution. The value of the optimal integral solution for the second subproblem must be at least as large as the value of the relaxation. Therfore, the incumbent solution is batter than any feasible integral solution for (F3 ), so it actually solves the original problem.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 14 / 17
Example of the Branch and Cut Paradigm
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 15 / 17
Example of the Branch and Cut Paradigm
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 16 / 17
Conclusion
Conclusion
There are some methods to solve the mixed-integer linear
programming. The Gomory Cutting Plane Method is fast, but unreliable. Branch and Bound Method is reliable but slow. The Branch and Cut Method combines 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 the whole system to the branch and bound. Branch and Cut Method is not only reliable, but also faster than branch and bound alone. Finally, we understand that using Branch and Cut Method is more efficient than using the Branch and Bound Method.
Integer Optimization (University of Jordan) BRANCH AND CUT 30-04-2018 17 / 17
