Sbihi, Abdelkader, CEntre de Recherche en Mathématiques, Statistique et Économie Mathématique (CERMSEM), Université Paris 1 Panthéon-Sorbonne (UP1)-Centre National de la Recherche Scientifique (CNRS), Laboratoire de Recherche en Informatique d'Amiens (LaRIA), Université de Picardie Jules Verne (UPJV)-Centre National de la Recherche Scientifique (CNRS), Université Panthéon-Sorbonne - Paris I, and Mhand Hifi(mhand.hifi@u-picardie.fr)
Cette thèse a été préparée au sein du CERMSEM (Centre de Recherches en Mathématiques, Statistiques et Economie Mathématique) UMR-CNRS 8095, et ausein de l'équipe Optimisation et Recherche Opérationnelle; The thesis is in the field of the particular field of operations research and combinatorial optimisation that is the modeling and algorithmic resolution. In this thesis we propose to study twoparticular NP-Hard variant problems of the binary knapsack type. More precisely, we treat theKnapsack Sharing Problem namely KSP and the Mutiple Choice Multidimensional KnapsackProblem namely MMKP. The first part of this dissertation is concerning to develop approxiamatealgorithms for the two evoked variants of the 01 knapsask problem. The second part isparticularly concerning with the exact resolution of the MMKP. The exact approach which wepropose is of branch-and bound type which : (i) computes of lower and upper bounds and (ii)develops a son-brother double node branches with a best first startegy of exploration.Indeed, the first part gets the study of the two problems KSP and MMKP. We are interestedto develop approximate algorithms based upon local search strategies. First and concerning theKSP, we propose a first version of an approximate algorithm based upon tabu search strategy.Second, we enhance this version by combining the intensification of the search in the space ofsolutions and the diversifiaction of the obtained solution. Experimental results shows the fastnessofthe first version and the effectiveness and the efficiency of the second one. Next, we proposetwo iterative local search methods for the MMKP. The first one is an heuristic based guidedlocal search end the second is a heuristic that we call a reactive local search approach with someimproving degrading and debloking strategies of the solution based local swapping search.In the second part of the dissertation, we propose an optimal method based branch-and-bound forsolving the MMKP. First, we propose to transform the MMKP into an MMKPaux problem whichis a Multiple-Choice Knapsack Problem MCKP.We compute an upper bound for MMKPaux andwe establish the theoritical result for which an upper bound for MMKPaux is also an upper boundfor MMKP. After, we deal with the computing of lower and upper bounds which are necessaryto reduce the space search in a branch-and-bound approach. Add to this, the resolution stronglydepends on the density and the size of the treated instances. The experimental study showsthe the efficiency of the proposed algorithm which is able tos solve different groups of instancesof small and medium sizes. Finally, we explain the limits of the branch-and-bound developedalgorithm which are because of the the complexity of the studied model.; La thèse se situe dans le domaine de l'optimisation combinatoire, en particulier celui de lamodélisation et de la résolution algorithmique. Dans cette thèse, nous étudions deux variantesNP-difficiles de problèmes de type sac-à-dos. Plus précisément, nous traitons le problème dela distribution équitable (le Knapsack Sharing Problem : KSP) et le problème du sac-à-dosgénéralisé à choix multiple (le Multiple-choice Multidimensional Knapasck Problem : MMKP).Dans la première partie de cette thèse, nous nous intéressons au développement d'algorithmesapprochés pour les deux variantes évoquées du problème de type sac-à-dos. La deuxième partietraite essentiellement de la résolution exacte du problème du sac-à-dos généralisé à choix multiple.L'approche exacte que nous proposons est de type séparation et évaluation s'appuyantprincipalement sur : (i) le calcul des bornes inférieure et supérieure et (ii) l'utilisation de lastratégie par le meilleur d'abord en développant des branches à double noeuds fils et frère.La première partie porte sur l'étude et la résolution approchée des deux problèmes KSP etMMKP. Concernant le problème de la distribution équitable, nous proposons dans un premiertemps, une première version de l'algorithme exploitant certaines caractéristiques de larecherche tabou. Dans un deuxième temps, nous développons une deuxième version de l'algorithme dont l'idée principale consiste à tenter de combiner l'intensification de la recherche dans l'espace des solutions et la diversification de la solution obtenue. Nous soulignons la rapiditéde la première version et l'efficacité de la deuxième. Ensuite nous nous intéressons au problèmede sac-à-dos généralisé à choix multiple. Nous proposons deux heuristiques de recherche localeitérative. Le premier algorithme s'appuie sur une “recherche guidée”. Le deuxième algorithmeest une recherche locale que nous appelons réactive avec stratégies de déblocage et de dégradtion améliorantes de la solution et basées sur l'inter-change local.Dans la deuxième partie de cette thèse, nous proposons une méthode de résolution exacte de type séparation et évaluation pour le problème du sac-à-dos généralisé à choix multiple. D'une part, nous nous proposons la réduction du problème initial au problème auxiliaire MMKPaux qui n'est autre que le problème de sac-à-dos à choix multiple MCKP. Nous calculons une borne supérieure pour le MMKPaux et nous établissons le résultat théorique pour lequel une borne supérieure pour le MMKPaux est une borne supérieure pour le MMKP. D'autre part, nous proposons le calcul d'une borne supérieure ainsi qu'une borne inférieure de départ pour le problème étudié qui sont nécessaires pour la réduction de l'espace de recherche. L'étude expérimentale montre l'efficacité de la méthode proposée sur différents groupes d'instances de petite et moyenne taille.Nous expliquons enfin pourquoi cet algorithme exact atteint ses limites de résolution, dˆuesprincipalement à la complexité intrinsèque du modèle étudié. D'autant la résolution dépend dela taille et la densité des instances traitées.