Improved Performance Through Cutting Plane Technique
Learn how the cutting plane technique enhances the performance of integer programs by adding constraints that maintain the set of feasible integer solutions while improving the LP-relaxation feasible region. Examples illustrate the concept and its application to problems like the Bin Packing Problem.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Cutting Plane Technique for Solving Integer Programs 1
Motivating Example for Cutting Planes Recall the bad-case example for the LP-rounding algorithm: Integer Program max x1 + 5x2 s.t. x1 +10x2 20 x1 2 x1 , x2 0 integer LP relaxation max x1 + 5x2 s.t. x1 +10x2 20 x1 2 x1 , x2 0 x1 = 2 Solution to LP-relaxation: (2, 1.8) Rounded IP solution: (2, 1) with value 7 IP optimal solution: (0, 2) with value 10 Conclusion: Rounded solution too far from optimal solution x1 +10x2 = 20 Z=11 2
How can we improve the performance of the LP-rounding? Add the following new constraint to the problem: x1 + 2x2 4 . New Integer Program max x1 + 5x2 s.t. x1 +10x2 20 x1 2 x1 + 2x2 4 x1 , x2 0 integer The set of feasible integer points is the same for the old and new IPs But the feasible region of the new LP-relaxation is different: some of the fractional points are cut off As a result, the optimal solution of the new LP-relaxation, (0,2) is also the optimal IP solution. New LP relaxation max x1 + 5x2 s.t. x1 +10x2 20 x1 2 x1 + 2x2 4 x1 , x2 0 x1 = 2 (0, 2) x1 +10x2 = 20 Z=10 x1 + 2x2 = 4 3
General Idea of Cutting Plane Technique Add new constraints (cutting planes) to the problem such that (i) the set of feasible integer solutions remains the same, i.e., we still have the same integer program. (ii) the new constraints cut off some of the fractional solutions making the feasible region of the LP-relaxation smaller. Smaller feasible region might result in a better LP value (i.e., closer to the IP value), thus making the search for the optimal IP solution more efficient. Each integer program might have many different formulations. Important modeling skill: Give as tight formulation as possible. How? Find cutting planes that make the formulation of the original IP tighter. 4
Example of making a formulation tighter: Bin Packing Problem Given: Goal: Pack the items into the bins Example: n=13 items with sizes 20, 20, 20, 20, 20, 81, 81, 81, 81, 82, 91, 49, 51 ; Bin size is W=100. Minimum number of bins needed is 8. n items with sizes s[1], s[2], , s[n]; bins with size W (where W s[i], any i=1, ,n). using as few bins as possible. 5
Example of making a formulation tighter: Bin Packing Problem Want an IP formulation for this problem. Let M be an upper bound on the number of bins needed. (M=n is a safe upper bound; but should try for smaller values) Define the following variables. For j=1, ,M, let open[j] 1 if bin j used is = 0 if not For each i=1, ,n and j=1, ,M, let 1 if item is i packed in bin j = assign[i, j] 0 if not 6
Example of making a formulation tighter: Bin Packing Problem Our objective is to minimize the number of used bins: Minimize sum{j in 1..M}open[j] We need the following functional constraints. Each item should be packed in exactly one bin: (C1) sum{j in 1..M}assign[i,j] = 1 , for each i=1, ,n Each bin can contain items of total size at most W: (C2) sum{i in 1..n}s[i]*assign[i,j] W , Items can be packed only in open bins: (C3) assign[i,j] open[j] , for each j=1, ,M for each i=1, ,n and j=1, ,M Set constraints: All variables are binary. 7
Example of making a formulation tighter: Bin Packing Problem The optimal solution to the LP relaxation: open[j] = 1/M , assign[i,j] = 1/M , with optimal value M * 1/M = 1 . Let s check that it really satisfies the constraints: (C1) sum{j in 1..M}assign[i,j] = 1 , for each i=1, ,n For this solution, M * 1/M = 1 . (C2) sum{i in 1..n}s[i]*assign[i,j] W , For this solution, sum{i in 1..n} s[i] / M W . (C3) assign[i,j] open[j] , For this solution, 1/M 1/M . for each i=1, ,n and j=1, ,M for each j=1, ,M for each i=1, ,n and j=1, ,M 8
Example of making a formulation tighter: Bin Packing Problem The optimal solution with value 1 might be too far from the optimal IP solution. E.g., recall that we needed 8 bins for our example with 13 items. Thus, the bound given by the LP-relaxation is too loose. How to make the IP formulation tighter? Replace constraints (C2) with the following constraints: (C2 ) sum{i in 1..n}s[i]*assign[i,j] W*open[j] , Note that these constraints are valid for the integer program (i.e., no feasible integer point is cut off). But it cuts off some of the fractional points, particularly the optimal solution of the old LP-relaxation. The optimal solution of the new LP-relaxation has value 6.97 for our example. This is a much tighter lower bound for the optimal IP value 8. for each j=1, ,M 9
Methods of getting Cutting Planes 1) Exploit the special structure of the problem Often can be hard to get Topic of intensive research 2) More general methods are also available Can be used automatically for many problems 3) Often so-called branch-and-cut algorithms (some combination of branch-and-bound and cutting planes) are used to solve integer programs. to get cutting planes More examples in the next handout 10
