Integer Programming
Dedy Suryadi
Parahyangan Catholic University
2020
1
For educational purpose only.
Source: Wayne Winston, Operations Research Applications and Algorithms 4th. Edition, 2003
2
Branch-and-Bound
• Branch-and-Bound method finds the optimal
solution to the IP by efficiently enumerating
the points in a subproblem’s feasible region.
3
About LP Relaxation
If we solve the LP
relaxation of a pure IP
and obtain an optimal
solution where all
variables are integers,
then it is also optimal for
the IP.
4
Ex.9: Branch-and-Bound Method
5
Subproblem 1
• Branch-and-
Bound method
begins by solving
the LP relaxation
of the IP.
• We call the LP
relaxation
subproblem 1.
• The solution of
subproblem 1:
6
Review: Finding Optimal Solution
(Graphically)
Point = (0,4)
z = 8(0) + 5(4) = 20
20 = 8x1 + 5x2
* More than 2 variables:
Use Simplex algorithm
7
Upper Bound
• We know that:
• The z-value obtained from the
subproblem 1 (LP relaxation)
becomes the upper bound.
→ upper bound = z = 165/4
8
Partition
• Next, we partition the feasible region of the
previous subproblem, because it has not
produced an IP feasible solution yet.
• We arbitrarily choose a variable that is fractional
in the previous subproblem.
9
Partition: Subproblem 2 & 3
• The solution of subproblem 1:
15/4
0 1 2 3 4 x1
• We branch on x1 to create:
10
Subproblem 2
Optimal solution
(for Subproblem 2):
11
Tree
• Our accomplishments so
far are summarized in a
tree.
• Each subproblem is a
node.
• t indicates the
chronological order in
which subproblems are
solved.
12
Partition: Subproblem 4 & 5
• The solution of Subproblem 2:
• We obtain:
• We have subproblem 3, 4, 5 unsolved.
→ Using LIFO rule, we arbitrarily choose subproblem 4.
13
Subproblem 4
14
Subproblem 4
No solution
(for Subproblem 4):
Infeasible
15
Subproblem 4: Fathomed
• There is no use
to branch
subproblem 4 any
further.
• So, the node is
fathomed.
• Using LIFO rule,
next we solve
subproblem 5 16
Subproblem 5
17
Subproblem 5
Optimal solution
(for Subproblem 5):
18
Partition: Subproblem 6 & 7
• The solution of Subproblem 5:
• We branch on x1=40/9
(from subproblem 5).
19
Subproblem 7
20
Subproblem 7
Optimal solution
(for Subproblem 7):
21
Subproblem 7:
Candidate Solution
• Subproblem 7
becomes candidate
solution, with z=37.
• The optimal z-value
for the IP
must be >= 37.
• Thus now LB=37.
22
Subproblem 6
Optimal solution
(for Subproblem 6):
23
Subproblem 6:
Candidate Solution
• Subproblem 7 is
fathomed.
• Subproblem 6
becomes a
candidate solution.
• The new LB = 40.
• Next, we solve
subproblem 3.
24
Subproblem 3
Optimal solution
(for Subproblem 3):
25
Subproblem 3: Fathomed
• Subproblem 3 is
fathomed because it
cannot yield the
optimal solution to
the IP.
• Thus, the optimal
solution to the IP is
subproblem 6.
26
Do We Need to Check (2,2)? Why?
27
Simplex & Dual Simplex
28
Branching Methods
• There are 2 methods in branching:
1. Backtracking (LIFO) → leading us down quickly
to find a candidate solution, then backtrack our
way back to the top of the other side.
2. Jumptracking → solving all subproblems
created by the branching, then it branches
again on the node with the best z-value.
29
