La méthode PEEC est connue comme une bonne méthode pour la modélisation des interconnexions électriques dans les domaines de l’électronique de puissance et l’électrotechnique. Elle s'applique à une large gamme de dispositifs : circuits imprimés, bus-barres, conducteurs massifs. Elle est particulièrement bien adaptée pour la modélisation de régions conductrices du type filaire. Cependant, elle est requise d’un maillage structuré(discrétisation des géométries en quadrangles) et l’approche est limitée en fréquence (grande épaisseur de peau). Enfin, il semble actuellement difficile d’envisager la modélisation de conducteurs volumiques dans une formulation PEEC standard.Cette thèse développe des formulations intégrales en utilisant des éléments de facette afin d’lever des verrous de la méthode PEEC standard évoqués ci-dessus. Elle constitue de fait une généralisation de la méthode PEEC standard par la prise en compte de maillages non structurés (volumique et surfacique) et la prise en compte de notion de régions minces à faible épaisseur de peau.Les applications visées sont la modélisation de systèmes de conducteurs complexes (des régions non simplement connexes) en prenant en compte des connexions entre des régions (volumique/filaire, surfacique/filaire,volumique/surfacique et surfacique/surfacique). / The PEEC method is known as a good method for modeling electrical connections in the domains of powerelectronics and electrical engineering. It applies to a wide range of devices: printed circuits, bus-bars, solidconductors. It is particularly well adapted for modeling the wire type conductive regions. However, it is requireda structured mesh (discretization geometries quadrangles) and this approach is limited in frequency (high skindepth). Finally, it now seems difficult to envisage modeling of the volume conductors in standard PEECformulation.This thesis develops integrals formulations using facet elements to improve the above mentioned limitations ofthe standard PEEC method. It is in fact a generalization of the standard PEEC method by taking into accountunstructured meshes (volume and surface) and taking into account the notion of thin region with a small skindepth.The applications are the modeling of complex systems of conductors (non-simply connected regions) taking intoaccount the connections between regions (volume / wireframe, surface / wired volume / surface and surface /surface).

Étant donné un graphe G = (V U T, E), tel que V U T représente l'ensemble des sommets où T est un ensemble de terminaux, et une fonction poids w associée aux sommets non terminaux, le problème du séparateur de poids minimum consiste à partitionner V U T en k + 1 sous-ensembles {S, V1,..., Vk} tel qu'il n'y a aucune arête entre deux sous-ensembles différents Vi et Vj, chaque Vi contient exactement un terminal et le poids de S est minimum. Dans cette thèse, nous étudions le problème d'un point de vue polyèdral. Nous donnons deux formulations en nombres entiers pour le problème, et pour une de ces formulations, nous étudions le polyèdre associé. Nous présentons plusieurs inégalités valides, et décrivons des conditions de facette. En utilisant ces résultats, nous développons un algorithme de coupes et branchement pour le problème. Nous étudions également le polytope des séparateurs dans les graphes décomposables par sommets d'articulation. Si G est un graphe qui se décompose en G1 et G2, alors nous montrons que le polytope des séparateurs dans G peut être décrit à partir de deux systèmes linéaires liés à G1 et G2. Ceci donne lieu à une technique permettant de caractériser le polytope des séparateurs dans les graphes qui sont récursivement décomposables. Ensuite, nous étudions des formulations étendues pour le problème et proposons des algorithmes de génération de colonnes et branchement ainsi que des algorithmes de génération de colonnes, de coupes et branchement. Pour chaque formulation, nous présentons un algorithme de génération de colonnes, une procedure pour le calcul de la borne duale ainsi qu'une règle de branchement. De plus, nous présentons quatre variantes du problème du séparateur. Nous montrons que celles-ci sont NP-difficiles, et pour chacune d'elles nous donnons une formulation en nombres entiers et présentons certaines classes d'inégalités valides. / Given a graph G = (V U T, E) with V U T the set of vertices, where T is a set of terminals, and a weight function w, associated with the nonterminal nodes, the multi-terminal vertex separator problem consists in partitioning V U T into k + 1 subsets {S, V1,..., Vk} such that there is no edge between two different subsets Vi and Vj, each Vi contains exactly one terminal and the weight of S is minimum. In this thesis, we consider the problem from a polyhedral point of view. We give two integer programming formulations for the problem, for one of them, we investigate the related polyhedron. We describe some valid inequalities and characterize when these inequalities define facets. Using these results, we develop a Branch-and-Cut algorithm for the problem. We also study the multi-terminal vertex separator polytope in the graphs decomposable by one node cutsets. If G is a graph that decomposes into G1 and G2, we show that the multi-terminal vertex separator polytope in G can be described from two linear systems related to G1 and G2. This gives rise to a technique for characterizing the multi-terminal vertex separator polytope in the graphs that are recursively decomposable. Moreover, we propose three extended formulations for the problem and derive Branch-and-Price and Branch-and-Cut-and-Price algorithms. For each formulation we present a column generation scheme, the way to compute the dual bound, and the branching scheme. Finally, we discuss four variants of the multi-terminal vertex separator problem. We show that all these variants are NP-hard and for each one we give an integer programming formulation and present some class of valid inequalities.

In this thesis, we consider the k-edge connected L-hop-constrained network design problem. Given a weighted graph G=(N,E), a set D of pairs of terminal nodes, and two integers k,L > 1, it consists in finding in G the minimum cost subgraph containing at least k edge-disjoint paths of at most L edges between each pair in D. This problem is of great interest in today's telecommunication industry, where highly survivable networks need to be constructed. We first study the particular case where the set of demands D is reduced to a single pair {s,t}. We propose an integer programming formulation for the problem, which consists in the st-cut and trivial inequalities, along with the so-called L-st-path-cut inequalities. We show that these three classes of inequalities completely describe the associated polytope when k=2 and L=2 or 3, and give necessary and sufficient conditions for them to be facet-defining. We also consider the dominant of the associated polytope, and discuss how the previous inequalities can be separated in polynomial time. We then extend the complete and minimal description obtained above to any number k of required edge-disjoint L-st-paths, but when L=2 only. We devise a cutting plane algorithm to solve the problem, using the previous polynomial separations, and present some computational results. After that, we consider the case where there is more than one demand in D. We first show that the problem is strongly NP-hard, for all L fixed, even when all the demands in D have one root node in common. For k=2 and L=2,3, we give an integer programming formulation, based on the previous constraints written for all pairs {s,t} in D. We then proceed by giving several new classes of facet-defining inequalities, valid for the problem in general, but more adapted to the rooted case. We propose separation procedures for these inequalities, which are embedded within a Branch-and-Cut algorithm to solve the problem when L=2,3. Extensive computational results from it are given and analyzed for both random and real instances. Since those results appear less satisfactory in the case of arbitrary demands (non necessarily rooted), we present additional families of valid inequalites in that situation. Again, separation procedures are devised for them, and added to our previous Branch-and-Cut algorithm, in order to see the practical improvement granted by them. Finally, we study the problem for greater values of L. In particular, when L=4, we propose new families of constraints for the problem of finding a subgraph that contains at least two L-st-paths either node-disjoint, or edge-disjoint. Using these, we obtain an integer programming formulation in the space of the design variables for each case. ------------------------------------------------ Dans cette thèse, nous considérons le problème de conception de réseau k-arete connexe à chemins L-bornés. Etant donné un graphe pondéré G=(N,E), un ensemble D de paires de noeuds terminaux, et deux entiers k,L > 1, ce problème consiste à trouver, dans G, un sous-graphe de cout minimum tel que, entre chaque paire dans D, il existe au moins k chemins arete-disjoints de longueur au plus L. Ce problème est d'un grand intéret dans l'industrie des télécommunications, où des réseaux hautement fiables doivent etre construits. Nous étudions tout d'abord le cas particulier où l'ensemble des demandes D est réduit à une seule paire de noeuds. Nous proposons une formulation du problème sous forme de programme linéaire en nombres entiers, laquelle consiste en les inégalités triviales et de coupe, ainsi que les inégalités dites de L-chemin-coupe. Nous montrons que ces trois types d'inégalités décrivent complètement le polytope associé lorsque k=2 et L=2,3, et donnons des conditions nécessaires et suffisantes pour que celles-ci en définissent des facettes. Nous considérons également le dominant du polytope associé et discutons de la séparation polynomiale des trois classes précédentes. Nous étendons alors cette description complète et minimale à tout nombre k de chemins arete-disjoints de longueur au plus 2. De plus, nous proposons un algorithme de plans coupants utilisant les précédentes séparations polynomiales, et en présentons quelques résultats calculatoires, pour tout k>1 et L=2,3. Nous considérons ensuite le cas où plusieurs demandes se trouvent dans D. Nous montrons d'abord que le problème est fortement NP-dur, pour tout L fixé et ce, meme si les demandes sont toutes enracinées en un noeud. Pour k=2 et L=2,3, nous donnons une formulation du problème sous forme de programme linéaire en nombres entiers. Nous proposons également de nouvelles classes d'inégalités valides, pour lesquelles nous réalisons une étude faciale. Celles-ci sont alors séparées dans le cadre d'un algorithme de coupes et branchements pour résoudre des instances aléatoires et réelles du problème. Enfin, nous étudions le problème pour de plus grandes valeurs de L. En particulier, lorsque L=4, nous donnons de nouvelles familles de contraintes pour le problème consistant à déterminer un sous-graphe contenant entre deux noeuds fixés au moins deux chemins de longueur au plus 4, que ceux-ci doivent etre arete-disjoints ou noeud-disjoints. Grace à ces dernières, nous parvenons à donner une formulation naturelle du problème dans chacun de ces deux cas.

Dans cette thèse, nous nous intéressons à un problème de fiabilité dans les réseaux multicouches IP-sur-WDM. Etant donné un ensemble de demandes pour lesquelles on connaît une topologie fiable dans la couche IP, le problème consiste à sécuriser la couche optique WDM en y cherchant une topologie fiable. Nous montrons que le problème est NP-complet même dans le cas d'une seule demande. Ensuite, nous proposons quatre formulations en termes de programmes linéaires en nombres entiers pour le problème. La première est basée sur les contraintes de coupes. Nous considérons le polyèdre associé. Nous identifions de nouvelles familles de contraintes valides et étudions leur aspect facial. Nous proposons également des algorithmes de séparation pour ces contraintes. En utilisant ces résultats, nous développons un algorithme de coupes et branchements pour le problème et présentons une étude expérimentale. La deuxième formulation utilise comme variables des chemins entre des terminaux dans le graphe sous-jacent. Un algorithme de branchements et génération de colonnes est proposé pour cette formulation. Par la suite, nous discutons d'une formulation dite naturelle utilisant uniquement les variables de design. Enfin, nous présentons une formulation étendue compacte qui, en plus des variables naturelles, utilise des variables de routage. Nous montrons que cette formulation fournit une meilleure borne inférieure. / This thesis deals with a problem related to survivability issues in multilayer IP-over-WDM networks. Given a set of traffic demands for which we know a survivable logical routing in the IP layer, the aim is determine the corresponding survivable topology in the WDM layer. We show that the problem is NP-hard even for a single demand. Moreover, we propose four integer linear programming formulations for the problem. The first one is based on the so-called cut inequalities. We consider the polyhedron associated with the formulation. We identify several families of valid inequalities and discuss their facial aspect. We also develop separation routines. Using this, we devise a Branch-and-Cut algorithm and present experimental results. The second formulation uses paths between terminals of the underlying graph as variables. We devise a Branch-and-Price algorithm based on that formulation. In addition, we investigate a natural formulation for the problem which uses only the design variables.  Finally, we propose an extended compact formulation which, in addition to the design variables, uses routing variables. We show that this formulation provides a tighter bound for the problem.

Les interconnexions des circuits intégrés sub-0.25µm nécessitent l'intégration d'isolants «low-K» à plus faible permittivité diélectrique que SiO2 (~ 4.4) tel que le SiLK™ (~ 2.65), un matériau organique prometteur. Mais sa gravure plasma conduit à l'obtention de structures en forme de tonneau («bow»), alors que les profils gravés doivent rester anisotropes pour les étapes ultérieures d'intégration. Afin de réduire le bow, cette étude montre que la passivation des flancs des structures gravées est nécessaire, et fortement corrélée à la dégradation («graphitisation») du SiLK et à la présence de résidus carbonés peu volatils dans le plasma. La présence de sources carbonées autres que le SiLK™ permet aussi d'améliorer la passivation. L'étude du phénomène à l'origine du bow montre enfin que les charges électrostatiques jouent un rôle majoritaire dans la déflexion des ions sur les flancs. Ces résultats intéressent également tous les low-Ks à faible seuil de gravure ionique réactive.

L’organisation des connaissances est une discipline investie par des bibliothécaires, documentalistes, archivistes spécialistes de l’information, informaticiens et tous professionnels de documents. Elle englobe toutes activités, études et recherches qui élaborent et traitent les processus d’organisation et de présentation des ressources documentaires utiles dans une organisation. Dans ce contexte, le projet ANR Miipa-Doc a pour objectifs d’explorer des nouvelles méthodes d’indexation ascendantes, en utilisant des termes descripteurs formulés par les individus plutôt que choisis parmi une liste préétablie, pour l’organisation des contenus documentaires complexes au sein des entreprises de large taille, et concevoir l’architecture logicielle correspondante.Dans ce projet notre contribution consiste à gérer l’hétérogénéité d’un système d’information d’organisation des contenus documentaires, basé sur une approche orientée métier et un SOC (système d’organisation des connaissances) folksonomique à facette. Nous proposons dans cette gestion une approche incrémentale dirigée par les modèles, issue de l’IDM (ingénierie dirigée par les modèles), basée sur des méta-modèles pour garantir l’aspect d’évolutivité. Après l’implémentation du prototype HyperTaging qui met en place ces deux approches, nous proposons un processus d’évaluation permet de positionner ce prototype et tous SI de classification documentaire dans l’environnement des ECM, en se basant sur des critères d’évaluation fins et particuliers. / The knowledge organization is invested by librarians, archivists, information specialists, IT professionals and all discipline of document. It includes all activities, studies and research which develop and treat organization process and presentation of relevant information resources in an organization. In this context the Miipa-Doc project aims to explore new ascendants indexing methods, using descriptors made by individuals rather than selected given list for complex contained in the organization document, in large size companies, and design the corresponding software architecture.Our contribution in this project is to manage the heterogeneity of an information system of document organization, based on a business-oriented approach and a KOS (knowledge organization system) of folksonomy facet. We propose an incremental approach this management model driven, outcome of MDE (Model Driven Engineering), based on meta-models to ensure scalability appearance. After implementing the HyperTaging prototype, that implements both approaches, we propose an evaluation process used to position the prototype and all IS of documentary classification in the environment of ECM based on purposes of delicate and particular evaluation criteria.

Nur ein Bruchteil der in den Schlagwortnormsätzen abgelegten Informationen wird von heutigen OPACs für die Benutzerrecherche nutzbar gemacht. Wie man das Input-Output-Verhältnis der bibliothekarischen Erschließungsleistung verbessern kann, wird am Beispiel der ISO-Ländercodes gezeigt. Diese werden nicht nur in Datensätzen für Geographika erfasst, sondern z.B. auch bei Personen und Körperschaften. Macht man sie im OPAC recherchierbar, so können sie als Basis für eine Einschränkung nach dem geographischen Raum dienen. Dadurch erhöht sich der Recall bei Anfragen vom Typ "Tourismus in Baden-Württemberg" oder "Klima in Afrika" teils dramatisch, ohne dass sich die Precision verschlechtern würde. Denn über die Ländercodes wird auch Literatur zu kleineren geographischen Einheiten gefunden (z.B. Landkreise, Städte, Landschaften), die bei einer einfachen Schlagwortsuche ausgeblendet bleiben. Im HEIDI-Katalog der UB Heidelberg und im Primo-Katalog der UB Mannheim wurde die Ländercode-Recherche vor kurzem prototypisch in Form eines Drill-down-Menüs realisiert.

Ces dernières années, la Méthode Intégrale de Volume (MIV) a reçu une attention particulière pour lamodélisation des problèmes électromagnétiques en basse fréquence. Son intérêt principal est l’absencedu maillage de la région air, ce qui rend la méthode légère et rapide. Associée aux méthodes decompression matricielle la MIV devient aujourd'hui une alternative compétitive à la méthode deséléments finis pour la modélisation de dispositifs électromagnétiques ayant un volume d'airprépondérant.Ce rapport porte sur le développement de deux formulations intégrales de volume pour la résolution deproblèmes magnétostatiques avec prise en compte des matériaux non linéaires, des aimants, desbobines, des circuits magnétiques avec ou sans entrefer et des régions minces magnétiques. Lapremière est une formulation en flux de mailles indépendantes basée sur l'interpolation par éléments defacette. La deuxième est une formulation en potentiel vecteur magnétique basée sur l'interpolation paréléments d'arête. L'application de ces formulations permet d’une part d'obtenir des résultats précismême en présence d’un faible maillage et d’autre part de résoudre aisément des problèmes nonlinéaires. Des méthodes de calcul de la force magnétique globale ainsi que du flux magnétique dansles bobines ont été également mises en oeuvre. Les développements informatiques ont été réalisés dansla plateforme MIPSE et ont été validés sur des problèmes académiques ainsi que sur quelquesdispositifs industriels. / In recent years, the Volume Integral Method (VIM) has been received particular attention formodeling of low frequency electromagnetic problems. The main advantage of this method is thatinactive regions do not to be discretized, which makes it light and rapid. Associated with matrixcompression methods, the VIM is a competitive alternative to the finite element method for modelingelectromagnetic devices containing a predominant air volume.This PhD thesis focuses on the development of two volume integral formulations for solvingmagnetostatic problems, in the presence of nonlinear materials, magnets, coils, multiply connectedmagnetic regions, and the presence of magnetic shielding. The first one is a mesh magnetic fluxformulation based on the interpolation of facet elements and the second one is a magnetic vectorpotential formulation based on the interpolation of edge elements. The application of theseformulations provides accurate results even with coarse meshes and allows solving straightforwardnonlinear magnetostatic problems. Methods for computing global magnetic force and magnetic fluxthrough a coil were also implemented as part of this work. Developments performed in the MIPSEplatform were validated on academic case-tests as well as some industrial devices.

L’organisation des connaissances est une discipline investie par des bibliothécaires, documentalistes, archivistes spécialistes de l’information, informaticiens et tous professionnels de documents. Elle englobe toutes activités, études et recherches qui élaborent et traitent les processus d’organisation et de présentation des ressources documentaires utiles dans une organisation. Dans ce contexte, le projet ANR Miipa-Doc a pour objectifs d’explorer des nouvelles méthodes d’indexation ascendantes, en utilisant des termes descripteurs formulés par les individus plutôt que choisis parmi une liste préétablie, pour l’organisation des contenus documentaires complexes au sein des entreprises de large taille, et concevoir l’architecture logicielle correspondante.Dans ce projet notre contribution consiste à gérer l’hétérogénéité d’un système d’information d’organisation des contenus documentaires, basé sur une approche orientée métier et un SOC (système d’organisation des connaissances) folksonomique à facette. Nous proposons dans cette gestion une approche incrémentale dirigée par les modèles, issue de l’IDM (ingénierie dirigée par les modèles), basée sur des méta-modèles pour garantir l’aspect d’évolutivité. Après l’implémentation du prototype HyperTaging qui met en place ces deux approches, nous proposons un processus d’évaluation permet de positionner ce prototype et tous SI de classification documentaire dans l’environnement des ECM, en se basant sur des critères d’évaluation fins et particuliers. / The knowledge organization is invested by librarians, archivists, information specialists, IT professionals and all discipline of document. It includes all activities, studies and research which develop and treat organization process and presentation of relevant information resources in an organization. In this context the Miipa-Doc project aims to explore new ascendants indexing methods, using descriptors made by individuals rather than selected given list for complex contained in the organization document, in large size companies, and design the corresponding software architecture.Our contribution in this project is to manage the heterogeneity of an information system of document organization, based on a business-oriented approach and a KOS (knowledge organization system) of folksonomy facet. We propose an incremental approach this management model driven, outcome of MDE (Model Driven Engineering), based on meta-models to ensure scalability appearance. After implementing the HyperTaging prototype, that implements both approaches, we propose an evaluation process used to position the prototype and all IS of documentary classification in the environment of ECM based on purposes of delicate and particular evaluation criteria.

La connaissance inter-entreprises permet à chaque société de se renseigner sur ses clients, ses fournisseurs et de développer son activité tout en limitant le risque lié à la solvabilité ou retard de paiement de ses partenaires. Avec les tensions de trésorerie, la nécessité de la croissance et l'augmentation de la concurrence, ce domaine devient plus que jamais stratégique aussi bien pour les PME que pour les grands groupes. La quantité de données traitée dans ce domaine, les exigences de qualité et de fraîcheur, la nécessité de croiser ces données pour déduire des nouvelles informations et indicateurs, posent plusieurs problèmes pour lesquels l'optimisation en général et l'optimisation combinatoire en particulier peuvent apporter des solutions efficaces. Dans cette thèse, nous utilisons l'optimisation combinatoire, l'algorithmique du texte et la théorie des graphes pour résoudre efficacement des problèmes issus du domaine de la connaissance inter-entreprises et posés par Altares D&B. Dans un premier temps, nous nous intéressons à la qualité de la base de données des dirigeants. Ce problème combine la détection et suppression des doublons dans une base de données et la détection d'erreurs dans une chaîne de caractères. Nous proposons une méthode de résolution basée sur la normalisation des données et l'algorithmique de texte et de comparaison syntaxique entre deux chaînes de caractères. Les résultats expérimentaux montrent non seulement que cette méthode est pertinente dans la détection et la suppression des doublons mais aussi qu'elle est efficace de point du vue temps de traitement. Nous nous focalisons par la suite sur les données des liens capitalistiques et nous considérons le problème de calcul des liens indirects et l'identification des têtes des groupes. Nous présentons une méthode de résolution basée sur la théorie des graphes. Nous testons cette méthode sur plusieurs instances réelles. Nous prouvons l'efficacité de cette méthode par son temps de traitement et par l'espace de calcul qu'elle utilise. Enfin, nous remarquons que le temps de calcul de celui-ci augmente de façon logarithmique en fonction de la taille d'instance. Enfin, nous considérons le problème de l'identification des réseaux d'influence. Nous formalisons ce problème en termes de graphes et nous le ramenons à un problème de partitionnement de graphe qui est NP-difficile dans ce cas général. Nous proposons alors une formulation en programme linéaire en nombre entier pour ce problème. Nous étudions le polyèdre associé et décrivons plusieurs classes de contraintes valides. Nous donnons des conditions nécessaires pour que ces contraintes définissent des facettes et discutons des algorithmes de séparations de ces contraintes. En utilisant les résultats polyédraux obtenus, nous développons un algorithme de coupes et branchements. Enfin, nous donnons quelques résultats expérimentaux qui montrent l'efficacité de notre algorithme de coupes et branchements / The inter-companies knowledge allows to every partner to learn about its customers, its suppliers and to develop its activity. Also this permits to limit the risk related to the creditworthiness, or the late payment of its partners. With the cash flow pressures, the need for growth and increased competition, this area becomes more strategic than ever, for both small (PME) and large groups. The amount of data processed in this domain, the requirements of quality and freshness, the need to cross these data to obtain new information and indicators, yield several optimization problems for which the recent techniques and computational tools can bring effective solutions. In this thesis, we use combinatorial optimization, text algorithms as well as graph theory to solve efficiently problems arising in the field of inter-companies knowledge. In particular, such problems was encountered in Altares D&B. First, we focus on the quality of the managers database. This problem combines the detection and removal of duplicates in a database, as well as the error detection in a string. We propose a method for solving this problem, based on data normalization, text algorithms and syntactic comparison between two strings. Our experimental results show that this method is relevant for the detection and removal of duplicates, and it is also very efficient in terms of processing time. In a second part of the thesis, we address a problem related to the data of ownership links. We compute the indirect links, and identify the group heads. We propose a method for solving this problem using graph theory and combinatorial optimization. We then perform a set of experiments on several real-world instances. The computational results show the effectiveness of our method in terms of CPU-time and resource allocation. In fact, the CPU time for computation increases logarithmically with the size of the instances. Finally, we consider the problem of identifying influence networks. We give a description of this problem in terms of graphs, and show that it can reduce to a graph partitioning problem. The latter is NP-hard. We then propose an integer linear programming formulation to model the problem. We investigate the associated polyhedron and describe several classes of valid inequalities. We give some necessaryand sufficient conditions for these inequalities to define facets of the considered polyhedron, and we discuss the related separation problems. Based on the obtained polyhedral results, we devise a Branch-and-Cut algorithm to solve the problem. Some numerical results are presented to show the efficiency of our algorithm.