41 
Symmetries and Distances : two intriguing challenges in Mathematical Programming / Symétries et Distances : deux défis fascinants dans la programmation mathématiqueDias da Silva, Gustavo 24 January 2017 (has links)
Cette thèse est consacrée à l’étude et à la discussion de deux questions importantes qui se posent dans le domaine de la Programmation Mathématique: les symétries et les distances. En arrièreplan, nous examinons la Programmation Semidéfinie (PSD) et sa pertinence comme l’un des principaux outils employés aujourd’hui pour résoudre les Programmes Mathématiques (PM) durs. Après le chapitre introductif, nous discutons des symétries au Chapitre 2 et des distances au Chapitre 5. Entre ces deux chapitres, nous présentons deux courts chapitres que nous préférons en fait appeler entr’actes: leur contenu ne mérite pas d’être publié pour le moment, mais ils fournissent un lien entre les deux Chapitres 2 et 5 apparemment distincts, qui contiennent les principales contributions de cette thèse. Il est bien connu que les PMs symétriques sont plus difficiles à résoudre pour l’optimalité globale en utilisant des algorithmes du type BranchandBound (B&B). Il est également bien connu que certaines des symétries de solution sont évidentes dans la formulation, ce qui permet d’essayer de traiter les symétries en tant qu’étape de prétraitement. L’une des approches les plus simples consiste à rompre les symétries en associant les Contraintes de Rupture de Symétrie (CRS) à la formulation, en supprimant ainsi des optima globaux symétriques, puis à résoudre la reformulation avec un solveur générique. Ces contraintes peuvent être générés à partir de chaque orbite de l’action des symétries sur l’ensemble des indices des variables. Cependant, il est difficile de savoir si et comment il est possible de choisir deux ou plus orbites distinctes pour générer des CRSs qui sont compatibles les unes avec les autres (elles ne rendent pas tous les optima globaux infaisables). Dans le Chapitre 2, nous discutons et testons un nouveau concept d’Indépendance Orbitale (IO) qui clarifie cette question. Les expériences numériques réalisées à l’aide de PLMEs et de PNLMEs soulignent l’exactitude et l’utilité de la théorie de l’IO. Programmation Quadratique Binaire (PQB) est utilisée pour étudier les symétries et SDP dans Entr'acte 3. Programmes quadratiques binaires symétriques ayant une certaine structure de symétrie sont générés et utilisés pour illustrer les conditions dans lesquelles l'utilisation de CRSs est avantageuse. Une discussion préliminaire sur l'impact des symétries et des CRSs dans la performance des solveurs PSD est également réalisée. Le Problème Euclidien de l'Arbre de Steiner est étudié dans Entr'acte 4. Deux modèles sont dérivés, ainsi que des relaxations SDP. Un algorithme heuristique basé à la fois sur les modèles mathématiques et sur les principes d'IO présentés au Chapitre 2 est également proposé. Concernant ces méthodes, des résultats préliminaires sur un petit ensemble d'exemples bien connus sont fournis. Finalement, dans le Chapitre 5, nous abordons le problème fondamental qui se pose dans le domaine de la Géométrie de Distance: il s’agit de trouver une réalisation d’un graphe pondéré non orienté dans RK pour un certain K donné, de sorte que les positions pour les sommets adjacents respectent la distance donnée par le poids de l’arête correspondante. Le Problème de la Géométrie de Distance Euclidienne (PGDE) est d’une grande importance car il a de nombreuses applications en science et en ingénierie. Il est difficile de calculer numériquement des solutions, et la plupart des méthodes proposées jusqu’à présent ne sont pas adaptées à des tailles utiles ou sont peu susceptibles d’identifier de bonnes solutions. La nécessité de contraindre le rang de la matrice représentant des solutions réalisables du PGDE rend le problème si difficile. Nous proposons un algorithme heuristique en deux étapes basé sur la PSD (en fait basé sur le paradigme de la PDD) et la modélisation explicite de Contraintes de Rang. Nous fournissons tests informatiques comprenant des instances générées de façon aléatoire ainsi que des exemples réalistes de conformation de protéines. / This thesis is mostly dedicated to study and discuss two important challenges existing not only in the field of Mathematical Programming: symmetries and distances. In the background we take a look into Semidefinite Programming (SDP) and its pertinency as one of the major tools employed nowadays to solve hard Mathematical Programs (MP). After the introductory Chapter 1, we discuss about symmetries in Chapter 2 and about distances in Chapter 5. In between them we present two short chapters that we actually prefer to call as entr’actes: their content is not necessarily worthy of publication yet, but they do provide a connection between the two seemingly separate Chapters 2 and 5, which are the ones containing the main contributions of this thesis. It is widely known that symmetric MPs are harder to solve to global optimality using BranchandBound (B&B) type algorithms, given that the solution symmetry is reflected in the size of the B&B tree. It is also wellknown that some of the solution symmetries are usually evident in the formulation, which makes it possible to attempt to deal with symmetries as a preprocessing step. Implementationwise, one of the simplest approaches is to break symmetries by adjoining SymmetryBreaking Constraints (SBC) to the formulation, thereby removing some symmetric global optima, then solve the reformulation with a generic solver. Sets of such constraints can be generated from each orbit of the action of the symmetries on the variable index set. It is unclear, however, whether and how it is possible to choose two or more separate orbits to generate SBCs which are compatible with each other (in the sense that they do not make all global optima infeasible). In Chapter 2 we discuss and test a new concept of Orbital Independence (OI) that clarifies this issue. The numerical experiences conducted using public MILPs and MINLPs emphasize the correctness and usefulness of the OI theory. Binary Quadratic Programming (BQP) is used to investigate symmetries and SDP in Entr'acte 3. Symmetric Binary Quadratic Programs having a certain symmetry structure are generated and used to exemplify the conditions under which the usage of SBCs is majoritarily advantageous. A preliminary discussion about the impact of symmetries and SBCs in the performance of SDP solvers is also carried out. The Euclidean Steiner Tree Problem is studied in Entr'acte 4. Two models (which are exact reformulations of an existing formulation) are derived, as well as SDP relaxations. A heuristic algorithm based on both the mathematical models and the OI principles presented in Chapter 2 is also proposed. As concerns these methods, preliminary results on a small set of wellknown instances are provided. Finally and following up the Distance Geometry subject, in Chapter 5 we cope with the most fundamental problem arising in the field of Distance Geometry, the one of realizing graphs in Euclidean spaces: it asks to find a realization of an edgeweighted undirected graph in RK for some given K such that the positions for adjacent vertices respect the distance given by the corresponding edge weight. The Euclidean Distance Geometry Problem (EDGP) is of great importance since it has many applications to science and engineering. It is notoriously difficult to solve computationally, and most of the methods proposed so far either do not scale up to useful sizes, or unlikely identify good solutions. In fact, the need to constrain the rank of the matrix representing feasible solutions of the EDGP is what makes the problem so hard. Intending to overcome these issues, we propose a twosteps heuristic algorithm based on SDP (or more precisely based on the very recent Diagonally Dominant Programming paradigm) and the explicitly modeling of Rank Constraints. We provide extensive computational testing against randomly generated instances as well as against feasible realistic protein conformation instances taken from the Protein Data Bank to analyze our method.

42 
High Assurance Models for Secure SystemsAlmohri, Hussain 08 May 2013 (has links)
Despite the recent advances in systems and network security, attacks on large enterprise networks consistently impose serious challenges to maintaining data privacy and software service integrity. We identify two main problems that contribute to increasing the security risk in a networked environment: (i) vulnerable servers, workstations, and mobile devices that suffer from vulnerabilities, which allow the execution of various cyber attacks, and, (ii) poor security and system configurations that create loopholes used by attackers to bypass implemented security defenses.
Complex attacks on large networks are only possible with the existence of vulnerable intermediate machines, routers, or mobile devices (that we refer to as network components) in the network. Vulnerabilities in highly connected servers and workstations, that compromise the heart of today's networks, are inevitable. Also, modern mobile devices with known vulnerabilities cause an increasing risk on large networks. Thus, weak security mechanisms in vulnerable network components open the possibilities for effective network attacks
On the other hand, lack of systematic methods for an effective static analysis of an overall complex network results in inconsistent and vulnerable configurations at individual network components as well as at the network level. For example, inconsistency and faults in designing firewall rules at a host may result in enabling more attack vector. Further, the dynamic nature of networks with changing network configurations, machine availability and connectivity, make the security analysis a challenging task
This work presents a hybrid approach to security by providing two solutions for analyzing the overall security of large organizational networks, and a runtime framework for protecting individual network components against misuse of system resources by cyber attackers. We observe that to secure an overall computing environment, a static analysis of a network is not sufficient. Thus, we couple our analysis with a framework to secure individual network components including high performance machines as well as mobile devices that repeatedly enter and leave networks. We also realize the need for advancing the theoretical foundations for analyzing the security of large networks.
To analyze the security of large enterprise network, we present the first scientific attempt to compute an optimized distribution of defensive resources with the objective of minimizing the chances of successful attacks. To achieve this minimization, we develop a rigorous probabilistic model that quantitatively measures the chances of a successful attack on any network component. Our model provides a solid theoretical foundation that enables efficient computation of unknown success probabilities on every stage of a network attack. We design an algorithm that uses the computed attack probabilities for optimizing security configurations of a network. Our optimization algorithm uses state of the art sequential linear programming to approximate the solution to a complex single objective nonlinear minimization problem that formalizes various attack steps and candidate defenses at the granularity of attack stages.
To protect individual network components, we develop a new approach under our novel idea of em process authentication.
We argue that to provide high assurance security, enforcing authorization is necessary but not sufficient. In fact, existing authorization systems lack a strong and reliable process authentication model for preventing the execution of malicious processes (i.e., processes that intentionally contain malicious goals that violate integrity and confidentiality of legitimate processes and data). Authentication is specially critical when malicious processes may use various system vulnerabilities to install on the system and stealthily execute without the user's consent.
We design and implement the Application Authentication (A2) framework that is capable of monitoring application executions and ensuring proper authentication of application processes. A2 has the advantage of strong security guarantees, efficient runtime execution, and compatibility with legacy applications. This authentication framework reduces the risk of infection by powerful malicious applications that may disrupt proper execution of legitimate applications, steal users' private data, and spread across the entire organizational network.
Our process authentication model is extended and applied to the Android platform. As Android imposes its unique challenges (e.g., virtualized application execution model), our design and implementation of process authentication is extended to address these challenges. Per our results, process authentication in Android can protect the system against various critical vulnerabilities such as privilege escalation attacks and drive by downloads.
To demonstrate process authentication in Android, we implement DroidBarrier. As a runtime system, DroidBarrier includes an authentication component and a lightweight permission system to protect legitimate applications and secret authentication information in the file system. Our implementation of DroidBarrier is compatible with the Android runtime (with no need for modifications) and shows efficient performance with negligible penalties in I/O operations and process creations. / Ph. D.

43 
AN ANALYTICAL FRAMEWORK FOR OPTIMAL PLANNING OF LONGTERM CARE FACILITIES IN ONTARIOZargoush, Mohsen January 2019 (has links)
Longterm care facility network in Ontario, and in Canada as a whole, encounters critical issues regarding balancing demand with capacity. Even worse, it is faced with rising demand in the coming years. Moreover, there is an urgent need to provide longterm care for patients in their own language (particularly French). This study proposes a dynamic MixedInteger Linear Programming model based on the current standing of the longterm care system in Ontario, which simultaneously optimizes the time and location of constructing new longterm care facilities, adjusting the capacity (namely, human resources and beds) of each facility dynamically, and the assignment of patients to the facilities based on their demand region, gender, language, and age group over a finite time horizon. We apply the diversitysupport constraints, based on patients’ gender and language, to save patients from loneliness and to comply with the Canadian values of providing care. Finally, we validate the model by performing a case study in Hamilton, Ontario. An extensive set of numerical analyses are explored to provide deeper insights into the whole issue. One set of such analysis is an extensive simulation study to examine the effect of distributional uncertainty in some of the input parameters on the optimal results, hence providing a much more realistic understanding of the optimization model. / Thesis / Master of Science (MSc)

44 
Delay Management in Public Transportation: Capacities, Robustness, and Integration / Anschlusssicherung im Öffentlichen Verkehr: Kapazitäten, Robustheit und IntegrationSchachtebeck, Michael 17 December 2009 (has links)
No description available.

45 
Métodos de otimização aplicados à análise de estruturas / Linear and nonlinear programming applied to structural analysisRigo, Eduardo 22 October 1999 (has links)
O Método dos Elementos Finitos quando aplicado à análise de estruturas, em sua forma usual, conduz a sistemas de equações que, no caso nãolinear, exigem algoritmos iterativos que realizam, em essência, uma linearização a cada passo de carga. Por outro lado, o Método da Energia formula o problema de análise estrutural na forma de uma minimização, podendo apresentar restrições sobre a função deslocamento, por exemplo. Nesse caso, os algoritmos de programação matemática proporcionam a maneira mais consistente para a obtenção da solução. O presente trabalho de mestrado trata, essencialmente, da aplicação das técnicas de otimização como ferramenta para a análise do comportamento nãolinear de estruturas, que pode ser decorrente de condições de vinculação. Os problemas estruturais são formulados via Método da Energia, que resulta na minimização de funções quadráticas sujeitas a um conjunto de restrições. São discutidos os métodos do tipo Gradiente, Newton e QuaseNewton, com a descrição dos seus algoritmos básicos e apresentação da regra de busca unidimensional adotada (Regra de Armijo ou Exata). Devido ao fato do Método de Newton ter apresentado uma melhor convergência em relação aos demais algoritmos estudados, optouse por combinálo com uma estratégia de conjuntos ativos para o caso de minimização com variáveis canalizadas. / The finite element method when applied to structural analysis, in its usual form, it drives the equations systems that, in the nonlinear case, they demand algorithms repetitive that accomplish, in essence, a linear programming to each load step. However, the Energy Method formulates the problem of structural analysis in the form of the minimizing, could present restrictions on the displacement function, for example. In that case, the algorithms of mathematical programming provide the most consistent way for obtaining of the solution. The present work negotiates, essentially, of the application in mathematical programming as a form to analyze the nonlinear structures behavior, that can be current of boundary conditions. The structural problems are formulated through Energy Method, that results in the mathematical programming of quadratic functions subject to a group of restrictions. The methods of the type Gradient are discussed, of Newton and QuasiNewton, with the description of its basic algorithms and presentation of the rule of search adopted unidimensional (Rule of Armijo or Exact). Due to the fact of Newton\'s Method to have presented a better convergence in relation to the other studied algorithms, it was opted for combining it with a \"strategy of the active groups\" for the case of mathematical programming with restricted variables.

46 
Internetinė matematinio programavimo ir modeliavimo sistema. Sistemos kūrimas ir testavimas / Online Mathematical Programming and Simulation System. The Implementation and Testing the SystemValčiukas, Remigijus 31 August 2012 (has links)
Šio darbo pagrindinis tikslas yra suprojektuoti ir sukurti internetinę matematinio programavimo ir modeliavimo sistemą. Šiam tikslui pasiekti buvo nagrinėjama matematinio programavimo samprata. Atlikta panašių matematinių programavimo sistemų bei matematinių funkcijų bibliotekų, skirtų įvairioms programavimo kalboms, analizė. Identifikuojamos ir nagrinėjamos problemos, kurios iškilo kuriant internetinę matematinio programavimo ir modeliavimo sistemą. Taip pat šiai sistemai parašytos testinės programos su C++, Java, Fortran programavimo kalbomis bei Netlib Repository LAPACK ir QT bibliotekomis. Sukurta sistema palyginta su Mathematica ir Scilab matematinio programavimo sistemomis. / The aim of this work is to design and develop webbased mathematical programming and simulation system. For this purpose were analyzed the concept of mathematical programming and performed analysis of similar mathematical programming systems and libraries of mathematical functions for various programming languages. Identified and analyzed the problems that arose in the development of an online mathematical programming and simulation system. Also, written test programs for created system in C++, Java, Fortran programming languages and Netlib Repository LAPACK, QT libraries. The developed system was compared with Mathematica and Scilab mathematical programming systems.

47 
Métodos de otimização aplicados à análise de estruturas / Linear and nonlinear programming applied to structural analysisEduardo Rigo 22 October 1999 (has links)
O Método dos Elementos Finitos quando aplicado à análise de estruturas, em sua forma usual, conduz a sistemas de equações que, no caso nãolinear, exigem algoritmos iterativos que realizam, em essência, uma linearização a cada passo de carga. Por outro lado, o Método da Energia formula o problema de análise estrutural na forma de uma minimização, podendo apresentar restrições sobre a função deslocamento, por exemplo. Nesse caso, os algoritmos de programação matemática proporcionam a maneira mais consistente para a obtenção da solução. O presente trabalho de mestrado trata, essencialmente, da aplicação das técnicas de otimização como ferramenta para a análise do comportamento nãolinear de estruturas, que pode ser decorrente de condições de vinculação. Os problemas estruturais são formulados via Método da Energia, que resulta na minimização de funções quadráticas sujeitas a um conjunto de restrições. São discutidos os métodos do tipo Gradiente, Newton e QuaseNewton, com a descrição dos seus algoritmos básicos e apresentação da regra de busca unidimensional adotada (Regra de Armijo ou Exata). Devido ao fato do Método de Newton ter apresentado uma melhor convergência em relação aos demais algoritmos estudados, optouse por combinálo com uma estratégia de conjuntos ativos para o caso de minimização com variáveis canalizadas. / The finite element method when applied to structural analysis, in its usual form, it drives the equations systems that, in the nonlinear case, they demand algorithms repetitive that accomplish, in essence, a linear programming to each load step. However, the Energy Method formulates the problem of structural analysis in the form of the minimizing, could present restrictions on the displacement function, for example. In that case, the algorithms of mathematical programming provide the most consistent way for obtaining of the solution. The present work negotiates, essentially, of the application in mathematical programming as a form to analyze the nonlinear structures behavior, that can be current of boundary conditions. The structural problems are formulated through Energy Method, that results in the mathematical programming of quadratic functions subject to a group of restrictions. The methods of the type Gradient are discussed, of Newton and QuasiNewton, with the description of its basic algorithms and presentation of the rule of search adopted unidimensional (Rule of Armijo or Exact). Due to the fact of Newton\'s Method to have presented a better convergence in relation to the other studied algorithms, it was opted for combining it with a \"strategy of the active groups\" for the case of mathematical programming with restricted variables.

48 
Multilevel Monte Carlo for jump processesXia, Yuan January 2013 (has links)
This thesis consists of two parts. The first part (Chapters 24) considers multilevel Monte Carlo for option pricing in finite activity jumpdiffusion models. We use a jumpadapted Milstein discretisation for constant rate cases and with the thinning method for bounded statedependent rate cases. Multilevel Monte Carlo estimators are constructed for Asian, lookback, barrier and digital options. The computational efficiency is numerically demonstrated and analytically justified. The second part (Chapter 5) deals with option pricing problems in exponential Lévy models where the increments of the underlying process can be directly simulated. We discuss several examples: Variance Gamma, Normal Inverse Gaussian and alphastable processes and present numerical experiments of multilevel Monte Carlo for Asian, lookback, barrier options, where the running maximum of the Lévy process involved in lookback and barrier payoffs is approximated using discretely monitored maximum. To analytically verify the computational complexity of multilevel method, we also prove some upper bounds on L<sup>p</sup> convergence rate of discretely monitored error for a broad class of Lévy processes.

49 
The Impact of Changes in the AgriStability Program on Crop Activities: A Farm Modeling ApproachLiu, Xuan 28 April 2015 (has links)
The objective of this thesis is to examine the impacts of changes in Canada’s AgriStability program on crop allocation, particularly the change in the payment trigger associated with the shift from Growing Forward (GF) to Growing Forward 2 (GF2). To examine whether this change could affect production decisions, and thereby potentially violate the WTO’s ‘green box’ criteria, farm management models are constructed for representative farms in six different Alberta regions. To incorporate risk and uncertainty into the farm model, I assume that, instead of maximizing overall gross margin, a farmer varies her crop activities to maximize expected utility subject to technological and market constraints. The models are calibrated using positive mathematical programming (PMP), which then facilitates their use for policy analysis; however, PMP is not straightforward in the case of expected utility maximization because a risk parameter also needs to be calibrated. Possible ways to address this issue are examined. Results indicate that the initial introduction of the AgriStability program tilted farmers’ planting decisions towards crops with higher returns and greater risk, but that a change in the AgriStability payout trigger (going from GF to GF2) would not further alter landuse decisions. However, the latter shift does reduce indemnities and farmers’ expected profits. Meanwhile, increases in farmers’ aversion to risk will lead to changes in crop allocations. / Graduate / 0503 / 0508 / sheriliu@uvic.ca

50 
The Effect of Certain Modifications to Mathematical Programming Models for the TwoGroup Classification ProblemWanarat, Pradit 05 1900 (has links)
This research examines certain modifications of the mathematical programming models to improve their classificatory performance. These modifications involve the inclusion of secondorder terms and secondary goals in mathematical programming models. A Monte Carlo simulation study is conducted to investigate the performance of two standard parametric models and various mathematical programming models, including the MSD (minimize sum of deviations) model, the MIP (mixed integer programming) model and the hybrid linear programming model.

Page generated in 0.2214 seconds