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 adds its exact quadratic value as a constant and replaces remaining profits by 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.
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
Articles by others on the same topic
Branch and Bound is an algorithm design paradigm used primarily for solving optimization problems, particularly in discrete and combinatorial optimization. The method is applicable to problems like the traveling salesman problem, the knapsack problem, and many others where the goal is to find the optimal solution among a set of feasible solutions. ### Key Concepts: 1. **Branching**: This step involves dividing the problem into smaller subproblems (branches).