Integer Programming (2) : Danu Hadi Syaifullah ST., MSC., PH.D
Integer Programming (2) : Danu Hadi Syaifullah ST., MSC., PH.D
• Formally applying the fathoming tests, we see that the first solution passes
test 3 and the second passes test 2. Furthermore, this feasible first solution is
better than the incumbent (14 > 9), so it becomes the new incumbent, with
Z* = 14.
•
Completing the Example
Iteration 4
• Because a new incumbent has been found, we now reapply fathoming
test 1 with the new larger value of Z* to the only remaining subproblem, the
one at node (1, 0).
• Subproblem 3: Bound = 13 < Z* = 14. Therefore, this subproblem now is
fathomed.
Branch and Bound for Pure & Mix
IP
Branching:
• Among the remaining (unfathomed) subproblems, select the one that was
created most recently. (Break ties according to which has the larger
bound).
• Among the integer-restricted variables that have a noninteger value in the
optimal solution for the LP relaxation of the subproblem, choose the first
one in the natural ordering of the variables to be the branching variable.
• Let xj be this variable and xj* its value in this solution.
• Using square brackets to denote
[xj*] = greatest integer ≤ xj
• Branch from the node for the subproblem to create two new subproblems
by adding the respective constraints xj ≤ [xj*] and xj ≥ [xj*] + 1
Branch and Bound for Pure & Mix
IP
Bounding:
For each new subproblem, obtain its bound by applying the simplex
method (or the dual simplex method when reoptimizing) to its LP
relaxation and using the value of Z for the resulting optimal solution.
Branch and Bound for Pure & Mix
IP
Fathoming:
For each new subproblem, apply the three fathoming tests given
below, and discard those subproblems that are fathomed by any of
the tests.
1. Test 1: Its bound ≤ Z*, where Z* is the value of Z for the current
incumbent.
2. Test 2: Its LP relaxation has no feasible solutions.
3. Test 3: The optimal solution for its LP relaxation has integer values for
the integer-restricted variables. (If this solution is better than the
incumbent, it becomes the new incumbent and test 1 is reapplied
to all unfathomed subproblems with the new larger Z*.)
Example
We will now illustrate this algorithm by applying it to the following
MIP problem:
Example
Initialization. After setting Z* = -∞, we form the LP relaxation of this problem by
deleting the set of constraints that xj is an integer for j = 1, 2, 3. Applying the
simplex method to this LP relaxation yields its optimal solution below:
Because it has feasible solutions and this optimal solution has noninteger
values for its integer-restricted variables, the whole problem is not fathomed,
so the algorithm continues with the first full iteration
Example
Iteration 1.
In this optimal solution for the LP relaxation, the first integer-restricted
5
variable that has a noninteger value is x1= , so x1 becomes the branching variable.
4
Branching from the All node (all feasible solutions) with this branching variable then
creates the following two subproblems:
Example
Iteration 1.
This outcome for subproblem 2 means that it is fathomed by test 2. However, just as
for the whole problem, subproblem 1 fails all fathoming tests.
These results are summarized in the solution tree shown below:
Example
Iteration 2.
With only one remaining subproblem, the next branching is from this node.
Examining its LP relaxation’s optimal solution, we see that this node reveals
6
that the branching variable is x2, because x2 = is the first integer-restricted
5
variable that has a noninteger value.
Adding one of the constraints x2 ≤ 1 or x2 ≥ 2 then creates the following two
new subproblems.
Example
Iteration 2.
Example
Iteration 2.
Because both solutions exist (feasible solutions) and have noninteger values
for integer-restricted variables, neither subproblem is fathomed. (Test 1 still is
not operational, since Z* = -∞ until the first incumbent is found.)
The solution tree at this point is given in figure below
Example
Iteration 3.
With two remaining subproblems (3 and 4) that were created simultaneously,
1 1
the one with the larger bound (subproblem 3, with 14 > 12 ) is selected for
6 6
the next branching.
5
Because x1 = has a noninteger value in the optimal solution for this
6
subproblem’s LP relaxation, x1 becomes the branching variable. (Note that x1
now is a recurring branching variable, since it also was chosen at iteration 1.)
This leads to the following new subproblems.
Example
Iteration 3.
Example
Iteration 3.
Subproblem 6 is immediately fathomed by test 2.
However, note that subproblem 5 also can be fathomed. Test 3 passes
because the optimal solution for its LP relaxation has integer values (x1 = 0, x2 =
1
0, x3 = 2) for all three integer-restricted variables. (It does not matter that x4 = ,
2
since x4 is not integer-restricted.)
This feasible solution for the original problem becomes our first incumbent:
Example
Iteration 3.
Using this Z* to reapply fathoming test 1 to the only other subproblem
1
(subproblem 4) is successful, because its bound 12 ≤ Z*.
6
This iteration has succeeded in fathoming subproblems in all three possible
ways. Furthermore, there now are no remaining subproblems, so the current
incumbent is optimal.
Example
Summary.
These results are summarized by the final solution tree given in figure below:
Exercise
Previous furniture company problem:
• A furniture company makes two kind of product, table and
cupboard. Both kind need two process to be produced: wood
cutting and assembly.
• A table needs 6 hours to finish cutting process and a cupboard
needs 5 hours. For assembly, a table needs 2 hours and a cupboard
needs 3 hours. In a week, the company has capacity of 30 hours for
cutting process and 12 hours for assembly.
• If the profit for a table is Rp 800.000/kg and Rp 700.000/kg for a
cupboard, how much table and cupboard need to be produced to
maximize the profit?
The End