Notre objectif dans cette thèse est de proposer des algorithmes efficaces pour résoudre des problèmes d’optimisation combinatoire difficiles. Dans un premier temps, nous établissons le principe de l’énumération ordonnée qui consiste à générer dans un ordre adéquat les solutions d’un problème relâché associé au problème principal jusqu’à l’obtention de la preuve d’optimalité d’une solution. Nous construisons une procédure générique dans le cadre général des problème d’optimisation combinatoire. Dans un second temps nous abordons les applications de notre algorithme sur des problèmes qui admettent le problème d’affectation comme relaxation. Le premier cas particulier que nous étudions est la recherche d’une solution de bon compromis pour le problème d’affectation multiobjectif. La seconde application se rapporte au problème du voyageur de commerce asymétrique qui présente la difficulté de comporter des contraintes qui interdisent les sous-tournées, en plus des contraintes du problème d’affectation. / Our aim in this thesis is to propose efficient algorithms for solving difficult combinatorial optimization problems. Our algorithms are based on a generic method of ordered enumeration. Initially, we describe the principle of ordered enumeration which consists in generating in a specific order solutions of a relaxed problem associated to the difficult main problem, until meeting a proof of the optimality of a feasible solution. We construct a generic procedure in the general context of combinatorial optimization problems. In a second step we discuss applications of our algorithm on some difficult problems which admit the assignment problem as relaxation. The first special case we study is the search for a compromise solution to the multiobjective assignment problem. The second application is the asymmetric travelling salesman problem, which contains sub-tour constraints in addition to the constraints of the assignment problem.

Ziel dieser Arbeit ist es, die Entwicklung von RDF-Wissensbasen in verteilten kollaborativen Szenarien zu unterstützen. In dieser Arbeit wird eine neue Methodik für verteiltes kollaboratives Knowledge Engineering – „Quit“ – vorgestellt. Sie geht davon aus, dass es notwendig ist, während des gesamten Kooperationsprozesses Dissens auszudrücken und individuelle Arbeitsbereiche für jeden Mitarbeiter bereitzustellen. Der Ansatz ist von der Git-Methodik zum kooperativen Software Engineering inspiriert und basiert auf dieser. Die Analyse des Standes der Technik zeigt, dass kein System die Git-Methodik konsequent auf das Knowledge Engineering überträgt. Die Hauptmerkmale der Quit-Methodik sind unabhängige Arbeitsbereiche für jeden Benutzer und ein gemeinsamer verteilter Arbeitsbereich für die Zusammenarbeit. Während des gesamten Kollaborationsprozesses spielt die Data-Provenance eine wichtige Rolle. Zur Unterstützung der Methodik ist der Quit-Stack als eine Sammlung von Microservices implementiert, die es ermöglichen, die Semantic-Web-Datenstruktur und Standardschnittstellen in den verteilten Kollaborationsprozess zu integrieren. Zur Ergänzung der verteilten Datenerstellung werden geeignete Methoden zur Unterstützung des Datenverwaltungsprozesses erforscht. Diese Managementprozesse sind insbesondere die Erstellung und das Bearbeiten von Daten sowie die Publikation und Exploration von Daten. Die Anwendung der Methodik wird in verschiedenen Anwendungsfällen für die verteilte Zusammenarbeit an Organisationsdaten und an Forschungsdaten gezeigt. Weiterhin wird die Implementierung quantitativ mit ähnlichen Arbeiten verglichen. Abschließend lässt sich feststellen, dass der konsequente Ansatz der Quit-Methodik ein breites Spektrum von Szenarien zum verteilten Knowledge Engineering im Semantic Web ermöglicht.:Preface by Thomas Riechert Preface by Cesare Pautasso 1 Introduction 2 Preliminaries 3 State of the Art 4 The Quit Methodology 5 The Quit Stack 6 Data Creation and Authoring 7 Publication and Exploration 8 Application and Evaluation 9 Conclusion and Future Work Bibliography Web References List of Figures List of Tables List of Listings List of Definitions and Acronyms List of Namespace Prefixes / The aim of this thesis is to support the development of RDF knowledge bases in a distributed collaborative setup. In this thesis, a new methodology for distributed collaborative knowledge engineering – called Quit – is presented. It follows the premise that it is necessary to express dissent throughout a collaboration process and to provide individual workspaces for each collaborator. The approach is inspired by and based on the Git methodology for collaboration in software engineering. The state-of-the-art analysis shows that no system is consequently transferring the Git methodology to knowledge engineering. The key features of the Quit methodology are independent workspaces for each user and a shared distributed workspace for the collaboration. Throughout the whole collaboration process data provenance plays an important role. To support the methodology the Quit Stack is implemented as a collection of microservices, that allow to integrate the Semantic Web data structure and standard interfaces with the distributed collaborative process. To complement the distributed data authoring, appropriate methods to support the data management process are researched. These management processes are in particular the creation and authoring of data as well as the publication and exploration of data. The application of the methodology is shown in various use cases for the distributed collaboration on organizational data and on research data. Further, the implementation is quantitatively compared to the related work. Finally, it can be concluded that the consequent approach followed by the Quit methodology enables a wide range of distributed Semantic Web knowledge engineering scenarios.:Preface by Thomas Riechert Preface by Cesare Pautasso 1 Introduction 2 Preliminaries 3 State of the Art 4 The Quit Methodology 5 The Quit Stack 6 Data Creation and Authoring 7 Publication and Exploration 8 Application and Evaluation 9 Conclusion and Future Work Bibliography Web References List of Figures List of Tables List of Listings List of Definitions and Acronyms List of Namespace Prefixes

Many senior citizens are surviving on minimal Social Security benefits and as a result, struggle with food security. Metrocrest Services in Farmers Branch, Texas, a suburb of Dallas, is a non-profit organization that provides several food programs to residents of the community including some programs that are specifically tailored to the needs of senior citizens. This project was to provide Metrocrest with an assessment of the food security of their senior clientele as well as other elderly residents of the Metrocrest service area and to evaluate the current senior focused programs. The project utilized qualitative research including both Metrocrest clients and residents who were not Metrocrest clients bot whose demographics were similar. The objectives were to determine the coping skills used by senior citizens in obtaining food, to assess seniors' awareness of the programs offered by Metrocrest, to discover barriers to accessing needed resources and to make recommendations of how programs could be improved or modified if needed. Through my research, I was able to present Metrocrest with a number of recommendations to improve their existing programs. I was also able to recommend some potential new programs that could be designed in conjunction with local senior centers to better serve the community.

Dans un graphe non orienté, le problème du sous-graphe k-sommet connexe consiste à déterminer un sous-graphe de poids minimum tel que entre chaque paires de sommets, il existe k chemins sommet-disjoints. Ce modèle a été étudié dans la littérature en termes d'arête connexité. Cependant, le cas de la sommet connexité n'a pas été traité jusqu'à présent. Nous décrivons de nouvelles inégalités valides et nous présentons un algorithme de Coupes et Branchements ainsi qu'une large étude expérimentale qui montrent l'efficacité des contraintes utilisées. Nous proposons ensuite une formulation étendue pour le même problème pour une connexité k=2, suivi d'un algorithme de Génération de Colonnes et Branchements pour résoudre cette formulation.Nous étudions ensuite la version avec chemins bornés du problème. Le problème consiste à trouver un sous-graphe de poids minimum, tel que entre chaque paire d'origine-destination, il existe k chemins sommet-disjoints de longueur au plus L. Nous proposons une formulation linéaire en nombres entiers pour L=2,3. Nous présentons de nouvelles inégalités valides et nous proposons des algorithmes de séparation pour ces contraintes. Nous présentons ensuite un algorithme de Coupes et Branchements qu'on a testé sur des instances de la TSPLIB. / Given a weighted undirected graph and an integer k, the k-node-connected subgraph problem is to find a minimum weight subgraph which contains k-node-disjoint paths between every pair of nodes. We introduce new classes of valid inequalities and discuss their facial aspect. We also devise separation routines, investigate the structural properties of the linear relaxation and discuss some reduction operations that can be used in a preprocessing phase for the separation. Using these results, we devise a Branch-and-Cut algorithm and present some computational results. Then we present a new extended formulation for the the k-node-connected subgraph problem, along with a Branch-and-Cut-and-Price algorithm for solving the problem.Next, we investigate the hop-constrained version of the problem. The k node-disjoint hop-constrained network design problem is to find a minimum weight subgraph such that between every origin and destination there exist at least k node-disjoint paths of length at most L. We propose an integer linear programming formulation for L=2,3 and investigate the associated polytope. We introduce valid inequalities and devise separation algorithms. Then, we propose a B\&C algorithm for solving the problem along with some computational results.

L’Optimisation Combinatoire (OC) est un domaine de recherche qui est en perpétuel changement. Résoudre un problème d’optimisation combinatoire (POC) consiste essentiellement à trouver la ou les meilleures solutions dans un ensemble des solutions réalisables appelé espace de recherche qui est généralement de cardinalité exponentielle en la taille du problème. Pour résoudre des POC, plusieurs méthodes ont été proposées dans la littérature. On distingue principalement les méthodes exactes et les méthodes d’approximation. Ne pouvant pas viser une résolution exacte de problèmes NP-Complets lorsque la taille du problème dépasse une certain seuil, les chercheurs on eu de plus en plus recours, depuis quelques décennies, aux algorithmes dits hybrides (AH) ou encore à au calcul parallèle. Dans cette thèse, nous considérons la classe POC des problèmes de conception d'un réseau fiable. Nous présentons un algorithme hybride parallèle d'approximation basé sur un algorithme glouton, un algorithme de relaxation Lagrangienne et un algorithme génétique, qui produit des bornes inférieure et supérieure pour les formulations à base de flows. Afin de valider l'approche proposée, une série d'expérimentations est menée sur plusieurs applications: le Problème de conception d'un réseau k-arête-connexe avec contrainte de borne (kHNDP) avec L=2,3, le problème de conception d'un réseau fiable Steiner k-arête-connexe (SkESNDP) et ensuite deux problèmes plus généraux, à savoir le kHNDP avec L >= 2 et le problème de conception d'un réseau fiable k-arête-connexe (kESNDP). L'étude expérimentale de la parallélisation est présentée après cela. Dans la dernière partie de ce travail, nous présentons deux algorithmes parallèles exactes: un Branch-and-Bound distribué et un Branch-and-Cut distribué. Une série d'expérimentation a été menée sur une grappe de 128 processeurs, et des accélération intéressantes ont été atteintes pour la résolution du problèmes kHNDP avec k=3 et L=3. / Combinatorial Optimization (CO) is an area of research that is in a constant progress. Solving a Combinatorial Optimization Problem (COP) consists essentially in finding the best solution (s) in a set of feasible solutions called a search space that is usually exponential in cardinality in the size of the problem. To solve COPs, several methods have been proposed in the literature. A distinction is made mainly between exact methods and approximation methods. Since it is not possible to aim for an exact resolution of NP-Complete problems when the size of the problem exceeds a certain threshold, researchers have increasingly used Hybrid (HA) or parallel computing algorithms in recent decades. In this thesis we consider the COP class of Survivability Network Design Problems. We present an approximation parallel hybrid algorithm based on a greedy algorithm, a Lagrangian relaxation algorithm and a genetic algorithm which produces both lower and upper bounds for flow-based formulations. In order to validate the proposed approach, a series of experiments is carried out on several applications: the k-Edge-Connected Hop-Constrained Network Design Problem (kHNDP) when L = 2,3, The problem of the Steiner k-Edge-Connected Network Design Problem (SkESNDP) and then, two more general problems namely the kHNDP when L >= 2 and the k-Edge-Connected Network Design Problem (kESNDP). The experimental study of the parallelisation is presented after that. In the last part of this work, we present a two parallel exact algorithms: a distributed Branch-and-Bound and a distributed Branch-and-Cut. A series of experiments has been made on a cluster of 128 processors and interesting speedups has been reached in kHNDP resolution when k=3 and L=3.

Die Tourenbildung beschäftigt sich mit der Konstruktion kostengünstiger Transportrouten zur Belieferung von Verbrauchern. Sie ist eine der weitreichensten Erfolgsgeschichten des Operations Research. Das starke Interesse an diesen Problemen durch Industrie und Forschung liegt zum einen am wirtschaftlichen Potenzial der Tourenbildung und -optimierung, zum anderen macht ihr Reichtum an Struktur sie zu einem faszinierenden Forschungsgebiet. In der vorliegenden Arbeit soll ein Überblick über einige, u. a. auch neuere mathematische Modell- und Lösungsansätze gegeben werden. Auf Grund der hohen Anzahl der Veröffentlichungen auf diesem Gebiet wird nicht zwingend ein Anspruch auf die vollständige Darlegung aller möglichen Problemstellungen im Zusammenhang mit dem TSP sowie dem VRP und deren Lösungsansätze erhoben. An den gegebenen Stellen wird statt dessen auf weiterführende Literatur verwiesen.

Indiana University-Purdue University Indianapolis (IUPUI) / The first chapter of this thesis provides the background of the Labor Branch and the OSS as a whole. From the OSS’s inception in 1942 through its postwar transformation into the Central Intelligence Agency (CIA), I cover the evolution of the foreign intelligence community in the United States. This includes sections on the politics within the OSS, the reasons the Labor Branch has not been a focal point of OSS research, and quirks about the Labor Branch that make it stand out from the rest of the OSS. The Labor Branch’s specific role in the infiltration of Germany is also discussed in chapter one. Chapter two is an extension of the materials presented in the first chapter. It focuses on a section of the Labor Branch called Bach Section. This section was devoted to making the infiltration of Germany possible by creating cover stories, forging documents, and preparing agents to go to Germany in the midst of Nazism and be able to survive, gather intelligence, and create resistance networks. The bravery, intelligence, and will of the Bach Section are clear in this chapter, and the reader will recognize that, without the Labor Branch and their colleagues at the Bach Section, no one, be they with the OSS or British intelligence, would have had much success in infiltrating Germany during World War II. My third chapter is a bit more complicated than the first two. In it, I discuss the nuances of writing historical fiction responsibly and as a viable means of public history. As guidance, I undertake a discussion of the OSS in published works of fiction. I give an overview of the way different novelists handle the bureaucracy, agents, accomplishments, and failures of the OSS, revealing what I feel each does effectively and poorly. While discussing each of the potential strengths and pitfalls of historical fiction, especially as seen in the OSS novels, I then provide real examples of how historical fiction might work with a case study involving the OSS Labor Branch. One particular OSS mission, known as the Hammer Mission, serves as my example. I detail different parts of the mission, the men who participated, their training, and the mission itself and discuss how to use these details within a novel.

The quadratic traveling salesman problem (QTSP) is an extension of the (classical) Traveling Salesman Problem (TSP) where the costs depend on each two nodes that are traversed in succession, i. e., on the edges in the symmetric (STSP) and on the arcs in the asymmetric case (ATSP). The QTSP is motivated by an application in bioinformatics. It can be used in the solution of certain Permuted Markov models that are set up for the recognition of transcription factor binding sites and of splice sites in gene regulation. Important special cases are the Angular-Metric TSP used in robotics and the TSP with Reload Costs used in the planning of telecommunication and transport networks. The SQTSP and the AQTSP can be formulated as integer optimization problems over the polytope associated with the STSP resp. ATSP together with a quadratic cost function. We study the polytopes arising from a linearization of the respective quadratic integer programming formulations. Based on the proof of the dimension of the polytopes using the so called direct method we can prove the facetness of several valid inequalities. These facets and valid inequalities can be divided into three large groups. Some are related to the Boolean quadric polytope. Furthermore we introduce the conflicting edges/arc inequalities that forbid certain configurations of edges and 2-edges resp. of arcs and 2-arcs. Finally, we strengthen valid inequalities of STSP and ATSP in order to get stronger inequalities in the quadratic case. We present two general lifting approaches. One is applicable to all inequalities with nonnegative coefficients and the second allows to strengthen clique tree inequalities. Applying these approaches to the subtour elimination constraints leads to facets in most cases, but in general facetness is not preserved. In addition, the complexity of the separation problems for some of the facet classes is studied. Finally, we present some computational results using a branch-and-cut framework, which is improved by some of the newly derived cutting planes. The tested instances from biology could be solved surprisingly well. Instances with up to 100 nodes could be solved in less than 700 seconds improving the results in the literature by several orders of magnitude. For most of the randomly generated instances using some additional separators allowed to reduce the root gaps and the numbers of nodes in the branch-and-cut tree significantly, often even the running times.

A payment is the most fundamental aspect of a trade that involves funds. In recent years, the development of new payment services has accelerated significantly as the world has moved further into the digital era. This transition has led to an increased demand of digital payment solutions that can handle trades across the world. As trades today can be agreed at any time wherever the payer and payee are located, the party that mediates payments must at any time to be available in order to mediate an agreed exchange. This requires the payment service provider to always have funds available in the required countries and currencies in order for trades to always be available. This thesis concerns how a payment service provider can reallocate capital in a cost efficient way in order for trades to always be available. Traditionally, the reallocation of capital is done in a rule-based manner, which discard the cost dimension and thereby only focus on the reallocation itself. This thesis concerns methods to optimally reallocate capital focusing on the cost of transferring capital within the network. Where the concerned methods has the potential of transferring capital in a far more cost efficient way. When mathematically formulating the reallocation decisions as an optimization problem, the cost function is formulated as a linear program with both Boolean and real constraints. This impose non-feasibility of locating the optimal solution using traditional methods for linear programs, why developed traditional and more advanced methods were used. The model was evaluated based on a large number of simulations in comparison with the performance of a rule-based reallocation system. The developed model provides a significant cost reduction compared to the rule-based approach and thereby outperforms the traditional reallocation system. Future work should focus on expanding the model by broadening the available transfer options, by increasing the considered uncertainty via a bayesian treatment and finally by considering all cost aspects of the network. / En betalning är den mest fundamentala aspekten av handel som involverar kapital. De senaste åren har utvecklingen av nya betalmedel ökat drastiskt då världen fortsatt att utvecklas genom digitaliseringen. Utvecklingen har lett till en ökad efterfrågan på digitala betalningslösningar som kan hantera handel över hela världen. Då handel idag kan ske när som helst oberoende av var betalaren och betalningsmottagaren befinner sig, måste systemet som genomför betalningen alltid vara tillgängligt för att kunna förmedla handel mellan olika parter. Detta kräver att betalningssystemet alltid måste ha medel tillgängligt i efterfrågade länder och valutor för att handeln ska kunna genomföras. Den här uppsatsen fokuserar på hur kapital kostnadseffektivt kan omallokeras i ett betalsystem för att säkerställa att handel alltid är tillgängligt. Traditionellt har omallokeringen av kapital gjorts på ett regelbaserat sätt, vilket inte tagit hänsyn till kostnadsdimensionen och därigenom enbart fokuserat på själva omallokeringen. Den här uppsatsen använder metoder för att optimalt omallokera kapital baserat på kostnaderna för omallokeringen. Därigenom skapas en möjlighet att flytta kapital på ett avsevärt mer kostnadseffektivt sätt. När omallokeringsbesluten formuleras matematiskt som ett optimeringsproblem är kostnadsfunktionen formulerad som ett linjärt program med både Booleska och reella begränsningar av variablerna. Detta gör att traditionella lösningsmetoder för linjära program inte är användningsbara för att finna den optimala lösningen, varför vidareutveckling av tradtionella metoder tillsammans med mer avancerade metoder använts. Modellen utvärderades baserat på ett stort antal simuleringar som jämförde dess prestanda med det regelbaserade systemet. Den utvecklade modellen presterar en signfikant kostnadsreduktion i jämförelse med det regelbaserade systemet och överträffar därigenom det traditionellt använda systemet. Framtida arbete bör fokusera på att expandera modellen genom att utöka de potentiella överföringsmöjligheterna, att ta ökad hänsyn till osäkerhet genom en bayesiansk hantering, samt slutligen att integrera samtliga kostnadsaspekter i nätverket.

No description available.