[go: up one dir, main page]
Scribd
Upload
24 views29 pages

13,14-Integer Programming 9.3

This document discusses integer programming and the branch-and-bound method. [1] It explains that branch-and-bound finds the optimal integer programming solution by solving linear programming relaxations of subproblems. [2] The linear programming relaxation of a subproblem provides an upper bound on the optimal integer solution. [3] Branching on fractional variables partitions the feasible region into new subproblems until an optimal integer solution is found.

Uploaded by

CHRISTOPHER ABIMANYU
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
24 views29 pages

13,14-Integer Programming 9.3

This document discusses integer programming and the branch-and-bound method. [1] It explains that branch-and-bound finds the optimal integer programming solution by solving linear programming relaxations of subproblems. [2] The linear programming relaxation of a subproblem provides an upper bound on the optimal integer solution. [3] Branching on fractional variables partitions the feasible region into new subproblems until an optimal integer solution is found.

Uploaded by

CHRISTOPHER ABIMANYU
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 29

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

You might also like