All possible convex hull (i.e. the minimum area convex polygon containing the planar set) algorithms ever published in scientific press have been analysed in this work. Two new convex hull algorithms created by myself have been presented. The running time of analysed algorithms has been surveyed. Three most popular algorithms (Graham Scan, Jarvis March and Quickhull), the oldest algorithm (Brute Force) as well as the both new ones have been implemented. Efficiency experiments have been carried out with them. The algorithms created by me achieved the best results. In order to raise the efficiency of all the algorithms I suggested a priori filtration of points, which decreases the amount of the original points by almost 50% and, consequently, the speed of algorithms is increased. The major part of this master work will be published in the magazine “Technological and economic development of economy”. Besides, the report of this work has been made in the conference of Lithuanian young scientists, called “Operation analysis and application”.

Šiame darbe yra trumpai aprašomi algoritmai, kurie naudoja nereikalingus skaičiavimus, ieškant iškilojo apvalkalo taškų. Pateikiamas naujas „Radaro“ algoritmas, kuris iškilojo apvalkalo taškus randa išrinkimo būdu. Pateikiamos ir trys „Radaro“ algoritmo realizacijos. Graham, Jarvi, „Radaro“ algoritmai bei „Radaro“ algoritmo trys realizacijos realizuojamos dvejais būdais: statiniais masyvais ir dinaminiais masyvais. Realizavus tris algoritmus (Graham, Jarvi, „Radaro“) ir tris „Radaro“ algoritmo realizacijas, buvo analizuojamas algoritmų atlikimo laikas. / There are shortly presented algorithms which use unnecessary calculations in order to find convex hull. In this work you can discover new “Radar” algorithm which finds convex hull by using selecting method and three ways of realization of this algorithm. Graham, Jarvi, “Radar” algorithms and three ways of realization of “Radar” algorithm are realized in two ways: static array and dynamic array. There were analyzed time needed for execution of three algorithms (Graham, Jarvi and “Radar”) and three ways of realization of “Radar” algorithm.

Cellular automata (CA) are an interesting computation medium to study because of their simplicity and inherently parallel operation. These characteristics make them a useful and efficient computation tool for applications such as cryptography and physical systems modelling, particularly when implemented on specialized parallel hardware. In this dissertation, we study a number of applications of CA and develop new theoretical results used for them. We begin by presenting conditions which guarantee that a composition of marker cellular automata has the same neighbourhood as each of the individual components. We show that, under certain technical assumptions, a marker cellular automaton has a unique inverse with a given neighbourhood. We use these results to develop a working key generation algorithm for a public-key cryptosystem based on reversible cellular automata originally conceived by Kari. We also give an improvement to a CA algorithm which solves a version of the convex hull problem, ensuring that the algorithm does not require a global rule change and correcting the operation in a special case. Finally, we study a modified version of an established CA-based car traffic flow model for the single-lane highway case, and use CA as a modelling tool to investigate the coverage problem in wireless sensor network design. We developed functional software implementations for all of these experiments. / Thesis (Master, Computing) -- Queen's University, 2009-03-23 11:20:58.666

In this Ph.D. dissertation research, we lay the mathematical foundations of various fundamental concepts in convex mixed-integer programs (MIPs), that is, optimization problems where all the decision variables belong to a given convex set and, in addition, a subset of them are required to be integer. In particular, we study properties of their feasible region and properties of cutting planes. The main contribution of this work is the extension of several fundamental results from the theory of linear MIPs to the case of convex MIPs. In the first part, we study properties of general closed convex sets that determine the closedness and polyhedrality of their integer hulls. We first present necessary and sufficient conditions for the integer hull of a general convex set to be closed. This leads to useful results for special classes of convex sets such as pointed cones, strictly convex sets, and sets containing integer points in their interior. We then present a sufficient condition for the integer hulls of general convex sets to be polyhedra. This result generalizes the well-known result due to Meyer in the case of linear MIPs. Under a simple technical assumption, we show that these sufficient conditions are also necessary for the integer hull of general convex sets to be polyhedra. In the second part, we apply the previous results to mixed-integer second order conic programs (MISOCPs), a special case of nonlinear convex MIPs. We show that there exists a polynomial time algorithm to check the closedness of the mixed integer hulls of simple MISOCPs. Moreover, in the special case of pure integer problems, we present sufficient conditions for verifying the closedness of the integer hull of intersection of simple MISOCPs that can also be checked in polynomial time. In the third part, we present an extension of the duality theory for linear MIPs to the case of conic MIPs. In particular, we construct a subadditive dual to conic MIPs. Under a simple condition on the primal problem, we are able to prove strong duality. In the fourth part, we study properties of maximal S-free convex sets, where S is a subset of integers contained in an arbitrary convex set. An S-free convex set is a convex set not containing any points of S in its interior. In this part, we show that maximal S-free convex sets are polyhedra and discuss some properties of these sets. In the fifth part, we study some generalizations of the split closure in the case of linear MIPs. Split cuts form a well-known class of valid inequalities for linear MIPs. Cook et al. (1990) showed that the split closure of a rational polyhedron - that is, the set of points in the polyhedron satisfying all split cuts - is again a polyhedron. In this thesis, we extend this result from a single rational polyhedron to the union of a finite number of rational polyhedra. We also show how this result can be used to prove that some generalizations of split cuts, namely cross cuts, also yield closures that are rational polyhedra.

In the current water resources scientific literature, a wide variety of engineering design problems are solved in a simulation-optimization framework. These problems can have single or multiple objective functions and their decision variables can have discrete or continuous values. The majority of current literature in the field of water resources systems optimization report using heuristic global optimization algorithms, including evolutionary algorithms, with great success. These algorithms have multiple parameters that control their behavior both in terms of computational efficiency and the ability to find near globally optimal solutions. Values of these parameters are generally obtained by trial and error and are case study dependent. On the other hand, water resources simulation-optimization problems often have computationally intensive simulation models that can require seconds to hours for a single simulation. Furthermore, analysts may have limited computational budget to solve these problems, as such, the analyst may not be able to spend some of the computational budget to fine-tune the algorithm settings and parameter values. So, in general, algorithm parsimony in the number of parameters is an important factor in the applicability and performance of optimization algorithms for solving computationally intensive problems. A major contribution of this thesis is the development of a highly efficient, single objective, parsimonious optimization algorithm for solving problems with discrete decision variables. The algorithm is called Hybrid Discrete Dynamically Dimensioned Search, HD-DDS, and is designed based on Dynamically Dimensioned Search (DDS) that was developed by Tolson and Shoemaker (2007) for solving single objective hydrologic model calibration problems with continuous decision variables. The motivation for developing HD-DDS comes from the parsimony and high performance of original version of DDS. Similar to DDS, HD-DDS has a single parameter with a robust default value. HD-DDS is successfully applied to several benchmark water distribution system design problems where decision variables are pipe sizes among the available pipe size options. Results show that HD-DDS exhibits superior performance in specific comparisons to state-of-the-art optimization algorithms. The parsimony and efficiency of the original and discrete versions of DDS and their successful application to single objective water resources optimization problems with discrete and continuous decision variables motivated the development of a multi-objective optimization algorithm based on DDS. This algorithm is called Pareto Archived Dynamically Dimensioned Search (PA-DDS). The algorithm parsimony is a major factor in the design of PA-DDS. PA-DDS has a single parameter from its search engine DDS. In each iteration, PA-DDS selects one archived non-dominated solution and perturbs it to search for new solutions. The solution perturbation scheme of PA-DDS is similar to the original and discrete versions of DDS depending on whether the decision variable is discrete or continuous. So, PA-DDS can handle both types of decision variables. PA-DDS is applied to several benchmark mathematical problems, water distribution system design problems, and water resources model calibration problems with great success. It is shown that hypervolume contribution, HVC1, as defined in Knowles et al. (2003) is the superior selection metric for PA-DDS when solving multi-objective optimization problems with Pareto fronts that have a general (unknown) shape. However, one of the main contributions of this thesis is the development of a selection metric specifically designed for solving multi-objective optimization problems with a known or expected convex Pareto front such as water resources model calibration problems. The selection metric is called convex hull contribution (CHC) and makes the optimization algorithm sample solely from a subset of archived solutions that form the convex approximation of the Pareto front. Although CHC is generally applicable to any stochastic search optimization algorithm, it is applied to PA-DDS for solving six water resources calibration case studies with two or three objective functions. These case studies are solved by PA-DDS with CHC and HVC1 selections using 1,000 solution evaluations and by PA-DDS with CHC selection and two popular multi-objective optimization algorithms, AMALGAM and ε-NSGAII, using 10,000 solution evaluations. Results are compared based on the best case and worst case performances (out of multiple optimization trials) from each algorithm to measure the expected performance range for each algorithm. Comparing the best case performance of these algorithms shows that, PA-DDS with CHC selection using 1,000 solution evaluations perform very well in five out of six case studies. Comparing the worst case performance of the algorithms shows that with 1,000 solution evaluations, PA-DDS with CHC selection perform well in four out of six case studies. Furthermore, PA-DDS with CHC selection using 10,000 solution evaluations perform comparable to AMALGAM and ε-NSGAII. Therefore, it is concluded that PA-DDS with CHC selection is a powerful optimization algorithm for finding high quality solutions of multi-objective water resources model calibration problems with convex Pareto front especially when the computational budget is limited.

abstract: The shortest path between two locations is important for spatial analysis, location modeling, and wayfinding tasks. Depending on permissible movement and availability of data, the shortest path is either derived from a pre-defined transportation network or constructed in continuous space. However, continuous space movement adds substantial complexity to identifying the shortest path as the influence of obstacles has to be considered to avoid errors and biases in a derived path. This obstacle-avoiding shortest path in continuous space has been referred to as Euclidean shortest path (ESP), and attracted the attention of many researchers. It has been proven that constructing a graph is an effective approach to limit infinite search options associated with continuous space, reducing the problem to a finite set of potential paths. To date, various methods have been developed for ESP derivation. However, their computational efficiency is limited due to fundamental limitations in graph construction. In this research, a novel algorithm is developed for efficient identification of a graph guaranteed to contain the ESP. This new approach is referred to as the convexpath algorithm, and exploits spatial knowledge and GIS functionality to efficiently construct a graph. The convexpath algorithm utilizes the notion of a convex hull to simultaneously identify relevant obstacles and construct the graph. Additionally, a spatial filtering technique based on intermediate shortest path is enhances intelligent identification of relevant obstacles. Empirical applications show that the convexpath algorithm is able to construct a graph and derive the ESP with significantly improved efficiency compared to visibility and local visibility graph approaches. Furthermore, to boost the performance of convexpath in big data environments, a parallelization approach is proposed and applied to exploit computationally intensive spatial operations of convexpath. Multicore CPU parallelization demonstrates noticeable efficiency gain over the sequential convexpath. Finally, spatial representation and approximation issues associated with raster-based approximation of the ESP are assessed. This dissertation provides a comprehensive treatment of the ESP, and details an important approach for deriving an optimal ESP in real time. / Dissertation/Thesis / Doctoral Dissertation Geography 2015

abstract: Two thirds of the U.S. power systems are operated under market structures. A good market design should maximize social welfare and give market participants proper incentives to follow market solutions. Pricing schemes play very important roles in market design. Locational marginal pricing scheme is the core pricing scheme in energy markets. Locational marginal prices are good pricing signals for dispatch marginal costs. However, the locational marginal prices alone are not incentive compatible since energy markets are non-convex markets. Locational marginal prices capture dispatch costs but fail to capture commitment costs such as startup cost, no-load cost, and shutdown cost. As a result, uplift payments are paid to generators in markets in order to provide incentives for generators to follow market solutions. The uplift payments distort pricing signals. In this thesis, pricing schemes in electric energy markets are studied. In the first part, convex hull pricing scheme is studied and the pricing model is extended with network constraints. The subgradient algorithm is applied to solve the pricing model. In the second part, a stochastic dispatchable pricing model is proposed to better address the non-convexity and uncertainty issues in day-ahead energy markets. In the third part, an energy storage arbitrage model with the current locational marginal price scheme is studied. Numerical test cases are studied to show the arguments in this thesis. The overall market and pricing scheme design is a very complex problem. This thesis gives a thorough overview of pricing schemes in day-ahead energy markets and addressed several key issues in the markets. New pricing schemes are proposed to improve market efficiency. / Dissertation/Thesis / Masters Thesis Electrical Engineering 2016

abstract: This research mainly focuses on improving the utilization of photovoltaic (PV) re-sources in distribution systems by reducing their variability and uncertainty through the integration of distributed energy storage (DES) devices, like batteries, and smart PV in-verters. The adopted theoretical tools include statistical analysis and convex optimization. Operational issues have been widely reported in distribution systems as the penetration of PV resources has increased. Decision-making processes for determining the optimal allo-cation and scheduling of DES, and the optimal placement of smart PV inverters are con-sidered. The alternating current (AC) power flow constraints are used in these optimiza-tion models. The first two optimization problems are formulated as quadratically-constrained quadratic programming (QCQP) problems while the third problem is formu-lated as a mixed-integer QCQP (MIQCQP) problem. In order to obtain a globally opti-mum solution to these non-convex optimization problems, convex relaxation techniques are introduced. Considering that the costs of the DES are still very high, a procedure for DES sizing based on OpenDSS is proposed in this research to avoid over-sizing. Some existing convex relaxations, e.g. the second order cone programming (SOCP) relaxation and semidefinite programming (SDP) relaxation, which have been well studied for the optimal power flow (OPF) problem work unsatisfactorily for the DES and smart inverter optimization problems. Several convex constraints that can approximate the rank-1 constraint X = xxT are introduced to construct a tighter SDP relaxation which is referred to as the enhanced SDP (ESDP) relaxation using a non-iterative computing framework. Obtaining the convex hull of the AC power flow equations is beneficial for mitigating the non-convexity of the decision-making processes in power systems, since the AC power flow constraints exist in many of these problems. The quasi-convex hull of the quadratic equalities in the AC power bus injection model (BIM) and the exact convex hull of the quadratic equality in the AC power branch flow model (BFM) are proposed respectively in this thesis. Based on the convex hull of BFM, a novel convex relaxation of the DES optimizations is proposed. The proposed approaches are tested on a real world feeder in Arizona and several benchmark IEEE radial feeders. / Dissertation/Thesis / Doctoral Dissertation Electrical Engineering 2016

Anomalias ou outliers são exemplos ou grupo de exemplos que apresentam comportamento diferente do esperado. Na prática,esses exemplos podem representar doenças em um indivíduo ou em uma população, além de outros eventos como fraudes em operações bancárias e falhas em sistemas. Diversas técnicas existentes buscam identificar essas anomalias, incluindo adaptações de métodos de classificação e métodos estatísticos. Os principais desafios são o desbalanceamento do número de exemplos em cada uma das classes e a definição do comportamento normal associada à formalização de um modelo para esse comportamento. Nesta dissertação propõe-se a utilização de um novo espaço para realizar a detecção,esse espaço é chamado espaço de parâmetros. Um espaço de parâmetros é criado utilizando parâmetros estimados a partir da concatenação(encadeamento) de dois exemplos. Apresenta-se,então,um novo framework para realizar a detecção de anomalias através da fusão de detectores que utilizam fechos convexos em múltiplos espaços de parâmetros para realizar a detecção. O método é considerado um framework pois é possível escolher quais os espaços de parâmetros que serão utilizados pelo método de acordo como comportamento da base de dados alvo. Nesse trabalho utilizou-se,para experimentos,dois conjuntos de parâmetros(média e desvio padrão; média, variância, obliquidade e curtose) e os resultados obtidos foram comparados com alguns métodos comumente utilizados para detecção de anomalias. Os resultados atingidos foram comparáveis ou melhores aos obtidos pelos demais métodos. Além disso, acredita-se que a utilização de espaços de parâmetros cria uma grande flexibilidade do método proposto, já que o usuário pode escolher um espaço de parâmetros que se adeque a sua aplicação. Tanto a flexibilidade quanto a extensibilidade disponibilizada pelo espaço de parâmetros, em conjunto como bom desempenho do método proposto nos experimentos realizados, tornam atrativa a utilização de espaços de parâmetros e, mais especificamente, dos métodos apresentados na solução de problemas de detecção de anomalias. / Anomalies or outliers are examples or group of examples that have a behaviour different from the expected. These examples may represent diseases in individuals or populations,as well as other events such as fraud and failures in banking systems.Several existing techniques seek to identify these anomalies, including adaptations of classification methods, statistical methods and methods based on information theory. The main challenges are that the number of samples of each class is unbalanced, the cases when anomalies are disguised among normal samples and the definition of normal behaviour associated with the formalization of a model for this behaviour. In this dissertation,we propose the use of a new space to helpwith the detection task, this space is called parameter space. We also present a new framework to perform anomaly detection by using the fusion of convex hulls in multiple parameter spaces to perform the detection.The method is considered a framework because it is possible to choose which parameter spaces will be used by the method according to the behaviour of the target data set.For the experiments, two parameter spaces were used (mean and standard deviation; mean, variance, skewness and kurtosis) and the results were compared to some commonly used anomaly detection methods. The results achieved were comparable or better than those obtained by the other methods. Furthermore, we believe that a parameter space created great fexibility for the proposed method, since it allowed the user to choose a parameter space that best models the application. Both the flexibility and extensibility provided by the use of parameter spaces, together with the good performance achieved by the proposed method in the experiments, make parameter spaces and, more specifically, the proposed methods appealing when solving anomaly detection problems.

Topological materials have discovered ultrahigh magnetoresistance, chiral anomalies, the inherent anomalous Hall effect, and unique Fermi arc surface states. Topological materials now include insulators, metals, and semimetals. Weyl semimetals (WSM) are topological materials that show linear dispersion with crossings in their band structure which creates the pair of Weyl nodes of opposite chirality. WSMs have topological Fermi arc surface states connecting opposing chirality Weyl nodes. Spin-orbit coupling can result in the band opening in Dirac nodal rings, and creating the pair of Weyl nodes either by breaking the time-reversal or spatial inversion symmetry (but not both) 1-3. The chirality of a Weyl node is set by the Berry flux through a closed surface in reciprocal space around it. The purpose of this thesis was to characterize and investigate the thermodynamic stability of WSM. To accomplish these goals, quantum mechanical modeling at the level of density functional theory (DFT) was used. WloopPHI, a Python module, integrates the characterization of WSMs into WIEN2k, a full-potential all-electron density functional theory package. It calculates the chirality of the Weyl node (monopole charge) with an enhanced Wilson loop method and Berry phase approach. First, TaAs, a well-characterized Weyl semimetal, validates the code theoretically. We then used the approach to characterize the newly discovered WSM YRh6Ge4, and we found a set of Weyl points into it. Further, we study the stability of the kagome-based materials A3Sn2S2, where A is Co, Rh, or Ru, in the context of the ternary phase diagrams and competing binary compounds using DFT. We demonstrated that Co3Sn2S2 and Rh3Sn2S2 are stable compounds by examining the convex hull and ternary phase diagrams. It is feasible to synthesize Co3Sn2S2 by a chemical reaction between SnS, CoSn and Co9S8. Moreover, Rh3Sn2S2 can be produced by SnS, RhSn and Rh3S4. On the other hand, we found that Ru3Sn2S2 is a thermodynamically unstable material with respect to RuS2, Ru3S7 and Ru. Our work provides some insights for confirming materials using the DFT approach. 1. S. M. Young et al. Dirac Semimetal in Three Dimensions. Physical Review Letters108(14) (2012), 140405. 2. J. Liu and D. Vanderbilt. Weyl semimetals from noncentrosymmetric topological insulators. Physical Review B 90(15) (2014), 155316. 3. H. Weng et al. Weyl Semimetal Phase in Noncentrosymmetric Transition-Metal Monophosphides. Physical Review X 5(1) (2015), 011029. / Thesis / Master of Applied Science (MASc)