No description available.

The last 15 years have seen a significant progress in the development of general purpose algorithms and software for polyhedral computation. Many polytopes of practical interest have enormous output complexity and are often highly degenerate, posing severe difficulties for known general purpose algorithms. They are, however, highly structured and attention has turned to exploiting this structure, particularly symmetry. We focus on polytopes arising from combinatorial optimization problems. In particular, we study the face lattice of the metric polytope associated with the well-known maxcut and multicommodity flow problems, as well as with finite metric spaces. Exploiting the high degree of symmetry, we provide the first complete orbitwise description of the higher layers of the face lattice of the metric polytope for any dimension. Further computational and combinatorial issues are presented. / Thesis / Master of Applied Science (MASc)

The question of finding the optimal size for battery energy storage systems (BESS) to be used for energy arbitrage and peak shaving has gained more and more interest in recent years. This is due to the increase in variability of electricity prices caused by the increase of renewable but also variable electricity production units in the electricity grid. The problem of finding the optimal size for a BESS is of high complexity. It includes many factors that affect the usefulness and the economic value of a BESS. This study includes a thorough literature study regarding different methods and techniques used for finding optimal size (both capacity and power) for a BESS. From the literature study two meta-heuristic algorithms were found to have been used with success for similar problems. The two algorithms were Genetic algorithm (GA) and Firefly algorithm (FF). These algorithms have in this thesis been tested in a case study optimizing the BESS capacity and power to either maximising the net present value (NPV) of investing in a Li-ion BESS of the LPF type or minimizing the levelized cost of storage (LCOS) for the BESS, with a project lifetime of 10 years. The BESS gains monetary value from energy arbitrage by being a middleman between a large residential house complex seen as the "user" with a predefined hourly electricity load demand and the electricity grid. For the case study a simplified charge and discharge dispatch schedule was implemented for the BESS with the focus of maximising the value of energy arbitrage. The case study was divided into 3 different cases, the base case where no instalment of a BESS was done. Case 2 included the instalment of the BESS whilst case 3 included installing both a BESS and an electrical heater (ELH). The electrical heater in case 3 was implemented to shift a heating load from the user to an electrical load, to save money as well as reduce CO2 emissions from a preinstalled gas heater used in the base case. The results showed that overall GA was a better optimization algorithm for the stated problem, having lower optimization time overall between 60%-70% compared to FF and depending on the case. For case 2, GA achieves the best LCOS with a value of 0.225 e/kWh, being 11.4% lower compared to using FF. Regarding NPV for case 2, FF achieves the best solutions at the lowest possible value in the search space for the capacity and power (i.e., 0.1 kWh for capacity and 0.1 kW for power), with an NPV at -51.5e, showing that for case 2 when optimizing for NPV an investment in a BESS is undesirable. GA finds better solutions for case 3 for both NPV and LCOS at 954,982e and 0.2305 e/kWh respectively, being 35.7% larger and 9.1% lower respectively compared to using FF. For case 3 it was shown that the savings from installing the ELH stands for a large portion of the profits, leading to a positive NPV compared to case 2 when it was not implemented. Finally, it was found that the GA can be a useful tool for finding optimal power and capacity for BESS instalments, compared to FF that got stuck at local optimums. However, it was seen that the charge and discharge dispatch schedule play an important role regarding the effectiveness of installing a BESS. As for some cases the BESS was only used 17% of all hours during a year (case 2, when optimizing for NPV). Therefore, further research is of interest into the schedule function and its role regarding finding the optimal BESS size. / Frågan angående hur man hittar den optimal storleken på en energilagringsenhet av batteritypen (BESS) som skall användas för energiarbitrage samt "peak shaving" har fått mer och mer uppmärksamhet de senaste åren. Detta sker på grund av en ökning av variabiliteten av elpriser, vilket i sig delvis kommer från ett ökat installerande av förnyelsebar, men då också variabla energiproduktionsenheter till elnätet. Problemet med att hitta den optimala storleken för en BESS är på grund av komplexitet i frågan. Det innehåller många faktorer som påverkar effektiviteten samt det ekonomiska värdet av en BESS. Denna avhandling innehåller en litteraturstudie om olika tekniker och metoder som används för att hitta den optimal lösningen för optimal storlek (kapacitet och kraft) på en BESS. Från litteraturstudien hittades två meta-heuristiska algoritmer som använts med succés på liknande problem. De två algoritmerna var "Genetic algorithm" (GA) och "Firefly algorithm (FF). Dessa algoritmer har i denna avhandling blivit testade i en fallstudie för att optimera kapacitet och kraft för en BESS genom att antingen maximera nettonuvärdet (NPV) som fås av att investera i en Li-ion BESS av typen LPF eller att minimera "levelized cost of storage" (LCOE) för en BESS med en livstid på 10 år. Detta genom att man får monetärt värde från att använda en BESS för energiarbitrage genom att vara en mellanhand mellan ett stort bostadskomplex som ses vara en "användare" med ett förbestämt elanvändningsmönster och elnätet. För fallstudien användes en simpel metodologi för laddnings- och urladdninsgschema för att maximera energiarbitrage. Fallstudien delades upp i tre olika fall, ett basfall där ingen installation av en BESS gjordes. I fall 2 installerades bara en BESS medans för fall 3 installerades både en BESS samt en elektrisk värmare (ELH) för att omvandla användarens termiska energianvändning till mer elektrisk energianvändning. Genom detta kan monetära besparingar göras samt reducera mängden CO2 utsläpp som annars hade kommit från en redan installerade gasvärmare, i basfallet.  Resultatet visade att totalt sätt var GA en bättre optimeringsalgoritm för det specifika problemet, med lägre optimeringstid på 60%-70% jämfört med FF och beroende på fall. För fall 2 hittar GA det lägsta värdet på LCOS på 0.225 e/kWh, och var då 11.4% lägre jämfört med FF. Angående NPV för fall 2 hittar FF den bästa lösningen på det minsta möjliga värdet på kraft och kapacitet i sökutrymmet (det vill säga 0.1 kWh för kapacitet och 0.1 kW för kraft), med ett NPV värde på -51.5e, vilket visar att för fall 2 när man optimerar för NPV så finns ingen ekonomisk vinning av att investera i en BESS. GA hittar den bästa lösningen för fall 3, både för NPV och LCOS på 954,982e och 0.2305 e/kWh respektivt, vilket är 35.7% större och 9.1% lägre respektivt jämfört när man använder FF. För fall 3 visade resultaten att besparingarna från att installera en ELH stod för den större delen av alla vinster, vilket ledde till positiva värden för NPV. Slutligen visade resultaten att GA kan vara ett användbart verktyg för att hitta den optimala lösningen för storleken på en BESS, jämfört med FF som fastande på lokal optimala lösningar. Dock kunde resultaten också visa att laddnings- och urladdninsgschemat använt i fallstudien spelade en viktig roll angående effektiviteten med att installera en BESS. I vissa fall så användes BESS:en så lite som 17% av alla timmar på ett år (fall 2, optimering av NPV). Därför är det ett stort intresse att göra fortsatt forskning på andra laddnings- och urladdninsgscheman och dess roll med att hitta en optimal storlek på en BESS.

No / This paper presents a novel approach for probabilistic clustering, motivated by a real-world problem of modelling driving behaviour. The main aim is to establish clusters of drivers with similar journey behaviour, based on a large sample of historic journeys data. The proposed approach is to establish similarity between driving behaviours by using the Kullback-Leibler and Jensen-Shannon divergence metrics based on empirical multi-dimensional probability density functions. A graph-clustering algorithm is proposed based on modifications of the Markov Cluster algorithm. The paper provides a complete mathematical formulation, details of the algorithms and their implementation in Python, and case study validation based on real-world data.

With the onset of large-scale gene expression profiling, many researchers have turned their attention toward biological process modeling and system identification. The abundance of data available, while inspiring, is also daunting to interpret. Following the initial work of Rangel et al., we propose a linear model for identifying the biological model behind the data and utilize a modification of the Expectation-Maximization algorithm for training it. With our model, we explore some commonly accepted assumptions concerning sampling, discretization, and state transformations. Also, we illuminate the model complexities and interpretation difficulties caused by unknown state transformations and propose some solutions for resolving these problems. Finally, we elucidate the advantages and limitations of our linear state-space model with simulated data from several nonlinear networks. / Master of Science

Previous attempts to adapt MIMO systems in the presence of varying channel conditions typically focus on characterizing the performance of a limited and predefined set of joint MoDem/CoDec and MIMO configurations over a representative set of channel realizations. Other work has attempted to adapt only the MIMO scheme to varying channel conditions without considering modulation format or the channel code used. Finally, attempts to configure the system through direct BER calculation based on channel conditions were also proposed. These methods suffer the problems of dependence on a limited set of simulated curves which may not account for all channel conditions that a real system might see, not configuring all parameters jointly or implicitly requiring channel state information to be fed back to the transmitter. None of these previous attempts have handled both cases where CSIT is available or not while jointly configuring the MoDem, CoDec and multi-antenna scheme. This work consists of two parts, focusing on energy efficiency in the presence of unoccupied frequency bands and on spectrally efficient operation under static frequency assignment. Utilizing minimum Euclidean distances of MoDem constellations and the minimum free Hamming distance metrics for channel codes, we develop distance metrics to describe the MIMO schemes which are considered. A minimum required distance is then determined as a function of desired BER and constellation. Based on the unified set of distance metrics, adaptive algorithms can evaluate the total distance of a signaling scheme, including MoDem, CoDec and MIMO scheme, and then calculate a decision metric based on the total distance and the required distance to meet the desired BER. The proposed system which aims to maximize energy efficiency is able to choose, based on spatial correlation, available channels, CSIT availability, and power amplifier configuration, the appropriate multi-antenna configuration, MoDem and Codec to meet a fixed throughput requirement while maximizing the energy efficiency or robustness of the link. The proposed work assumes that the open channels of a network can be accessed through individually tunable RF chains of the multi-antenna systems. This assumption permits the use of a multi-antenna, multi-channel scheme which sacrifices spatial diversity for frequency diversity. In addition to traditional, single-channel transmit diversity schemes, the adaptive system is also able choose, when more energy efficient, this novel, multi-channel configuration. When focusing on the maximization of spectral efficiency, a more conventional, single-channel model is assumed. In addition to the distance metrics for single-channel diversity schemes, distance metrics are then developed for spatial multiplexing schemes which take into account the interaction of spatial correlation, number of antennas and the rate of the channel code. The adaptive system uses the total distance of the joint configuration of MoDem, CoDec and MIMO scheme to calculate a decision metric which indicates whether the configuration will meet the desired BER. From a list of joint configurations which will meet the desired BER, the adaptive system then chooses the one which maximizes the spectral efficiency. / Master of Science

This work examines a straightforward solution to a problem of satellite network resource allocation by exploring the application of an optimal algorithm to a subset of the general scheduling problem. Making some basic simplifications, such as the limitation of the mission scenarios to Low Earth Orbiting satellites, allows the effective application of the rigorous methods of the Greedy Activity-Selector algorithm. Tools such as Analytical Graphic's Satellite Tool Kit and MATLAB 5.0 are integrated to assist in the implementation of the algorithm. Several examples are presented in order to illustrate the effectiveness of the process. / Master of Science

Current research suggests that by actively involving students, you can increase pedagogical value of algorithm visualizations. We believe that a pedagogically successful visualization, besides actively engaging participants, also requires certain other key features. We compared several existing algorithm visualizations for the purpose of identifying features that we believe increase the pedagogical value of an algorithm visualization. To identify the most important features from this list, we conducted two experiments using a variety of the heapsort algorithm visualizations. The results of these experiments indicate that the single most important feature is the ability to control the pace of the visualization. Providing a good data set that covers all the special cases is important to help students comprehend an unfamiliar algorithm. An algorithm visualization having minimum features that focuses on the logical steps of an algorithm is sufficient for procedural understanding of the algorithm. To have better conceptual understanding, additional features (like an activity guide that makes students cover the algorithm in detail and analyze what they are doing, and pseudocode display of an algorithm) may prove to be helpful, but that is a much harder effect to detect. / Master of Science

Many technologically important problems are coupled in nature. For example, blood flow in deformable arteries, flow past (flexible) tall buildings, coupled deformation-diffusion, degradation, etc. It is, in general, not possible to solve these problems analytically, and one needs to resort to numerical solutions. An important ingredient of a numerical framework for solving these problems is the coupling algorithm, which couples individual solvers of the subsystems that form the coupled system, to obtain the coupled response. A popular coupling algorithm widely employed in numerical simulations of such coupled problems is the conventional staggered scheme (CSS). However, there is no systematic study on the stability characteristics of the CSS. The stability of coupling algorithms is of utmost importance, and assessment of the stability on real problems is not feasible given the computational costs involved. The main aim of this thesis, is to address this issue - assess the accuracy and stability characteristics of CSS using various canonical problems. In this thesis we show that the stability of CSS depends on the relative sizes of the domain, disparity in material properties, and the time step.

As DNA sequence information becomes increasingly available, researchers are now tackling the great challenge of characterizing and identifying peptides and proteins from complex mixtures. Automatic database searching algorithms have been developed to meet this challenge. This dissertation is aimed at improving these algorithms to achieve more accurate and efficient peptide and protein identification with greater confidence by incorporating peak intensity information and peptide cleavage patterns obtained in gas-phase ion dissociation research. The underlying hypothesis is that these algorithms can benefit from knowledge about molecular level fragmentation behavior of particular amino acid residues or residue combinations.SeQuence IDentification (SQID), developed in this dissertation research, is a novel Bayesian learning-based method that attempts to incorporate intensity information from peptide cleavage patterns in a database searching algorithm. It directly makes use of the estimated peak intensity distributions for cleavage at amino acid pairs, derived from probability histograms generated from experimental MS/MS spectra. Rather than assuming amino acid cleavage patterns artificially or disregarding intensity information, SQID aims to take advantage of knowledge of observed fragmentation intensity behavior. In addition, SQID avoids the generation of a theoretical spectrum predication for each candidate sequence, needed by other sequencing methods including SEQUEST. As a result, computational efficiency is significantly improved.Extensive testing has been performed to evaluate SQID, by using datasets from the Pacific Northwest National Laboratory, University of Colorado, and the Institute for Systems Biology. The computational results show that by incorporating peak intensity distribution information, the program's ability to distinguish the correct peptides from incorrect matches is greatly enhanced. This observation is consistent with experiments involving various peptides and searches against larger databases with distraction proteins, which indirectly verifies that peptide dissociation behaviors determine the peptide sequencing and protein identification in MS/MS. Furthermore, testing SQID by using previously identified clusters of spectra associated with unique chemical structure motifs leads to the following conclusions: (1) the improvement in identification confidence is observed with a range of peptides displaying different fragmentation behaviors; (2) the magnitude of improvement is in agreement with the peptide cleavage selectivity, that is, more significant improvements are observed with more selective peptide cleavages.