Branch and CutBranch and CutBranch and CutBranch and CutBranch and CutBranch and CutBranch and CutBranch and CutBranch and CutBranch and Cut•It is the combination of the Cutting Plane and Branch and Bound Algorithms. •We show the principle below through an example.Branch and Cut•Branch and CutBranch and Cut•Branch and Cut•Branch and Cut•The optimal solution to the original problem will be the better of the solutions to these two subproblems. •The solution to the linear programming relaxation of Eq1 is (3,2), with value (-28). This solution is integral, so it solves Eq1, and becomes the incumbent best known feasible solution. •The LP relaxation of Eq2 has optimal solution (2,3.5), with value (-29.5). This point is nonintegral, so it does not solve Eq2, and it must be attacked further.Branch and Cut•Branch and Cut•The LP relaxation of Eq3 has optimal solution (1.8,3.4), with value (-27.8). 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 to the second subproblem must be at least as large as the value of the relaxation. Therefore, the incumbent solution is better than any feasible integral solution for Eq3, so it actually solves the original problem.Branch and Cut•The progress of the algorithm is illustrated
View Full Document
Unlocking...