81 |
[en] PROPOSAL OF A METHODOLOGY FOR THE PRODUCTION AND INTERPRETATION OF EDUCATIONAL MEASURES IN LARGE-SCALE ASSESSMENT BY USING RASCH MODELING WITH TWO OR MORE FACETS / [pt] PROPOSTA DE UMA METODOLOGIA PARA A PRODUÇÃO E INTERPRETAÇÃO DE MEDIDAS EDUCACIONAIS EM AVALIAÇÃO EM LARGA ESCALA POR MEIO DA UTILIZAÇÃO DA MODELAGEM RASCH COM DUAS OU MAIS FACETASWELLINGTON SILVA 18 February 2020 (has links)
[pt] Nesta tese, trabalhou-se com a modelagem Rasch visando a apresentar alternativas mais práticas e de melhor qualidade em termos de medida, para dois cenários distintos. O primeiro está relacionado ao fato de que medir conhecimento é algo muito complexo e de difícil entendimento para profissionais que não são da área da psicometria. Por meio de experimentos envolvendo modelos da família Rasch, apresentamos a aplicabilidade e as potencialidades dessa modelagem para atender a novas demandas de avaliação em larga escala no Brasil. O segundo cenário relaciona-se à busca de medir, de modo o mais imparcial possível, itens de produção escrita, em que a nota recebida pelos alunos é influenciada pela subjetividade dos corretores, ou seja, corretores lenientes beneficiam alunos e corretores severos penalizam alunos. Diante desses dois cenários, esta tese tem os seguintes objetivos: (i) trazer para o âmbito das avaliações realizadas no Brasil uma modelagem matemática mais simples que aquela atualmente adotada, visando uma melhor comunicação com os professores, e; (ii) a possibilidade de operar não apenas com itens de múltipla escolha, corrigidos de forma automática, mas também com itens de produção escrita, em que a subjetividade dos corretores (severidade) é controlada pelo modelo psicométrico, gerando medidas de melhor qualidade. Para isso, utilizou-se a modelagem Rasch com multifacetas, abordando, por meio de casos práticos, as vantagens dessa modelagem em relação a outras metodologias atualmente adotadas no país. Assim, para a alcançarmos o primeiro objetivo, confrontamos a modelagem Rasch com multifacetas com a modelagem de três parâmetros logísticos em um estudo de efeito contexto em testes compostos por diferentes modelos de cadernos e com mais de uma disciplina avaliada por caderno e, para o segundo, comparamos as medidas de proficiência através da Rasch com multifacetas com as notas médias das duplas correções dadas pelos corretores aos alunos em testes do tipo redação. A partir dos resultados encontrados, concluímos que a Rasch com multifacetas pode ser utilizada de forma alternativa ou concomitante com as avaliações que utilizam a modelagem de três parâmetros logísticos, produzindo resultados mais rápidos e de entendimento mais fácil por parte dos professores e que, no caso de redações, as proficiências obtidas pela Rasch com multifacetas apresentaram medidas com melhores indicadores de fidedignidade e validade, quando comparadas com as medidas de notas via Teoria Clássica do Teste, sendo, portanto, uma alternativa mais viável para esse tipo de avaliação. Conclui-se essa tese apresentando situações de empregabilidade das metodologias estudadas. / [en] In this thesis, we worked with Rasch modeling, aiming to present more practical alternatives and better quality in terms of measurement, for two different scenarios. The first one is related to the fact that measuring knowledge is something very complex and difficult to understand for professionals who are not in the psychometrics area. Through experiments involving the Rasch family models, we present the applicability and the potentiality of this model to adequately comply with the new demands of the large-scale evaluation in Brazil. The second scenario is related to the search of measuring, in the most impartial way possible, written production items which grade received by the subjectivity of the raters (severity), that is, lenient raters benefit students and severe raters penalize them. In view of these two scenarios, this thesis has the following objectives: (i) to bring to the scope of the evaluations carried out in Brazil a simpler mathematical modeling than the currently adopted, aiming at a better communication with the teachers; and (ii) the possibility of operating not only with multiple choice items, corrected automatically, but also with written production items, in which the subjectivity of the raters (severity) is controlled by the psychometric model, generating better quality measures. For this, Many-Facet Rasch Measurement was used, approaching, through practical cases, the advantages of this modeling in relation to other methodologies currently adopted in the country. Thus, in order to reach the first objective, we confronted Many-Facet Rasch Measurement with the modeling of three logistic parameters in a study of context effect in tests composed by different models of test books and with more than one discipline evaluated by test book and, for the second one, we compared the measures of proficiency through the Many-Facet Rasch Measurement with the average scores of the double corrections given by the raters to the students in tests of the essay type. From the results found, we conclude that the Many-Facet Rasch Measurement can be used in an alternative or concomitant way with the evaluations that use the three logistic parameters model, producing faster results and easier to understand by the teachers and that, in the case of essays, the measures of proficiency obtained by Many-Facet Rasch Measurement presented measures with better reliability and validity indicators, when compared to the grading measures through the Classical Theory of Testing, being, therefore, a more viable alternative for this type of evaluation. This thesis concludes with situations of usability of the methodologies studied.
|
82 |
Design of Survivable Networks with Bounded-Length Paths / Conception de Réseaux Fiables à Chemins de Longueur BornéeHuygens, David D. P. O. 30 September 2005 (has links)
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.
|
83 |
Všímavost a klinické přístupy založené na jejím rozvíjení / Mindfulness and mindfulness-based treatment approachesŽitník, Jiří January 2011 (has links)
Theoretical section focuses on the concept of mindfulness, its historical background, variety of theoretical approaches and definitions of mindfulness. On this basis I provide own definition of mindfulness. Then, I present an overview of the features and characteristics of mindfulness, its applications in clinical environment, mindfulness-based approaches, effective therapeutic factors, and also its use with specific mental disorders. I also address neural correlates of mindfulness, developmental aspects of mindfulness and overview of measurement methods. Empirical section consists of standardization of Five Facets Mindfulness Questionnaire for the Czech population and verification of its factor model. Further I monitored the relation of mindfulness to chosen demographic variables. Results showed modestly significant correlation with age and education, and independence of sex and overall mindfulness score. In four subscales of the questionnaire, however, sexes differed. The hypothesis that mindfulness is related to profession was also confirmed. Highest mindfulness scores were reached by helping professions, especially psychotherapists, lowest scores were reached by technical professions. Next, results confirmed the hypothesis about relation between mindfulness and life satisfaction (cognitive...
|
84 |
Survavibility in Multilayer Networks : models and Polyhedra / Sécurisation de réseaux multicouches : modèles et polyèdresTaktak, Raouia 04 July 2013 (has links)
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.
|
85 |
Gestion de l’hétérogénéité d’un SI de classification documentaire multifacette et positionnement dans l’environnement des ECM. / Management of heterogeneity of a documentary multifaceted classification Information System and position in the ECM environment.Ankoud, Manel 19 December 2014 (has links)
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.
|
86 |
Erschließungsdaten besser nutzenWiesenmüller, Heidrun, Pfeffer, Magnus 22 December 2011 (has links) (PDF)
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.
|
87 |
Mixed n-Step MIR Inequalities, n-Step Conic MIR Inequalities and a Polyhedral Study of Single Row Facility Layout ProblemSanjeevi, Sujeevraja 2012 August 1900 (has links)
In this dissertation, we introduce new families of valid inequalities for general linear mixed integer programs (MIPs) and second-order conic MIPs (SOCMIPs) and establish several theoretical properties and computational effectiveness of these inequalities.
First we introduce the mixed n-step mixed integer rounding (MIR) inequalities for a generalization of the mixing set which we refer to as the n-mixing set. The n-mixing set is a multi-constraint mixed integer set in which each constraint has n integer variables and a single continuous variable. We then show that mixed n-step MIR can generate multi-row valid inequalities for general MIPs and special structure MIPs, namely, multi- module capacitated lot-sizing and facility location problems. We also present the results of our computational experiments with the mixed n-step MIR inequalities on small MIPLIB instances and randomly generated multi-module lot-sizing instances which show that these inequalities are quite effective.
Next, we introduce the n-step conic MIR inequalities for the so-called polyhedral second-order conic (PSOC) mixed integer sets. PSOC sets arise in the polyhedral reformulation of SOCMIPs. We first introduce the n-step conic MIR inequality for a PSOC set with n integer variables and prove that all the 1-step to n-step conic MIR inequalities are facet-defining for the convex hull of this set. We also provide necessary and sufficient conditions for the PSOC form of this inequality to be valid. Then, we use the aforementioned n-step conic MIR facet to derive the n-step conic MIR inequality for a general PSOC set and provide conditions for it to be facet-defining. We further show that the n-step conic MIR inequality for a general PSOC set strictly dominates the n-step MIR inequalities written for the two linear constraints that define the PSOC set. We also prove that the n-step MIR inequality for a linear mixed integer constraint is a special case of the n-step conic MIR inequality.
Finally, we conduct a polyhedral study of the triplet formulation for the single row facility layout problem (SRFLP). For any number of departments n, we prove that the dimension of the triplet polytope (convex hull of solutions to the triplet formulation) is n(n - 1)(n - 2)/3. We then prove that several valid inequalities presented in Amaral (2009) for this polytope are facet-defining. These results provide theoretical support for the fact that the linear program solved over these valid inequalities gives the optimal solution for all instances studied by Amaral (2009).
|
88 |
Développement de formulations intégrales de volume en magnétostatique / Development of magnetostatic volume integral formulationsLe Van, Vinh 14 December 2015 (has links)
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.
|
89 |
Gestion de l’hétérogénéité d’un SI de classification documentaire multifacette et positionnement dans l’environnement des ECM. / Management of heterogeneity of a documentary multifaceted classification Information System and position in the ECM environment.Ankoud, Manel 19 December 2014 (has links)
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.
|
90 |
Connaissance inter-entreprises et optimisation combinatoire / Inter-companies knowledge and combinatorial optimizationOuld Mohamed Lemine, Mohamed 17 June 2014 (has links)
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.
|
Page generated in 0.029 seconds