Using a mixed integer programming tool for solving the 0-1 quadratic knapsack problem

Alain Billionnet*, CEDRIC - IIE
Eric Soutif, CERMSEM

Résumé. Nous nous intéressons au problème du sac-à-dos quadratique en variables 0-1 (QKP). Le but de ce papier est de montrer qu'il est possible de résoudre efficacement (QKP) - en termes de temps de calcul et de taille de problèmes - en utilisant une formulation linéaire du problème. Pour un problème de n variables, la technique de linéarisation que nous proposons présente l'avantage de n'ajouter que (n - 1) variables réelles et 2(n - 1) contraintes. Nous présentons des résultats numériques concernant des instances générées aléatoirement ainsi que sur des problèmes issus d'applications et ayant une structure particulière. Cette méthode permet de résoudre des instances aléatoires de (QKP) comportant jusqu'à 140 variables.
Mots-clés : Programmation en nombres entiers, sac-à-dos quadratique en 0-1, linéarisation, résolution exacte, résultats numériques.

Abstract. In this paper we will consider the 0-1 Quadratic Knapsack Problem (QKP). Our purpose is to show that using a linear reformulation of this problem and a standard mixed integer programming tool, it is possible to solve efficiently (QKP) in terms of computation time and the size of problems considered, in comparison with existing methods. Considering a problem involving n variables, the linearization technique we propose has the advantage of adding only (n-1) real variables and 2(n-1) constraints. We present extensive computational results on randomly generated instances and on structured problems coming from applications. For example, the method allows us to solve randomly generated (QKP) instances exactly with up to 140 variables.
Keywords : Integer programming, 0-1 quadratic knapsack, lineariation, branch and bound, experiments.

JEL Classification : C44, C61, C63.

*CEDRIC - IIE, 18 allée Jean Rostand, 91025 Evry Cedex, France.