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.
| Subject : | : | typdoc_1455 |
| Language of text | : | French |
| Topics | : | Non-linear optimisation, bi-level optimisation and yield management |
| Keywords | : | branch and bound ; sac à dos quadratique ; programmation semi définie |
| PDF version | : |  PDF version |
