Branch and bound

A branch-and-bound search partitions a feasible set, maintains a feasible incumbent, and prunes subproblems using bounds that cannot improve that incumbent. For a quadratic knapsack problem, fixing a selected set $S$ adds its exact quadratic value as a constant and replaces remaining profits by $v_i+2{\sum }_{j\in S}{p}_{ij}$ under the ordered-pair convention. Residual fractional row bounds for quadratic knapsack and a Lagrangian knapsack bound can then be recomputed. Worst-case search remains exponential.

If a minimum one-tree is not a tour, some vertex has degree greater than two, since there are equally many edges and vertices. Every tour must omit at least one of its incident selected edges. Partition tours by the first omitted edge in an ordered list, forcing all preceding listed edges and forbidding that edge. These disjoint children cover all tours. Recompute the constrained one-tree lower bound in each child and compare it with the incumbent solution to prune.

An incumbent solution is the best feasible solution found so far by an optimization search. Its objective value is an upper bound on a minimization optimum and a lower bound on a maximization optimum; bounds on unexplored subproblems can be compared with it to prune the search.

// Target: combinatorics.bigb

For minimization, best-bound search expands the active branch and bound node with smallest lower bound. A feasible completed assignment supplies an incumbent upper bound. Nodes with lower bound at least that incumbent can be discarded when only one optimum is needed. Search ends with an optimality certificate when no active node can improve the incumbent.

// Target: combinatorics.bigb