09_Mixed Integer Programming

Question 1

MUB
Priority Rule

Branch and Bound

Answer 1

Maximum Upper Bound
- choose subproblem with highest objective function
- new upper bound z

Question 2

Shortcomings of MUB Rule

Branch and Bound

Answer 2

• The objective function value deteriorates as we introduce new constraints
• The search tree tends to grow horizontally (“breadth-first-search”)
• Since we gain information on the objective function values of the subproblems, we may adjust the upper bound z accordingly

Question 3

LIFO
Priority Rule

When selecting subproblem in Branch and Bound

Answer 3

• Last-In-First-Out
• select deepest subproblem of the tree
• if both subproblems have been introduced simultaneously then choose priority rule such as highest value

Question 4

Shortcomings of
LIFO

Branch and Bound

Answer 4

• The objective function value deteriorates as we introduce new constraints
• The search tree tends to grow vertically (“depth-first-search”)
• Notice how we made only little progress on the upper bound z

Question 5

Branching

Answer 5

• explore the solution space with subproblems of the integer program and determine a feasible solution.

Question 6

Bounding

Answer 6

• Pruning subproblems („branches“) to reduce the solution space using the lower bound.

Question 7

How to define lower bound when using MUB priority rule

Branch and Bound

Answer 7

• If you cannot find a feasible solution at the beginning, you can assume lower bound is 𝑧 = ∞
• If you can, use it! Here let’s use an arbitrary one

Question 8

Optimality Gap Delta

Answer 8

Quality of best-found feasible solution → Percentage deviation to best possible solution
∆= |𝐵𝑒𝑠𝑡 𝐵𝑜𝑢𝑛𝑑 − 𝐼𝑛𝑐𝑢𝑚𝑏𝑒𝑛𝑡 𝑂𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒|
𝐼𝑛𝑐𝑢𝑚𝑏𝑒𝑛𝑡 𝑂𝑏𝑗𝑒𝑐𝑡𝑖𝑣𝑒
▪ For a maximization problem: Incumbent Objective → Lower Bound (𝑧)(lb)

∆= 𝑧(up)−𝑧(lb) / 𝑧(lb)
▪ For a minimization problem: Incumbent Objective → Upper Bound (𝑧)(ub)
∆= 𝑧(ub) − 𝑧(lb) / 𝑧(ub)