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.
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).