Recherche évolutive adaptative faisable et non faisable pour le problème du sac à dos avec forfeits

Résumé Le problème du sac à dos (KP) avec forfeits est un KP généralisé qui vise à sélectionner certains articles, parmi un ensemble d'articles candidats, afin de maximiser une fonction de profit sans dépasser la capacité du sac à dos. De plus, un coût de forfeit est encouru et déduit de la fonction de profit lorsque deux articles incompatibles sont placés dans le sac à dos. Ce problème est un modèle pertinent pour un certain nombre d'applications et est cependant difficile sur le plan computationnel. Nous présentons une méthode heuristique hybride pour aborder ce problème qui combine la recherche évolutive avec la recherche adaptative faisable et non faisable pour trouver des solutions de haute qualité. Une technique de rationalisation est conçue pour accélérer l'évaluation des solutions candidates, ce qui augmente significativement l'efficacité computationnelle de l'algorithme. Nous évaluons l'algorithme sur 120 instances de test et démontrons sa domination par rapport aux meilleures approches de la littérature. En particulier, nous montrons 94 bornes inférieures améliorées. Nous examinons les composants algorithmiques essentiels pour comprendre leurs rôles.