Franklin Djeumou Fomeni, PhD
Postdoctoral Research Fellow
CIRRELT, Montreal, Canada
CIRRELT, Montreal, Canada
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.