Franklin Djeumou Fomeni, PhD

The quadratic knapsack problem (QKP)

The QKP is a particular kind of optimization problem that essentially amounts to maximizing a quadratic function of a set of binary variables, subject to a single linear side-constraint. Applications of the QKP include portfolio optimization, project selection, and the location of communications satellites, railway stations, freight handling terminals and airports.

An intriguing feature of the QKP is that it has both discrete and non-linear aspects. For this reason, it can be tackled in a variety of ways, for example by using linear, quadratic or semi-definite programming, or Lagrangian relaxation or decomposition. Good surveys of exact and heuristic algorithms for the QKP can be found in Kellerer et al. (2004) and Pisinger (2007).

At present, the most competitive exact solution method for the QKP is one based on Lagrangian relaxation, due to Caprara et al. (1999). It is capable of solving instances with up to around 400 variables to proven optimality. Some enhancements to this algorithm were recently proposed by Pisinger et al. (2007), which enable even larger instances to be solved.

The search for a much efficient solution algorithm for the QKP is still a challenge.

• An exact solution code can be obtained from David Pisinger's academic webpage at DTU. This code is based on the algorithm developed by the late Alberto Caprara et al. (1999).
• An effective deterministic heuristic algorithm was developed by myself and Adam Letchford. An implementable version of the C code can be obtained here. This code may not be the most efficient version. I therefore decline any liability for its use.