5. Branch&Bound algorithm

Question 1

Initialization

Answer 1

Z* = −∞
bounding step, fathoming step, and optimality test
If not fathomed -> subproblem
-> iteration

Question 2

Iteration

Answer 2

1 Branching
2 Bounding
3 Fathoming

Question 3

1. Branching

Answer 3

• select the one unfathomed subproblem that was created most recently or with the largest bound (smallest if min problem)
• create two new subproblems by fixing the next variable either 0 or 1

Question 4

2. Bounding

Answer 4

• applying the simplex method to its LP relaxation
• rounding down the value of Z

Question 5

Fathoming

Answer 5

Test 1: Z ≤ Z∗ (or ≥ Z∗ if min problem)
Test 2: no feasible solutions
Test 3: optimal solution for its LP relaxation is integer
If this solution is better than the incumbent, it becomes the new incumbent -> test 1 is reapplied to all unfathomed
subproblems

Question 6

Optimality test

Answer 6

Stop when there are no remaining subproblems; the current incumbent is optimal
Otherwise, return to perform another iteration.

Question 7

B&B changes for MIP

Answer 7

• consider only integer-restricted variables having noninteger value in the optimal solution for the LP relaxation of the current subproblem
• two ranges of value are specified and two new
  subproblems created (xj ≤ rounded down and xj ≥ rounded up)
• value of Z has not to be rounded down
• test requires only that the integer-restricted variables be integer in the optimal solution for the subproblem’s LP relaxation

Question 8

Node selection rules

Answer 8

1 Depth-first search
2 Breadth-first search
3 Best-bound search
4 Combinations of the previous ones

Question 9

Depth-first search

Answer 9

select a child of the preceding node after branching and backtracks as few nodes as possible after pruning a node

Question 10

Breadth-first search

Answer 10

select nodes that are closest to the top of the tree

Question 11

Best-bound search:

Answer 11

select the node with the best lower bound

Question 12

Heuristic choice of the rule

Answer 12

• Depth-first search: obtain solutions quickly risk that
  solution quality suffers
• Breath-first search avoids this risk and works in parallel on all branches of the tree, but slow to obtain feasible solutions
• Best-bound search: minimizes number of nodes treated to prove optimality
• Combination of rules: good compromise

Question 13

Node selection rule

Answer 13

1 Lexicographical order
2 Most fractional: select the variable whose fractional part is
farthest from being integer
3 Sophisticated rules: detecting the impact of the branching variable on the lower bound values

Question 14

Duality gap

Answer 14

when enumeration is unfinished, the duality gap measures the maximum relative deviation from optimality of the best feasible solution found

Question 15

Reformulation

Answer 15

• The set of feasible solutions X is not changed
• The linear relaxation is a smaller set
• Using this tightened formulation of X, we can solve the PIP problem by B&B only by analyzing the root node

Question 16

Convex hull

Answer 16

is the tightest valid formulation or valid LP relaxation for X
- All extreme points of conv(X) belong to X, all extreme optimal solutions to the LR belong to X
- solving the LR → extreme optimal solution to LR (which is also an optimal solution to MIP)

Question 17

Valid inequalities

Answer 17

A VI for the feasible set X of MIP is a constraint or inequality satisfied by all points in X

Question 18

Facet-defining valid inequality

Answer 18

… for X is a valid inequality that is necessary in a description of the polyhedron conv(X)

Question 19

Extended reformulation

Answer 19

An extended reformulation for the feasible set X of a MIP is a formulation (defined by linear constraints) involving new (and usually more) variables.