Le problème du sac à dos quadratique avec contrainte de cardinalité (E-kQKP) consiste à maximiser une fonction quadratique à coefficients positifs soumise à deux contraintes linéaires, l'une portant sur la capacité du sac et l'autre imposant le nombre d'objets à mettre dans le sac. Ce problème NP-difficile est une extension du problème du sac à dos quadratique dans lequel le nombre d'objets à mettre dans le sac est fixé à k.
Plusieurs approches exactes, basées sur une évaluation et séparation progressive, pour ce problème seront proposées et de nombreux résultats expérimentaux seront présentés afin de comparer ces différentes approches:
- résolution directe par un solveur (Cplex) en utilisant une relaxation linéaire ou une relaxation quadratique convexe,
- convexifications (Reformulation Quadratique Convexe (QCR) et une nouvelle variante permettant d'obtenir de meilleurs majorants à la racine de l'arbre de recherche) puis résolution du problème convexifié par un solveur,
- résolution par le solveur non linéaire BiqCrunch en intégrant une algorithmique spécifique, notamment pour la détermination de solutions réalisables et une approche basée sur la programmation semi-définie pour l'obtention des majorants,
- et résolution par un branch and bound spécifique intégrant différentes stratégies de branchement, des heuristiques dédiées, des inégalités valides lors de la résolution de la relaxation semi-définie (via csdp et conic bundle) en chaque noeud de l'arbre de recherche.