Les algorithmes Branch-and-Bound (B&B) font partie des méthodes exactes pour la résolution de problèmes d’optimisation combinatoire. Les calculs induits par un algorithme B&B sont extrêmement couteux surtout lorsque des instances de grande tailles sont considérées. Un algorithme B&B peut être vu comme une exploration implicite d’un espace représenté sous la forme d’un arbre qui a pour spécificité d’être hautement irrégulier. Pour accélérer l’exploration de cet espace, les calculs parallèles et distribués à très large échelle sont souvent utilisés. Cependant, atteindre des performances parallèles optimales est un objectif difficile et jalonné de plusieurs défis, qui découlent essentiellement de deux facteurs: (i) l’irrégularité des calculs inhérents à l’arbre B&B et (ii) l’hétérogénéité inhérente aux environnements de calcul large échelle. Dans cette thèse, nous nous intéressons spécifiquement à la résolution de ces deux défis. Nous nous concentrons sur la conception d’algorithmes distribués pour l’équilibrage de charge afin de garantir qu’aucune entité de calcul n’est surchargée ou sous-utilisée. Nous montrons comment résoudre l’irrégularité des calculs sur différents type d’environnements, et nous comparons les approches proposées par rapport aux approches de références existantes. En particulier, nous proposons un ensemble de protocoles spécifiques à des contextes homogènes, hétérogène en terme de puissance de calcul (muti-coeurs, CPU et GPU), et hétérogènes en terme de qualité des lien réseaux. Nous montrons à chaque fois la supériorité de nos protocoles à travers des études expérimentales extensives et rigoureuses. / Branch and Bound (B&B) algorithms are exact methods used to solve combinatorial optimization problems (COPs). The computation process of B&B is extremely time-intensive when solving large problem instances since the algorithm must explore a very large space which can be viewed as a highly irregular tree. Consequently, B&B algorithms are usually parallelized on large scale distributed computing environments in order to speedup their execution time. Large scale distributed computing environments, such as Grids and Clouds, can provide a huge amount of computing resources so that very large B&B instances can be tackled. However achieving high performance is very challenging mainly because of (i) the irregular characteristics of B&B workload and (ii) the heterogeneity exposed by large scale computing environments. This thesis addresses and deals with the above issues in order to design high performance parallel B&B on large scale heterogeneous computing environments. We focus on dynamic load balancing techniques which are to guarantee that no computing resources are underloaded or overloaded during execution time. We also show how to tackle the irregularity of B&B while running on different computing environments, and consider to compare our proposed solutions with the state-of-the-art algorithms. In particular, we propose several dynamic load balancing algorithms for homogeneous, node-heterogeneous and link-heterogeneous computing platforms. In each context, our approach is shown to perform much better than the state-of-the-art approaches.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.

Dans ces travaux, nous présentons des méthodes d'optimisation théoriques et numériques pour la conception optimale de circuits magnétiques pour propulseurs à effet Hall. Ces problèmes de conception sont des problèmes inverses très difficiles à résoudre que nous formulons sous forme de problèmes d'optimisation topologique. Les problèmes resultant sont non convexes avec des contraintes aux équations différentielles de Maxwell. Au cours de ces travaux, des approches originales ont été proposées afin de résoudre efficacement ces problèmes d'optimisation topologique. L'approche de densité de matériaux SIMP (Solid Isotropic Material with Penalization) qui est une variante de la méthode d'homogénéisation a été privilégiées. De plus, les travaux de ma thèse ont permis la mise en place de codes d'optimisation dénommé ATOP (Algorithm To Optimize Propulsion) utilisant en parallèle les logiciels de calculs scientifiques Matlab et d'élément finis FEMM (Finite Element Method Magnetics). Dans ATOP, nous utilisant à la fois des algorithmes d'optimisation locale de type descente basés sur une analyse de la sensibilité du problème et des algorithmes d'optimisation globale principalement de type Branch and Bound basés sur l'Arithmétique des Intervals. ATOP permettra d'optimiser à la fois la forme topologique des circuits magnétiques mais aussi le temps et le coût de production de nouvelles génération de propulseurs électriques. / In this work, we present theoretical and numerical optimization method for designing magnetic circuits for Hall effect thrusters. These design problems are very difficult inverse ones that we formulate under the form of topology optimization problems. Then, the obtained problems are non convex subject to Maxwell equations like constraints. Some original approaches have been proposed to solve efficiently these topology optimization problems. These approaches are based on the material density model called SIMP approach (Solid Isotropic Material with Penalization) which is a variante of the homogenization method. The results in my thesis allowed to provide optimization source code named ATOP (Algorithm To Optimize Propulsion) unsung in parallel two scientific computing softwares namely Matlab and FEMM (Finite Element Method Magnetics). In ATOP, we use both local optimization algorithms based on sensitivity analysis of the design problem; and global optimization algorithms mainly of type Branch and Bound based on Interval Arithmetic analysis. ATOP will help to optimize both the topological shape of the magnetic circuits and the time and cost of production (design process) of new generations of electrical thrusters.