The Quadratic Knapsack Problem (QKP) is an advanced form of the classical knapsack problem that incorporates quadratic terms into its objective function. This allows for modeling of inter-item dependencies, where the selection of one item may increase or decrease the total profit when combined with another. Originally introduced in the 19th century, the QKP remains a central challenge in operations research, combinatorial optimization, and computational complexity.
A special case, known as the 0–1 Quadratic Knapsack Problem (0–1 QKP), restricts each item to be either included (1) or excluded (0), forming one of the most studied NP-hard combinatorial optimization problems.
Formal Definition
Given n items, each with an individual profit pᵢ, pairwise profit Pᵢⱼ, and weight wᵢ, the goal is to determine which items to include in the knapsack to maximize total profit without exceeding its capacity W.
Formally: maximize∑i=1npixi+∑i=1n∑j=1,i≠jnPijxixj\text{maximize} \quad \sum_{i=1}^{n} p_i x_i + \sum_{i=1}^{n} \sum_{j=1, i \neq j}^{n} P_{ij} x_i x_jmaximizei=1∑npixi+i=1∑nj=1,i=j∑nPijxixj
subject to: ∑i=1nwixi≤W,xi∈{0,1} for i=1,…,n.\sum_{i=1}^{n} w_i x_i \leq W, \quad x_i \in \{0,1\} \text{ for } i = 1, …, n.i=1∑nwixi≤W,xi∈{0,1} for i=1,…,n.
Here, xᵢ is a binary decision variable representing whether item i is included. The quadratic term Pᵢⱼxᵢxⱼ captures the additional profit when both items are chosen.
Applications
The quadratic knapsack problem models a wide range of real-world optimization problems across several disciplines:
- Telecommunication: Site selection for satellite or cellular base stations to maximize traffic coverage.
- Transportation: Locating airports, railway hubs, and freight terminals to optimize connectivity.
- Computer Science: Problems in compiler design, VLSI circuit layout, and clique detection.
- Economics: Modeling investment portfolios and pricing strategies.
Historically, Witzgall discussed the QKP in the context of selecting satellite station sites to optimize global communication efficiency.
Computational Complexity
The QKP and its 0–1 variant are both NP-hard. The decision version (whether a profit of at least V can be achieved within capacity W) is NP-complete, meaning a proposed solution can be verified in polynomial time but no known algorithm can find the solution efficiently.
While exact algorithms exist for small instances, practical problems rely on heuristics and approximation methods due to the exponential growth in computational requirements.
Solution Methods
Because the QKP is nonlinear and combinatorial, several algorithmic approaches have been developed to obtain optimal or near-optimal solutions:
1. Brute-Force Search
Enumerates all possible subsets of items, computing total profit and weight for each.
- Complexity: O(2ⁿn²)
- Drawback: Impractical for large n due to exponential growth.
2. Linearization Methods
To simplify computation, quadratic terms are replaced with auxiliary linear variables and constraints.
- Standard Linearization: Introduces variables zᵢⱼ = xᵢxⱼ, creating a linear integer programming form.
- Glover’s Linearization: More efficient, using fewer auxiliary variables (n instead of n²) and constraints (2n instead of 3n²).
These methods transform the QKP into a mixed-integer linear program (MILP) solvable by commercial solvers like CPLEX or Gurobi.
Convex Quadratic Reformulation
A convex reformulation ensures that any local maximum is also the global maximum. By making the matrix P positive semi-definite (diagonally dominant), the objective becomes concave, allowing optimization using mixed-integer quadratic solvers.
The reformulated objective function is expressed as: pTx+xTPx+∑i=1n(∑j=1,j≠in∣Pij∣)(xi2−xi)p^T x + x^T P x + \sum_{i=1}^{n} \left( \sum_{j=1, j \neq i}^{n} |P_{ij}| \right) (x_i^2 – x_i)pTx+xTPx+i=1∑nj=1,j=i∑n∣Pij∣(xi2−xi)
This approach leverages the properties of convex optimization to improve computational efficiency.
Heuristic and Approximation Algorithms
Because exact solutions are costly, heuristics provide practical near-optimal solutions:
Greedy Heuristic Algorithm
Proposed by George Dantzig, this approach sorts items by value-to-weight ratio, including items with the highest contribution until capacity is reached. Subsequent pairwise swaps improve the solution iteratively.
- Complexity: O(2ⁿ) in the worst case.
- Advantage: Fast and effective for moderately sized problems.
Dynamic Programming Heuristics
Adaptations of dynamic programming can generate approximate lower bounds on optimal profit. Although pseudo-polynomial in time, they require significant memory and are more suitable for small-to-medium-scale problems.
Branch-and-Bound (Quadknap)
Caprara et al. introduced Quadknap, an exact branch-and-bound algorithm using Lagrangian relaxation to compute upper bounds efficiently. Subgradient optimization helps derive stable Lagrange multipliers, improving convergence.
Quadknap can handle up to 400 binary variables, outperforming earlier methods.
Dynamic Programming Algorithm
Define f(m, w) as the maximum profit using the first m items with total weight w. Then: f(m,w)={max[f(m−1,w),f(m−1,w−wm)+pm+∑i=1m−1Pimxi]if wm≤wf(m−1,w)otherwisef(m, w) = \begin{cases} \max \left[ f(m-1, w), f(m-1, w – w_m) + p_m + \sum_{i=1}^{m-1} P_{im}x_i \right] & \text{if } w_m \le w \\ f(m-1, w) & \text{otherwise} \end{cases}f(m,w)={max[f(m−1,w),f(m−1,w−wm)+pm+∑i=1m−1Pimxi]f(m−1,w)if wm≤wotherwise
- Time Complexity: O(Wn²)
- Space Complexity: O(Wn) in revised implementations
Though not guaranteed to reach the global optimum, this approach provides high-quality solutions.
Research Directions
Current research on the Quadratic Knapsack Problem explores:
- Efficient heuristics for large-scale real-world applications.
- Instance generation with predictable difficulty for benchmarking.
- Hybrid metaheuristics combining genetic algorithms, tabu search, and Lagrangian relaxation.
Most computational studies rely on randomly generated data, such as weights from uniform distributions in [1, 50] and values in [1, 100]. Researchers continue to refine methodologies for generating consistent and realistic test cases.
Conclusion
The Quadratic Knapsack Problem extends the classical knapsack framework into nonlinear optimization, capturing interdependencies among items. Though NP-hard, it remains a cornerstone in operations research and combinatorial optimization, with wide-ranging applications from network design to computational economics. Modern research focuses on scalable algorithms that balance solution accuracy with computational efficiency.
