Branch-And-Bound Bound

Problem

Combine bounds in a branch-and-bound node for a minimization problem.

Return [best, prune] where best = min(parent_bound, min(child_bounds)) and prune is True when best is at least the incumbent. An empty child list leaves the parent bound unchanged.

Hint

A node is pruned when no solution under it can beat the incumbent.

Test cases

case 1

in: [5,6,[4,7]]

expected: [4,false]

case 2

in: [5,4,[5.5,6]]

expected: [5,true]

case 3

in: [3,10,[]]

expected: [3,false]

case 4

in: [2,2,[1]]

expected: [1,false]

Starter codePython

def branch_and_bound_bound(parent_bound, incumbent, child_bounds):
    # Returns [best, prune]
    # Your code here
    pass

4 test cases · run your code against them in the editor