Contribution à la résolution des problèmes d'optimisation combinatoire : cas du problème des k-clusters dans un graphe biparti et du problème de sac à dos quadratique

Since long time, the scientific world has sought for modeling, simplification and resolution of combinatorial optimization problems, because of these problems are most interest for the scientific and the industrial world and for the fields of operational research and computer science. The objective of this thesis is to solve the difficult combinatorial optimization problems using approximate resolution methods. And, we were interested on two important problems that find several significant applications in real world. The first part of the thesis is devoted to the K-clusters in a bipartite graph that has been applied in the field of telecommunication. The second part of the thesis addresses to the quadratic knapsack problem that can be used to accommodate a wide range of practical applications in numerous fields. On the other hand, these problems are highly combinatorial and difficult to solve from computational perspective. The K-clustering minimum bi-clique completion problem (K - CmBCP) was presented in the latest date and it is very significant in real world and it has been applied to several real applications such as aggregation of multicast sessions. Since telecommunication network cannot manage many multicast sessions at the same time, it is hence necessary to group the sessions into a limited number of clusters. We note that, the hybrid resolution methods can combine several approximate resolution methods or optimal resolution and approximate resolution and which generally use decomposition techniques of the initial problem to allow hybridation. In this thesis, we propose two hybrid resolution methods: A first hybrid method for the problem of K-clusters in a bipartite graph that combines a neighborhood search and a complementary algorithm. A second hybrid method for the quadratic knapsack problem which combines a large neighborhood search with a variable reduction / fixing method. The proposed algorithm is capable of solving the small, large and very large size instances of the QKP that cannot be solved by Cplex solver or by other methodsLes problèmes d'optimisation combinatoire sont d'un grand intérêt à la fois pour le monde scientifique et le monde industriel. Les enjeux scientifiques, économiques, environnementaux et sociaux sont très nombreux et très importants. C'est pour cela que la communauté scientifique mondiale recherche depuis longtemps des méthodes de modélisation, de simplification et de résolution de ces problèmes. Parmi les problèmes combinatoires les plus connus se trouvent les problèmes de sac à dos et les problèmes liés aux décompositions des graphes. Nous nous sommes intéressés dans cette thèse à deux problèmes importants : - Le problème de regroupement dans un graphe biparti ; - Le problème de sac à dos quadratique. Le problème de regroupement dans un graphe biparti a de nombreuses applications dans le domaine des télécommunications. Il a également un grand intérêt théorique dans la modélisation, la décomposition et la résolution de plusieurs autres problèmes combinatoires. Le problème de sac à dos quadratique a un large champ d'applications théoriques et pratiques dans nombreux domaines. Il est très utile dans la modélisation et la résolution dans un contexte de gestion des exclusions par exemple. Ces deux problèmes sont hautement combinatoires et sont très difficiles à résoudre d'une manière optimale d'un point de vue informatique. La résolution de ce type de problèmes peut se faire de deux manières : - La résolution optimale, dite également exacte, qui s’appuie sur des modélisations et des méthodes mathématiques puissantes dont l'objectif est d'identifier une solution optimale du problème traité. - La résolution approchée, qui s'appuie principalement sur des algorithmes capables d'approcher la solution optimale du problème traité mais sans garantir l'optimalité du résultat. Les méthodes approchées sont les plus utilisées par les informaticiens dans la résolution des problèmes issus de l'industrie et des services car ces méthodes permettent de résoudre des problèmes de grande taille et de répondre aux exigences fonctionnelles des donneurs d'ordres. Il existe aussi des méthodes de résolution hydrides qui peuvent combiner plusieurs méthodes de résolution approchées ou exactes et qui utilisent généralement des techniques de décomposition du problème initial pour permettre l'hybridation. C'est dans ce sens que s'oriente cette thèse. Nous proposons dans cette thèse deux méthodes de résolution hydriques : - Une première méthode hydride pour le problème de regroupement dans un graphe biparti qui combine une recherche par voisinage et un algorithme approché complémentaire. - Une deuxième méthode hybride pour le problème du sac à dos quadratique qui combine une recherche par voisinage et une méthode de réduction/fix-ation des variable