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.

Au cours de leur durée de vie, les bâtiments importants sont susceptibles d’être soumis à des charges accidentelles, telles que des explosions ou des impacts. Evaluer leur stabilité vis-à-vis de charges traditionnelles statiques et sismiques ne suffit pas. Leurs performances structurelles liées à des scénarios d’effondrement progressif doivent également être examinées.L’étude de l’effondrement progressif est un problème dynamique. Malheureusement, les expériences sur le comportement des structures de génie civil dans des conditions dynamiques sont rares car difficiles à réaliser. Dans cette étude, des sous-assemblages poteaux-poutres en béton armé ont été testés sous chargement dynamique. Le chargement a consisté à placer une masse importante jouant le rôle de « charge morte » sur la colonne centrale d’un sous-assemblage simulant la liaison de 3 poteaux avec 2 poutres. Une pièce fusible jouant le rôle de support sous la colonne centrale est brutalement déverrouillée pour simuler la perte de portance soudaine de cette colonne. Le comportement dynamique et les dommages locaux causés à la structure ont été mesurés et étudiés. Le bâti de chargement et les dispositifs de support ont été conçus spécialement pour cet essai. La charge morte supérieure peut être modifiée et appliquées à différents spécimens. Les supports des colonnes latérales ont une rigidité horizontale contrôlée et sont conçus pour limiter la rotation de ces mêmes colonnes. Ainsi, les conditions aux limites des essais réalisés sont supposées être représentatives de situations réalistes. Au cours des essais, un laser a été installé sous la colonne centrale pour mesurer la vitesse de chute. Une caméra numérique rapide a été utilisée pour visualiser l'ensemble du processus de ruine du sous-assemblage. Les images obtenues de la caméra ont été traitées par une technique de DIC (Digital Image Correlation) afin d’obtenir le champs de déplacement et les déformations correspondantes. Grâce à ces mesures dynamiques, des données importantes ont été produites et enregistrées, notamment la période de vibration, la fréquence, la vitesse et le déplacement des différents échantillons testés. Sur la base de ces données expérimentales, l’effet de la section et de la portée des poutres sur la réponse dynamique et sur le mode d’endommagement des sous-assemblages a été discuté. Cette étude montre que les résultats expérimentaux obtenus, en termes de mécanismes structurels, de schéma de fissuration, de mode d'endommagement, peuvent être utilisés pour analyser le comportement de sous-assemblages de structures réelles.De plus, une modélisation numérique des essais a été réalisée pour simuler le processus de ruine de la structure. Une technique appelée «connecteur» a été proposée dans le modèle aux éléments finis du sous-assemblage poteaux-poutres. Cette technique consiste à ajouter une série de ressorts pour étudier le rôle de l’interaction entre les armatures en acier et le béton. Un modèle d'endommagement anisotrope, appelé modèle DFH-KST, a été utilisé pour caractériser l'évolution de la fissuration et l’endommagement du béton.La polyvalence de la méthodologie adoptée permet d’évaluer l’influence du comportement non-linéaire du matériau et celle de la géométrie de la structure testée. Les études numériques de calibration et de validation montrent que le modèle proposé peut reproduire le comportement et la résistance de la structure avec succès. / Important buildings may be subjected to accidental loads, such as explosions or impacts, during their service life. It is, therefore, necessary not only to evaluate their safety under traditional loads and seismic action. The structural performances related to progressive collapse scenarios need to be investigated.The study of progressive collapse involves a dynamic problem, but unfortunately dynamic experiments on the behavior of the civil engineering structures under dynamic conditions are rare. In this research, beam-column sub-assemblage specimens were tested under dynamic load. The loading program consists in placing a large mass, as a dead load, on the top of the middle column of a beam-column sub-assemblage. The support under the middle column is suddenly removed for simulating the sudden loss of a column and the damage that will result in the structure. The loading system and supporting devices were designed specially for this test. The upper dead load can be changed by increasing or decreasing the applied masse to different specimens. The supports for the side column have a controlled rigidity in the horizontal direction and are designed to restrain rotation of the side-column. Thus, the boundary conditions are supposed to be similar to real situations. During the test, a laser was installed under the middle pillar to collect the falling velocity and a high-speed camera was used to visualize the whole process of the component failure process. The images obtained from the camera were processed by Digital Image Correlation (DIC) technology to get the corresponding displacements and strain fields. By these means, all the information of the structure under dynamic loading was captured and recorded, such as the period of vibration, frequency, velocity and displacement. Based on these experimental data, the effect of section and span of the specimen on dynamic response and damage mode was discussed. Time history of resistance force curves was produced. Compared with previous published quasi-static experiments in terms of structural mechanisms, crack patterns, damage mode, it shows the experimental results from beam-column assemblage with the designed support device can be used to analyze the behavior of the local structure in the entire frame.In addition, numerical simulations were developed for simulating the failing process of the structure. A technique named “connector” was proposed into beam-column finite element model by adding a series of springs to investigate the interaction between steel rebars and concrete. A concrete damage model, named DFH-KST model, was used to characterize the development of concrete crack and damage. The versatility of the adopted methodology allows assessing the influence of the material nonlinear behavior and the geometry of the tested structure. Calibration and validation studies show that the proposed model can successfully represent the resistance of structure and behavior. Furthermore, the transverse component effect on the resistance to progressive collapse was discussed.

Dans les environnements d'exécution parallèle, la régulation de charge (ou l'ordonnancement applicatif) est le module responsable du contrôle de l'exécution d'un programme sur les ressources de l'architecture distribuée (processeurs et modules mémoire). En pratique, le choix de la stratégie de régulation la plus performante dépend non seulement de l'application mais doit aussi être adapté en fonction de l'architecture cible. Dès lors, la portabilité d'un code ne peut être assurée que si l'on peut modifier cette stratégie. Dans cette thèse, nous proposons l'utilisation de la description dynamique du flot de données comme l'élément central permettant de séparer le code applicatif de la régulation de charge. Sur cette proposition est basée la construction d'un environnement logiciel, modulaire et générique, qui rend possible la modification ou l'ajustement de la stratégie de régulation de charge. La spécification de cet environnement repose sur l'identification des interfaces de la régulation avec d'une part l'application et d'autre part l'architecture. Cette identification, centrée sur l'exploration macroscopique du flot de données, est originale: nous montrons qu'elle étend d'autres systèmes classiques de régulation de charge. Enfin, la validation expérimentale de cet environnement est réalisée grâce à son intégration dans l'interface de programmation Athapascan-1 de l'environnement Athapascan, du projet APACHE. Différentes stratégies d'ordonnancement, statiques, dynamiques et hybrides, ont ainsi été implantés. Nous présentons les performances de quelques unes de ces stratégies appliquées à des programmes Athapascan-1 sur différentes architectures.

L'objectif de ce travail est la mise au point et le test d'une série d'éléments finis de coque permettant de prendre en compte l'essentiel des situations rencontrées dans le calcul des ouvrages d'art. Pour ce faire, nous avons ainsi considéré trois catégories d'éléments : - Nous avons tout d'abord étudié les éléments de plaque en flexion à 3 et 4 noeuds (DKT et DKQ) basés sur les hypothèses de Love-Kirchhoff sous forme discrète. Après avoir étendu leur formulation pour permettre le calcul de coques de forme quelconque et d'épaisseur variable, nous avons effectué une série de tests numériques (plaque, coque cylindrique, structure de type caisson, barrage-voûte) qui permettent d'évaluer leurs performances. - Nous avons par la suite étudié le comportement des éléments de coque épaisse à 8 noeuds basés sur les hypothèses cinématiques de Mindlin. Les tests numériques effectués nous ont permis de vérifier que ces éléments sont très adaptés au calcul des structures épaisses et des structures dans lesquelles les effets de membrane sont importants. - Pour permettre l'étude de structures coques comportant des parties massives devant être modélisées par des éléments tridimensionnels, nous avons également étudié des éléments de coque épaisse de type tridimensionnel à 16 ou 12 noeuds permettant grâce à des éléments de transition une connection facile avec les éléments massifs.

L'équilibrage de charge est une étape importante conditionnant les performances des applications parallèles. Dans le cas où la charge varie au cours de la simulation, il est important de redistribuer régulièrement la charge entre les différents processeurs. Dans ce contexte, il peut s'avérer pertinent d'adapter le nombre de processeurs au cours d'une simulation afin d'obtenir une meilleure efficacité, ou de continuer l'exécution quand toute la mémoire des ressources courantes est utilisée. Contrairement au cas où le nombre de processeurs ne varie pas, le rééquilibrage dynamique avec un nombre variable de processeurs est un problème peu étudié que nous abordons ici.Cette thèse propose différentes méthodes basées sur le repartitionnement de graphe pour rééquilibrer la charge tout en changeant le nombre de processeurs. Nous appelons ce problème « repartitionnement M x N ». Ces méthodes se décomposent en deux grandes étapes. Dans un premier temps, nous étudions la phase de migration et nous construisons une « bonne » matrice de migration minimisant plusieurs critères objectifs comme le volume total de migration et le nombre total de messages échangés. Puis, dans un second temps, nous utilisons des heuristiques de partitionnement de graphe pour calculer une nouvelle distribution optimisant la migration en s'appuyant sur les résultats de l'étape précédente. En outre, nous proposons un algorithme de partitionnement k-aire direct permettant d'améliorer le partitionnement biaisé. Finalement, nous validons cette thèse par une étude expérimentale en comparant nos méthodes aux partitionneursactuels. / Load balancing is an important step conditioning the performance of parallel programs. If the workload varies drastically during the simulation, the load must be redistributed regularly among the processors. Dynamic load balancing is a well studied subject but most studies are limited to an initially fixed number of processors. Adjusting the number of processors at runtime allows to preserve the parallel code efficiency or to keep running the simulation when the memory of the current resources is exceeded.In this thesis, we propose some methods based on graph repartitioning in order to rebalance the load while changing the number of processors. We call this problem \M x N repartitioning". These methods are split in two main steps. Firstly, we study the migration phase and we build a \good" migration matrix minimizing several metrics like the migration volume or the number of exchanged messages. Secondly, we use graph partitioning heuristics to compute a new distribution optimizing the migration according to the previous step results. Besides, we propose a direct k-way partitioning algorithm that allows us to improve our biased partitioning. Finally, an experimental study validates our algorithms against state-of-the-art partitioning tools.

La dérégulation du marché de l'électricité, qui concerne progressivement tous les pays d'Europe, modifie profondément l'approche technico-économique dans l'exploitation et l'optimisation des réseaux électriques. C'est dans ce nouveau contexte que les spécialistes des .réseaux électriques se voient de plus en 'plus confrontés à de nombreux défis. Le développement des dispositifs FACTS (Flexible AC Transmission System) ouvre de nouvelles perspectives pour une meilleure exploitation des réseaux par leur action continue et rapide _sur les différents paramètres du réseau. Toutefois, ces dispositifs, ne sont pas à l'abri d'éventuelles interactions entre eux mais aussi avec d'autres éléments du réseau tels que les charges dynamiques. Cette thèse, qui s'inscrit dans le cadre de l'analyse et l'amélioration de la sécurité dynamique des réseaux électriques, s'est focalisé sur l'impact de l'interaction des dispositifs FACTS avec les charges dynamiques. Dans ce travail, il a été démontré que les boucles d'amortissement des oscillations de puissance dimensionnées par les techniques classiques de sensibilité ne sont pas robustes vis-à-vis des variations des modèles de charge. Pour remédier ,à ces problèmes, une première méthode, basée sur la sensibilité des valeurs propres et tenant compte. des variations des modèles de charge, a été proposée. Deux autres méthodes plus robustes, basées sur les techniques LMI, ont été mises en oeuvre. La première, basée Sllr une représentation polytopique des systèmes incertains, convient au cas d'incertitudes non structurées. La deuxième, basée sur une représentation LPV (système linéaire à paramètres variants), permet de traiter le cas d'incertitudes structurées.

Cette thèse s'inscrit comme une étape vers la maîtrise de la résistance au choc des structures en béton, en développant la connaissance du comportement dynamique du matériau pour mieux calculer les ouvrages vis-à-vis des chargements accidentels. Une première partie récapitule les mécanismes physiques mis en évidence grâce aux essais de traction directe à des vitesses échelonnées du régime quasi-statique au domaine atteint lors des chocs durs (technique des barres d'Hopkinson), et propose plusieurs expressions de l'évolution de la résistance avec la vitesse, en fonction des paramètres caractéristiques du matériau. On a pu en déduire une optimisation du béton par rapport aux sollicitations dynamiques rapides. Une deuxième partie décrit l'essai de dalles au tube à choc, mis au point pour valider sur une structure modèle les résultats obtenus à l'échelle du matériau. Les données recueillies sur 24 dalles constituées de différents bétons, armés ou non, sont présentées en détails. Leur analyse permet de tester plusieurs méthodes de calcul approchées, et de définir un cahier des charges incontournable pour des modèles de calcul en dynamique plus sophistiqués, qui restent à développer.

Bien qu'utilisé depuis longtemps dans les voies ferrées, le ballast in situ a un comportement encore mal connu. L'objet de ce mémoire est donc de décrire le processus d'identification d'une loi de tassement du ballast et d'un modèle de dégradation réaliste des voies ballastées. Le travail expérimental, réalisé au moyen d'un essai à échelle un tiers sert à identifier la loi de tassement du ballast -sous une traverse- dans le plan vertical. Pour cela, des lois de similitude décrivent le passage des grandeurs associées au modèle réel à celle du modèle réduit. Elles sont basées sur la conservation du matériau ballast et la conservation des champs de contraintes au sein de l'éprouvette. L'éprouvette de ballast est soumise à un chargement vertical reproduisant la charge appliquée sur le ballast lors du passage d'un bogie de TGV. Les résultats de cet essai servent à établir la loi de tassement du ballast qui relie le tassement à la déflexion élastique de l'ensemble formé par le ballast et le sol sur lequel il repose. Les paramètres intervenant dans le chargement, la qualité du sol supportant le ballast et l'épaisseur de la couche de ballast sont discutés. La simulation numérique vient compléter l'expérience, en étendant l'étude à une portion de voie. L'objectif est d'analyser l'évolution des défauts de voie en fonction du trafic. Les défauts considérés peuvent être d'ordre géométrique (irrégularités du nivellement lors de la mise en place de la voie) ou porter sur des variations de raideur du ballast et du sol. Un modèle de véhicule en circulation a aussi été développé pour calculer les efforts dynamiques exercés sur le rail. Ces efforts dynamiques sont ensuite injectés dans un modèle quasi-statique de voie prenant en compte le comportement du ballast identifié expérimentalement. Les évolutions de profils de voie ainsi calculées démontrent que les défauts de raideur du ballast et du sol sont plus endommageants pour la voie que les défauts de géométrie. Ce mémoire se termine par une analyse micromécanique du ballast, considéré pour l'occasion, comme un assemblage de corps rigides, discrets et tridimensionnels en contact. L'intérêt principal de cette étude est de démontrer la possibilité de modéliser, de façon discrète, le comportement unilatéral du ballast. Le modèle numérique ainsi développé reproduit fidèlement les résultats obtenus expérimentalement.

On propose une modélisation numérique des plaques multicouches en matériaux composites lorsqu'elles sont soumises à l'impact de charges dynamiques. Cette modélisation permet de déterminer les efforts engendrés par l'impact, le but étant de pouvoir étudier certains endommagements comme le délaminage. La nouvelle modélisation utilisée appelée modélisation multiparticulaire des matériaux multicouches (M4), permet de modéliser l'objet tridimensionnel par une géométrie bidimensionnelle tout en augmentant le nombre de champs cinématiques. Elle fait apparaître de manière naturelle des efforts au niveau des interfaces entre les couches. Ces efforts peuvent être reliés au phénomène de délaminage. L'analyse des résultats de la littérature permet de montrer que cette modélisation est pertinente dans le cas des chocs relativement rapides. Un outil numérique a été réalisé sur la base de la méthode des éléments finis en dynamique. Le code éléments finis obtenu est ensuite validé, puis appliqué à l'analyse des efforts dans une plaque multicouche impactée. Nous montrons sur un exemple, la pertinence de cette modélisation et sa capacité à fournir de manière simple et rapide, des informations utiles pour l'étude des différents aspects du délaminage (initiation, propagation, étendue).

L'équilibrage de charge est une étape importante conditionnant les performances des applications parallèles. Dans le cas où la charge varie au cours de la simulation, il est important de redistribuer régulièrement la charge entre les différents processeurs. Dans ce contexte, il peut s'avérer pertinent d'adapter le nombre de processeurs au cours d'une simulation afin d'obtenir une meilleure efficacité, ou de continuer l'exécution quand toute la mémoire des ressources courantes est utilisée. Contrairement au cas où le nombre de processeurs ne varie pas, le rééquilibrage dynamique avec un nombre variable de processeurs est un problème peu étudié que nous abordons ici. Cette thèse propose différentes méthodes basées sur le repartitionnement de graphe pour rééquilibrer la charge tout en changeant le nombre de processeurs. Nous appelons ce problème " repartitionnement M × N ". Ces méthodes se décomposent en deux grandes étapes. Dans un premier temps, nous étudions la phase de migration et nous construisons une " bonne " matrice de migration minimisant plusieurs critères objectifs comme le volume total de migration et le nombre total de messages échangés. Puis, dans un second temps, nous utilisons des heuristiques de partitionnement de graphe pour calculer une nouvelle distribution optimisant la migration en s'appuyant sur les résultats de l'étape précédente. En outre, nous proposons un algorithme de partitionnement k-aire direct permettant d'améliorer le partitionnement biaisé. Finalement, nous validons cette thèse par une étude expérimentale en comparant nos méthodes aux partitionneurs actuels.