Cutting Planes II
Cutting Planes II
The Knapsack Problem
Recall the knapsack problem:
•
n
items to be packed in a knapsack
(can take multiple copies of the same item).
•
The knapsack can hold up to
W lb
of items.
•
Each item has weight
w
i
lb
and benefit
b
i
.
•
Goal:
Pack the knapsack such that
the total benefit is maximized.
IP model for Knapsack problem
•
Define decision variables (
i
= 1, …, n):
x
i
= number of copies of item i to take
•
Then the total benefit:
the total weight:
Summarizing, the IP model is:
max
s.t.
x
i
≥ 0
integer (
i
= 1, …, n)
Cutting Planes for Knapsack Problem
•
Example
:
Knapsack size is
W=50
.
•
Size constraint for this example:
21x
1
+11x
2
+51x
3
+26x
4
+30x
5
50
.
•
IP optimum:
(1, 0, 0, 1, 0)
with value
87
.
LP-relax. optimum:
(0, 0, 50/51, 0, 0)
with value
490.2
.
LP solution is too far from IP solution.
•
How to cut the fractional optimal solution?
Add the following constraint (cutting plane):
x
3
= 0
.
Cuts off the old LP optimum:
(0, 0, 50/51, 0, 0)
with value
490.2
.
The new LP-relax. optimum:
(0, 0, 0, 50/26, 0)
with value
96.2
.
Cutting Planes for Knapsack Problem
•
More cutting planes? Add constraint
x
4
1
.
Cuts off the old LP optimum:
(0, 0, 0, 50/26, 0)
with value
96.2
.
The new LP-relax. optimum:
(24/21, 0, 0, 1, 0)
with value
92.3
.
•
Generally, for item i we can add the following cutting plane:
x
i
W / w
i
.
•
E.g.,
x
1
2
. Note, however, that this constraint doesn’t cut
the LP-optimum:
(24/21, 0, 0, 1, 0)
.
Can we add better (tighter) cutting planes?
•
Cutting planes can include more than one variable.
E.g., the following constraint is a valid cutting plane:
x
1
+ x
4
2
.
(Note that this constraint is tighter than
x
1
2
).
Cuts off the old LP optimum:
(24/21, 0, 0, 1, 0)
with value
92.3
.
The new LP-relax. optimum:
(1, 0, 0, 1, 1/10)
with value
91.1
.
Cutting Planes for Knapsack Problem
•
General form of cutting planes with more than one variable.
Let
k
≥1
and
S={ i | wi
> W / k }
.
Then we have the following cutting plane:
•
Take
k=3
in our example.
Then
S= { i | wi
> W / 3 } = {1, 3, 4, 5} .
Thus, we have the following cutting plane:
x
1
+ x
3
+ x
4
+ x
5
2
.
(Note that this constraint is tighter than
x
1
+ x
4
2
).
Cuts off the old LP optimum:
(1, 0, 0, 1, 1/10)
with value
91.1
.
The new LP-relax. optimum:
(1, 3/11, 0, 1, 0)
with value
90.3
.
Pairing Problem
•
2n
students
•
n
projects; each project needs two students
•
Value of pairing students
i
and
j
is
value[i , j]
•
Goal:
Pair up the students to work on the projects
so that the total value is maximized.
•
Example
: 4 students, 2 projects, value matrix:
Possible solutions:
(A, B), (C, D) with value 9
(A, C), (B, D) with value 17
(A, D), (B, C) with value 2
Optimal solution:
(A, C), (B, D)
IP Formulation for the Pairing Problem
•
Define the following variables. For any
i
1,…,2n
and
j
1,…,2n (i
j)
,
•
The goal is to maximize the total value:
Maximize 0.5 * sum{i
1,…,2n, j
1,…,2n : i
j}value[i,j]*x[i,j]
•
Need the following constraints.
Symmetry constraints:
x[i,j]= x[j,i]
for each i
1,…,2n, j
1,…,2n (i
j)
Each student works with exactly one other student:
sum{j
1,…,2n : i
j}x[i,j] = 1
for each i
1,…,2n
•
Q
: How good (tight) is this formulation?
Solving the LP-relaxation
•
Consider the following example:
There are multiple optimal
IP solutions
with value
21
The optimal solution to the LP-relaxation:
x[A,B] = x[B,A] = x[A,C] = x[C,A] = x[B,C] = x[C,B] = .5
;
x[D,E] = x[E,D] = x[D,F] = x[F,D] = x[E,F] = x[F,E] = .5
;
all other variables have value
0
.
Optimal LP value:
6*0.5*10 = 30
A
B
C
D
E
F
.5
.5
.5
.5
.5
.5
Cutting Planes for the Pairing Problem
•
Add the following cutting plane:
sum{ i
S, j
S
} x[i, j]
≥ 1
for
S = {A, B, C}Cuts off the old LP optimum with value
30
.
The new LP-relaxation has multiple optimal solutions with value
21
.
•
General form
:
For any set
S
{1,…,2n}that has an odd number of elements
sum{ i
S, j
S
} x[i, j]
≥ 1
is a cutting plane.
•
Note that the number of this kind of cutting planes is exponential
(order of 2
n
); so can’t add all of them in the IP formulation.
Thus, this kind of cutting planes should be added only if necessary
(to cut off a fractional solution of the current LP relaxation).
Branch-and-cut algorithms
•
Integer programs are rarely solved based solely on cutting
plane method.
•
More often cutting planes and branch-and-bound are
combined to provide a powerful algorithmic approach for
solving integer programs.
•
Cutting planes are added to
the subproblems created in branch-and-bound
to achieve tighter bounds
and thus to accelerate the solution process.
•
This kind of methods are known as
branch-and-cut algorithms
.
Exploring advanced optimization techniques with cutting planes for the Knapsack Problem. Learn how to improve solution efficiency by adding constraints to the integer programming model and tightening LP relaxations. Follow examples and strategies for achieving optimal knapsack packing solutions using cutting planes.
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
The Knapsack Problem Recall the knapsack problem: n items to be packed in a knapsack (can take multiple copies of the same item). The knapsack can hold up to W lb of items. Each item has weight wilb and benefit bi. Goal: Pack the knapsack such that the total benefit is maximized.
IP model for Knapsack problem Define decision variables (i = 1, , n): xi= number of copies of item i to take Then the total benefit: n = i b ix i n = i 1 the total weight: w ix i 1 Summarizing, the IP model is: max n = i b ix i 1 n =1 s.t. w x W i i i xi 0 integer (i = 1, , n)
Cutting Planes for Knapsack Problem Example: item 1 2 size 21 11 benefit 37 12 3 4 5 51 500 26 30 50 41 Knapsack size is W=50. Size constraint for this example: 21x1+11x2+51x3+26x4+30x5 50. IP optimum: (1, 0, 0, 1, 0) with value 87 . LP-relax. optimum: (0, 0, 50/51, 0, 0) with value 490.2 . LP solution is too far from IP solution. How to cut the fractional optimal solution? Add the following constraint (cutting plane): x3= 0 . Cuts off the old LP optimum: (0, 0, 50/51, 0, 0) with value 490.2 . The new LP-relax. optimum: (0, 0, 0, 50/26, 0) with value 96.2 .
Cutting Planes for Knapsack Problem More cutting planes? Add constraint x4 1 . Cuts off the old LP optimum: (0, 0, 0, 50/26, 0) with value 96.2 . The new LP-relax. optimum: (24/21, 0, 0, 1, 0) with value 92.3 . Generally, for item i we can add the following cutting plane: xi W / wi . E.g., x1 2 . Note, however, that this constraint doesn t cut the LP-optimum: (24/21, 0, 0, 1, 0) . Can we add better (tighter) cutting planes? Cutting planes can include more than one variable. E.g., the following constraint is a valid cutting plane: x1 + x4 2 . (Note that this constraint is tighter than x1 2 ). Cuts off the old LP optimum: (24/21, 0, 0, 1, 0) with value 92.3 . The new LP-relax. optimum: (1, 0, 0, 1, 1/10) with value 91.1 .
Cutting Planes for Knapsack Problem General form of cutting planes with more than one variable. Let k 1 and S={ i | wi > W / k } . Then we have the following cutting plane: S i 1 x k i Take k=3 in our example. Then S= { i | wi > W / 3 } = {1, 3, 4, 5} . Thus, we have the following cutting plane: x1 + x3 + x4 + x5 2 . (Note that this constraint is tighter than x1 + x4 2 ). Cuts off the old LP optimum: (1, 0, 0, 1, 1/10) with value 91.1 . The new LP-relax. optimum: (1, 3/11, 0, 1, 0) with value 90.3 .
Pairing Problem 2n students n projects; each project needs two students Value of pairing students i and j is value[i , j] Goal: Pair up the students to work on the projects so that the total value is maximized. Example: 4 students, 2 projects, value matrix: A B C D A - 5 10 1 B 5 - 1 7 C 10 1 - 4 D 1 7 4 - Possible solutions: (A, B), (C, D) with value 9 (A, C), (B, D) with value 17 (A, D), (B, C) with value 2 Optimal solution: (A, C), (B, D)
IP Formulation for the Pairing Problem Define the following variables. For any i 1, ,2n and j 1, ,2n (i j), = not if 0 1 if students work j and i on the same project x[i, j] The goal is to maximize the total value: Maximize 0.5 * sum{i 1, ,2n, j 1, ,2n : i j}value[i,j]*x[i,j] Need the following constraints. Symmetry constraints: x[i,j]= x[j,i] for each i 1, ,2n, j 1, ,2n (i j) Each student works with exactly one other student: sum{j 1, ,2n : i j}x[i,j] = 1 for each i 1, ,2n Q: How good (tight) is this formulation?
Solving the LP-relaxation Consider the following example: There are multiple optimal IP solutions with value 21 A - 10 10 1 1 1 B 10 - 10 1 1 1 C 10 10 - 1 1 1 D 1 1 1 - 10 10 E 1 1 1 10 - 10 F 1 1 1 10 10 - A B C D E F B D .5 .5 A .5 E .5 .5 .5 C F The optimal solution to the LP-relaxation: x[A,B] = x[B,A] = x[A,C] = x[C,A] = x[B,C] = x[C,B] = .5 ; x[D,E] = x[E,D] = x[D,F] = x[F,D] = x[E,F] = x[F,E] = .5 ; all other variables have value 0 . Optimal LP value: 6*0.5*10 = 30
Cutting Planes for the Pairing Problem Add the following cutting plane: sum{ i S, j S } x[i, j] 1 for S = {A, B, C} Cuts off the old LP optimum with value 30. The new LP-relaxation has multiple optimal solutions with value 21. General form: For any set S {1, ,2n} that has an odd number of elements sum{ i S, j S } x[i, j] 1 Note that the number of this kind of cutting planes is exponential (order of 2n); so can t add all of them in the IP formulation. Thus, this kind of cutting planes should be added only if necessary (to cut off a fractional solution of the current LP relaxation). is a cutting plane.
Branch-and-cut algorithms Integer programs are rarely solved based solely on cutting plane method. More often cutting planes and branch-and-bound are combined to provide a powerful algorithmic approach for solving integer programs. Cutting planes are added to the subproblems created in branch-and-bound to achieve tighter bounds and thus to accelerate the solution process. This kind of methods are known as branch-and-cut algorithms.
