3. (45pts) Suppose that you have the following integer programming problem: e(0.
ID: 351380 • Letter: 3
Question
3. (45pts) Suppose that you have the following integer programming problem: e(0.1). frjs 1, 2, 3, 4. 3.1. (5pts) Solve this problem performing a brute force approach, i.e., do the enumeration tree and identify the optimal solution to the problem 3.2. (20pts) Solve this problem using the branch-and-bound method, where you should use the simplex method when dealing with four or three variables and the graphical method when dealing with two. 3.3. (20pts) Solve this problem using the cutting plane method. Specifically, use the Gomory method and explain the steps taken.Explanation / Answer
BB algorithm to solve the following ILP:
maximize
9x1 + 5x2
+ 6x3
+ 4x4
subject to
6x1 + 3x2
+ 5x3
+ 2x4 10
x1
x3 + x4 1
+ x3
0
x2
+ x4 0
xj {0, 1} j = 1, . . . , 4
Initialization
At the initial node, we would solve its LP relaxation
maximize
9x1 + 5x2
+ 6x3
+ 4x4
subject to
6x1 + 3x2
+ 5x3
+ 2x4 10
x1
x3 + x4 1
+ x3
0
x2
+ x4 0
0 xj 1 j = 1, . . . , 4
Using LP algorithm, we find the optimal value (5/6, 1, 0, 1) and the optimal value z = 1612.
If the solution and the optimal value were integers, we would stop.
Since it is not, this value gives us 16 as the best lower bound on the optimal value of the ILP (blb = 16).
The initialization and moving to the first iteration
Iteration 1:
We branch from the LP relaxation (ALL node) into two new nodes corresponding to x1 = 1 and x1 = 0.
At node x1 = 1 we solve the following LP
maximize 9 + 5x2 + 6x3 + 4x4
subject to
3x2 + 5x3 + 2x4 4
x3 + x4 1
x3
1
x2
+ x4 0
0 xj 1 j = 2, . . . , 4
At node x1 = 0 we solve the following LP
maximize
5x2 + 6x3 + 4x4
subject to
3x2 + 5x3 + 2x4 10
x3 + x4 1
x3
0
x2
+ x4 0
0 xj 1 j = 2, . . . , 4
Node to the right is incumbent and fathomed (no branching there ever). Node to the left is the only active node and most recent.
Iteration 2:
We branch from the node x1 = 1 going to nodes x2 = 1 and x2 = 0. At node x2 = 1 (also we have x1 = 1), we solve the following LP
maximize
14 + 6x3 + 4x4
subject to
5x3 + 2x4 1
x3 + x4 1
x3
1
x4 1
0 xj 1 j = 3, 4
The solution is (1, 1, 0, 1/2) and the optimal value is 16.
At node x2 = 0 (and x1 = 1) we solve the following LP
maximize
9 + 6x3 + 4x4
subject to
5x3 + 2x4 4
x3 + x4 1
x3
1
x4 0
0 xj 1 j = 3, 4
The solution is (1, 0, 4/5, 0) and the optimal value is 1345.
We round this value down to 13.
At this point, we have two active nodes that are also the most recent (the two at the level x2).
Iteration 3:
We branch from the node x2 = 1 since it has a larger bound of the two active nodes (16 and 13).
We create two new nodes x3 = 1 and x3 = 0.
At node x3 = 1 (branch x1 = 1 and x2 = 1), we solve the following LP
maximize
20 + 4x4
subject to
2x4 4
x4 0
x4 1
0 x4 1
This LP has no solution - it is infeasible. We fathom this node.
We now create node x3 = 0 (x1 = 1, x2 = 1).
At this node we solve the following LP
maximize
14 + 4x4
subject to
2x4 1
x4 1
0 x4 1
The solution is (1, 1, 0, 1/2) and the optimal value is 16. This node remains active.
At this point, nodes x2 = 0 and x3 = 0 are active.
Iteration 4:
We branch from the node x3 = 0 since it is a more recent of the two remaining active nodes.
We create two new nodes x4 = 1 and x4 = 0.
At node x4 = 1 the problem reduces to: having a point (1, 1, 0, 1) and the “LP of the form”
maximize
20
subject to
2
4
1
0
1
1
The LP has no solution - it is infeasible. We fathom this node.
We now create node x4 = 0
At this node we have the following LP
maximize
14
subject to
0 1
and the point (1, 1, 0, 0) being feasible. The optimal value is 14.
This node becomes a new incumbent node. A new best value is Z = 14.
At this point, only the node x2 = 0 is active. Its value is smaller than the current best
Z = 14, so we fathom this node. Since no node is active, the algorithm terminates. The optimal point and the value are given by the solution and the value at the best incumbent node, namely (1, 1, 0, 0) and Z = 14.
maximize
9x1 + 5x2
+ 6x3
+ 4x4
subject to
6x1 + 3x2
+ 5x3
+ 2x4 10
x1
x3 + x4 1
+ x3
0
x2
+ x4 0
xj {0, 1} j = 1, . . . , 4
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.