= 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.
Back to article page
