5 - Branch&Bound algorithm

Question 1

Overview of different types of programs

Answer 1

Question 2

Enumeration tree (or solution tree)

defintion

Answer 2

The enumeration tree (or solution tree) is the tree representing the branching into subproblems with branches (arcs) connecting one node to two subsequent nodes corresponding to the subproblems. This tree continues growing branches iteration by iteration. The variable used to do this branching at any iteration by assigning values to the variable is the branching variable.

Question 3

Branch-and-Bound algorithm for binary programs

Answer 3

Question 4

Branch-and-Bound algorithm for mixed integer programs

Changes compared to B&B for binary programs

Answer 4

Question 5

Branch-and-Bound algorithm for MIPs

general

Answer 5

Question 6

Branch-and-Bound algorithm for MIPs

general

Answer 6

Question 7

Node selection rules

Answer 7

1 Depth-first search: select a child of the preceding node after branching, and backtracks (moves back in the enumeration tree to select the next node) as few nodes as possible after pruning a node

2 Breadth-first search: select nodes that are closest to the top of the tree

3 Best-bound search: select the node with the best (lowest if min, highest if max) lower bound

4 Combinations of the previous ones, such as:
- Breadth-first search for a certain number of nodes followed by depth-first search
- Depth-first search as long as branching is performed, and then best-bound after pruning a node

Question 8

Heuristic choice of the node selection rule

Answer 8

1 Depth-first search: obtain solutions quickly (more branching constraints), risk that solution quality suffers

2 Breath-first search avoids this risk and works in parallel on all branches of the tree, but slow to obtain feasible solutions

3 Best-bound search: minimizes number of nodes treated to prove optimality

4 Combination of rules: good compromise

Question 9

Branching rules

Answer 9

1 Lexicographical order

2 Most fractional (close to one-half): select the variable whose fractional part is
farthest from being integer (ex. 3.6 more fractional than 2.3)

3 Sophisticated rules detecting the impact of the branching variable on the lower bound values

Branching priority: branch first on variables with major impact on the solution quality

Question 10

Convex hull

Answer 10

Convex hull is the tightest valid formulation or valid LP relaxation for X
(conv(X) ⊆ PX , for any formulation PX of X)

Question 11

Valid inequalities

Answer 11

Question 12

Facet-defining valid inequalities

Answer 12

Question 13

A priori reformulation

Answer 13

Question 14

Reformulation

Answer 14

Question 15

Extended Reformulation

Answer 15