Management Science:
Operations Research(OR)
Chapter 4
Integer Programming
(4.3)
25-09-09 Lecture 1
4.3 Solution Methods for IP
Cutting plane methods
Branch-and-Bound Methods
Heuristic Methods
25-09-09 Lecture 2
4.3.2 Branch-and-Bound Methods
These methods are very flexible & are
applicable to AILP & MILPs.
Idea: Starting with the LP relaxation,
subdivide the problem into subproblems,
whose union includes all integer solutions
that are not worse than the best known
integer solution.
25-09-09 Lecture 3
For instance, if presently y3 = 5.2, we
subdivide the problem (the “parent”) by
adding the constraint y3 ≤ 5 & y3 ≥ 6,
respectively (thus creating “children”).
25-09-09 Lecture 4
Example: P: Max z = 400x1 + 900x2
s.t. 9x1 + 7x2 56
7x1 + 20x2 70
x1, x2 ≥ 0 and
integer.
25-09-09 Lecture 5
x1 = 4.809
x2 = 1.817
z = 3,558.90
x1 4 x1 5
x1 = 4.000 x1 = 5.000
x2 = 2.100 x2 = 1.571
z = 3,490 z = 3,413.90
x2 2 x2 3 x2 1 x2 2
x1 = 4.000 * x1 = 1.428 x1 = 5.444 NO
x2 = 2.000 OPTIMAL x2 = 3.000 x2 = 1.000 FEASIBLE
z = 3,400 z = 3,271.20 z = 3,077.60 SOLUTION
25-09-09 Lecture 6
Example:
Max z = 5y1 + 9y2
s.t. 5y1 + 11y2 94 Constraint I
10y1 + 6y2 87 Constraint II
y1 , y2 ≥ 0 and integer.
25-09-09 Lecture 7
25-09-09 Lecture 8
Solution Tree
25-09-09 Lecture 9
Each node of the solution tree represents one linear
program.
The constraints at a node are all original constraints
plus all additional constraints between the root of
the tree & the node in question.
As we move down the tree, the problems get to be
more constrained & thus their objective values
cannot improve.
25-09-09 Lecture 10
Alternative Solution
25-09-09 Lecture 11
