Exact solution of the Quadratic Knapsack Problem

The Quadratic Knapsack Problem (QKP) calls for maximizing a quadratic objec tive function subject to a knapsack constraint, where all coefficients are assumed to be nonnegative and all variables are binary. The problem has app lications in location and hydrology, and generalizes the problem of checkin g whether a graph contains a clique of a given size. We propose an exact br anch-and-bound algorithm for QKP, where upper bounds are computed by consid ering a Lagrangian relaxation that is solvable through a number of (continu ous) knapsack problems. Suboptimal Lagrangian multipliers are derived by us ing subgradient optimization and provide a convenient reformulation of the problem. We also discuss the relationship between our relaxation and other relaxations presented in the literature. Heuristics, reductions, and branch ing schemes are finally described. In particular, the processing of each no de of the branching tree is quite fast: We do not update the Lagrangian mul tipliers, and use suitable data structures to compute an upper bound in lin ear expected time in the number of variables. We report exact solution of i nstances with up to 400 binary variables, i.e., significantly larger than t hose solvable by the previous approaches. The key point of this improvement is that the upper bounds we obtain are typically within 1% of the optimum, but can still be derived effectively. We also show that our algorithm is c apable of solving reasonable-size Max Clique instances from the literature.