Qualitative Characteristics and Quantitative Measures of Solution's Reliability in Discrete Optimization: Traditional Analytical Approaches, Innovative Computational Methods and Applicability

The purpose of this thesis is twofold. The first and major part is devoted to sensitivity analysis of various discrete optimization problems while the second part addresses methods applied for calculating measures of solution stability and solving multicriteria discrete optimization problems. Despite numerous approaches to stability analysis of discrete optimization problems two major directions can be single out: quantitative and qualitative. Qualitative sensitivity analysis is conducted for multicriteria discrete optimization problems with minisum, minimax and minimin partial criteria. The main results obtained here are necessary and sufficient conditions for different stability types of optimal solutions (or a set of optimal solutions) of the considered problems. Within the framework of quantitative direction various measures of solution stability are investigated. A formula for a quantitative characteristic called stability radius is obtained for the generalized equilibrium situation invariant to changes of game parameters in the case of the H¨older metric. Quality of the problem solution can also be described in terms of robustness analysis. In this work the concepts of accuracy and robustness tolerances are presented for a strategic game with a finite number of players where initial coefficients (costs) of linear payoff functions are subject to perturbations. Investigation of stability radius also aims to devise methods for its calculation. A new metaheuristic approach is derived for calculation of stability radius of an optimal solution to the shortest path problem. The main advantage of the developed method is that it can be potentially applicable for calculating stability radii of NP-hard problems. The last chapter of the thesis focuses on deriving innovative methods based on interactive optimization approach for solving multicriteria combinatorial optimization problems. The key idea of the proposed approach is to utilize a parameterized achievement scalarizing function for solution calculation and to direct interactive procedure by changing weighting coefficients of this function. In order to illustrate the introduced ideas a decision making process is simulated for three objective median location problem. The concepts, models, and ideas collected and analyzed in this thesis create a good and relevant grounds for developing more complicated and integrated models of postoptimal analysis and solving the most computationally challenging problems related to it.

On state and parameter estimation in chaotic systems

State-of-the-art predictions of atmospheric states rely on large-scale numerical models of chaotic systems. This dissertation studies numerical methods for state and parameter estimation in such systems. The motivation comes from weather and climate models and a methodological perspective is adopted. The dissertation comprises three sections: state estimation, parameter estimation and chemical data assimilation with real atmospheric satellite data. In the state estimation part of this dissertation, a new filtering technique based on a combination of ensemble and variational Kalman filtering approaches, is presented, experimented and discussed. This new filter is developed for large-scale Kalman filtering applications. In the parameter estimation part, three different techniques for parameter estimation in chaotic systems are considered. The methods are studied using the parameterized Lorenz 95 system, which is a benchmark model for data assimilation. In addition, a dilemma related to the uniqueness of weather and climate model closure parameters is discussed. In the data-oriented part of this dissertation, data from the Global Ozone Monitoring by Occultation of Stars (GOMOS) satellite instrument are considered and an alternative algorithm to retrieve atmospheric parameters from the measurements is presented. The validation study presents first global comparisons between two unique satellite-borne datasets of vertical profiles of nitrogen trioxide (NO3), retrieved using GOMOS and Stratospheric Aerosol and Gas Experiment III (SAGE III) satellite instruments. The GOMOS NO3 observations are also considered in a chemical state estimation study in order to retrieve stratospheric temperature profiles. The main result of this dissertation is the consideration of likelihood calculations via Kalman filtering outputs. The concept has previously been used together with stochastic differential equations and in time series analysis. In this work, the concept is applied to chaotic dynamical systems and used together with Markov chain Monte Carlo (MCMC) methods for statistical analysis. In particular, this methodology is advocated for use in numerical weather prediction (NWP) and climate model applications. In addition, the concept is shown to be useful in estimating the filter-specific parameters related, e.g., to model error covariance matrix parameters.

Background for Designing an Improved Digital Musical Keyboard Instrument

Electrical keyboard instruments and computer-aided music-making generally base on the piano keyboard that was developed for a tuning system no longer used. Alternative keyboard layout offers at least easier playing, faster adopting, new ways to play and better ergonomics. This thesis explores the development of keyboard instruments and tunings, and different keyboard layouts. This work is preliminary research for an electrical keyboard instrument to be implemented later on.

Algorithmic Techniques in Gene Expression Processing. From Imputation to Visualization

The amount of biological data has grown exponentially in recent decades. Modern biotechnologies, such as microarrays and next-generation sequencing, are capable to produce massive amounts of biomedical data in a single experiment. As the amount of the data is rapidly growing there is an urgent need for reliable computational methods for analyzing and visualizing it. This thesis addresses this need by studying how to efficiently and reliably analyze and visualize high-dimensional data, especially that obtained from gene expression microarray experiments. First, we will study the ways to improve the quality of microarray data by replacing (imputing) the missing data entries with the estimated values for these entries. Missing value imputation is a method which is commonly used to make the original incomplete data complete, thus making it easier to be analyzed with statistical and computational methods. Our novel approach was to use curated external biological information as a guide for the missing value imputation. Secondly, we studied the effect of missing value imputation on the downstream data analysis methods like clustering. We compared multiple recent imputation algorithms against 8 publicly available microarray data sets. It was observed that the missing value imputation indeed is a rational way to improve the quality of biological data. The research revealed differences between the clustering results obtained with different imputation methods. On most data sets, the simple and fast k-NN imputation was good enough, but there were also needs for more advanced imputation methods, such as Bayesian Principal Component Algorithm (BPCA). Finally, we studied the visualization of biological network data. Biological interaction networks are examples of the outcome of multiple biological experiments such as using the gene microarray techniques. Such networks are typically very large and highly connected, thus there is a need for fast algorithms for producing visually pleasant layouts. A computationally efficient way to produce layouts of large biological interaction networks was developed. The algorithm uses multilevel optimization within the regular force directed graph layout algorithm.

Insights into the role of hydration in protein structure and stability obtained through hydrostatic pressure studies

A thorough understanding of protein structure and stability requires that we elucidate the molecular basis for the effects of both temperature and pressure on protein conformational transitions. While temperature effects are relatively well understood and the change in heat capacity upon unfolding has been reasonably well parameterized, the state of understanding of pressure effects is much less advanced. Ultimately, a quantitative parameterization of the volume changes (at the basis of pressure effects) accompanying protein conformational transitions will be required. The present report introduces a qualitative hypothesis based on available model compound data for the molecular basis of volume change upon protein unfolding and its dependence on temperature.

Pituusleikkureiden 3D-suunnittelun kehittäminen

Tämä diplomityö tehtiin Valmet Technologies Oy:n Järvenpään toimipisteelle. Työn tavoitteena oli tutkia miten pituusleikkureiden 3D-suunnittelua voidaan tehostaa hyödyntämällä uuden 3D-CAD -järjestelmän ominaisuuksia optimaalisesti. Työ koostuu teoriaosuudesta, haastattelututkimuksesta sekä käytännön osuudesta. Teoriaosuudessa perehdytään pituusleikkurin toimintaan ja rakenteeseen, 3D-suunnittelun teoriaan sekä CATIA-järjestelmään. Teoriaosuudessa etsitään myös uusia näkökulmia 3D-suunnitteluun. Haastattelututkimuksessa kartoitetaan nykyinen suunnitteluprosessi, suunnittelun kehitettäviä kohteita, sekä käytössä olevia suunnittelumenetelmiä, jotka ovat todettu toimiviksi. Haastattelututkimuksessa haastatellaan Valmet Technologies Oy:n Järvenpään toimipisteessä työskenteleviä pituusleikkureiden pääsuunnittelijoita sekä heidän esimiehiään. Lisäksi erillisten haastattelujen avulla kerätään kokemuksia CATIA V6 -ohjelmiston käytöstä sekä suunnitteluohjelmiston vaihtumisesta. Käytännön osuuden tavoitteena on arvioida pituusleikkurin parametroitujen mallirakenteiden siirtämiseen sekä korjauksiin kuluvia aikamääriä kyseisiin toimenpiteisiin tarvittavien resurssien määrittämiseksi. Käytännön osuudessa siirretään kaksi Valmet OptiWin Drum Compact -pituusleikkurin parametroitua osakokonaisuutta uuteen CAD-järjestelmään ja niille suoritetaan tarvittavat korjaustoimenpiteet Tutkimuksen tulosten perusteella yhteisen mallinnusmetodologian puuttuminen on merkittävin kehityskohde suunnittelun kehittämisessä. Lopuksi luotiin kehitysehdotukset sekä implementointisuunnitelma, joiden avulla pituusleikkureiden 3D-suunnittelua voidaan kehittää ja CATIA V6 -ohjelmisto voidaan ottaa käyttöön tehokkaasti.

Square Root Finding In Graphs

Abstract: Root and root finding are concepts familiar to most branches of mathematics. In graph theory, H is a square root of G and G is the square of H if two vertices x,y have an edge in G if and only if x,y are of distance at most two in H. Graph square is a basic operation with a number of results about its properties in the literature. We study the characterization and recognition problems of graph powers. There are algorithmic and computational approaches to answer the decision problem of whether a given graph is a certain power of any graph. There are polynomial time algorithms to solve this problem for square of graphs with girth at least six while the NP-completeness is proven for square of graphs with girth at most four. The girth-parameterized problem of root fining has been open in the case of square of graphs with girth five. We settle the conjecture that recognition of square of graphs with girth 5 is NP-complete. This result is providing the complete dichotomy theorem for square root finding problem.

Explaining the Transition Between Exchange Rate Regimes

This paper studies the transition between exchange rate regimes using a Markov chain model with time-varying transition probabilities. The probabilities are parameterized as nonlinear functions of variables suggested by the currency crisis and optimal currency area literature. Results using annual data indicate that inflation, and to a lesser extent, output growth and trade openness help explain the exchange rate regime transition dynamics.

MODELING HETEROTACHY IN PHYLOGENETICS

Il a été démontré que l’hétérotachie, variation du taux de substitutions au cours du temps et entre les sites, est un phénomène fréquent au sein de données réelles. Échouer à modéliser l’hétérotachie peut potentiellement causer des artéfacts phylogénétiques. Actuellement, plusieurs modèles traitent l’hétérotachie : le modèle à mélange des longueurs de branche (MLB) ainsi que diverses formes du modèle covarion. Dans ce projet, notre but est de trouver un modèle qui prenne efficacement en compte les signaux hétérotaches présents dans les données, et ainsi améliorer l’inférence phylogénétique. Pour parvenir à nos fins, deux études ont été réalisées. Dans la première, nous comparons le modèle MLB avec le modèle covarion et le modèle homogène grâce aux test AIC et BIC, ainsi que par validation croisée. A partir de nos résultats, nous pouvons conclure que le modèle MLB n’est pas nécessaire pour les sites dont les longueurs de branche diffèrent sur l’ensemble de l’arbre, car, dans les données réelles, le signaux hétérotaches qui interfèrent avec l’inférence phylogénétique sont généralement concentrés dans une zone limitée de l’arbre. Dans la seconde étude, nous relaxons l’hypothèse que le modèle covarion est homogène entre les sites, et développons un modèle à mélanges basé sur un processus de Dirichlet. Afin d’évaluer différents modèles hétérogènes, nous définissons plusieurs tests de non-conformité par échantillonnage postérieur prédictif pour étudier divers aspects de l’évolution moléculaire à partir de cartographies stochastiques. Ces tests montrent que le modèle à mélanges covarion utilisé avec une loi gamma est capable de refléter adéquatement les variations de substitutions tant à l’intérieur d’un site qu’entre les sites. Notre recherche permet de décrire de façon détaillée l’hétérotachie dans des données réelles et donne des pistes à suivre pour de futurs modèles hétérotaches. Les tests de non conformité par échantillonnage postérieur prédictif fournissent des outils de diagnostic pour évaluer les modèles en détails. De plus, nos deux études révèlent la non spécificité des modèles hétérogènes et, en conséquence, la présence d’interactions entre différents modèles hétérogènes. Nos études suggèrent fortement que les données contiennent différents caractères hétérogènes qui devraient être pris en compte simultanément dans les analyses phylogénétiques.

The ethical dilemma of lifestyle change: designing for sustainable schools and sustainable citizenship

his paper explores how participation and sustainability are being addressed by architects within the Building Schools for the Future (BSF) programme in the UK. The intentions promoted by the programme are certainly ambitious, but the ways to fulfil these aims are ill-explored. Simply focusing on providing innovative learning technologies, or indeed teaching young people about physical sustainability features in buildings, will not necessarily teach them the skills they will need to respond to the environmental and social challenges of a rapidly changing world. However, anticipating those skills is one of the most problematic issues of the programme. The involvement of young people in the design of schools is used to suggest empowerment, place-making and to promote social cohesion but this is set against government design literature which advocates for exemplars, standard layouts and best practice, all leading to forms of standardisation. The potentials for tokenistic student involvement and conflict with policy aims are evident. This paper explores two issues: how to foster in young people an ethic towards future generations, and the role of co-design practices in this process. Michael Oakeshott calls teaching the conversation of mankind. In this paper, I look at the philosophy of Hannah Arendt, Emmanuel Levinas, Maurice Merleau-Ponty and Luce Irigaray to argue that investigating the ethical dilemmas of the programme through critical dialogue with students offers an approach to meeting government objectives, building sustainable schools, and fostering sustainable citizenship.

Asset Pricing in a Production Economy with Chew–Dekel Preferences

In this paper we provide a thorough characterization of the asset returns implied by a simple general equilibrium production economy with Chew–Dekel risk preferences and convex capital adjustment costs. When households display levels of disappointment aversion consistent with the experimental evidence, a version of the model parameterized to match the volatility of output and consumption growth generates unconditional expected asset returns and price of risk in line with the historical data. For the model with Epstein–Zin preferences to generate similar statistics, the relative risk aversion coefficient needs to be about 55, two orders of magnitude higher than the available estimates. We argue that this is not surprising, given the limited risk imposed on agents by a reasonably calibrated stochastic growth model.

Utilisation de la visualisation interactive pour l’analyse des dépendances dans les logiciels

La compréhension de la structure d’un logiciel est une première étape importante dans la résolution de tâches d’analyse et de maintenance sur celui-ci. En plus des liens définis par la hiérarchie, il existe un autre type de liens entre les éléments du logiciel que nous appelons liens d’adjacence. Une compréhension complète d’un logiciel doit donc tenir compte de tous ces types de liens. Les outils de visualisation sont en général efficaces pour aider un développeur dans sa compréhension d’un logiciel en lui présentant l’information sous forme claire et concise. Cependant, la visualisation simultanée des liens hiérarchiques et d’adjacence peut donner lieu à beaucoup d’encombrement visuel, rendant ainsi ces visualisations peu efficaces pour fournir de l’information utile sur ces liens. Nous proposons dans ce mémoire un outil de visualisation 3D qui permet de représenter à la fois la structure hiérarchique d’un logiciel et les liens d’adjacence existant entre ses éléments. Notre outil utilise trois types de placements différents pour représenter la hiérarchie. Chacun peut supporter l’affichage des liens d’adjacence de manière efficace. Pour représenter les liens d’adjacence, nous proposons une version 3D de la méthode des Hierarchical Edge Bundles. Nous utilisons également un algorithme métaheuristique pour améliorer le placement afin de réduire davantage l’encombrement visuel dans les liens d’adjacence. D’autre part, notre outil offre un ensemble de possibilités d’interaction permettant à un usager de naviguer à travers l’information offerte par notre visualisation. Nos contributions ont été évaluées avec succès sur des systèmes logiciels de grande taille.

Le poids de l’oiseau sur la vitre ; suivi de L’hétérogénéité graphique dans Blankets de Craig Thompson

Le mémoire original s'accompagnait en annexe du livre-objet Le poids de l'oiseau sur la vitre.

Development and Evaluation of Blind Identification Techniques for Nonlinear Systems

Identification and Control of Non‐linear dynamical systems are challenging problems to the control engineers.The topic is equally relevant in communication,weather prediction ,bio medical systems and even in social systems,where nonlinearity is an integral part of the system behavior.Most of the real world systems are nonlinear in nature and wide applications are there for nonlinear system identification/modeling.The basic approach in analyzing the nonlinear systems is to build a model from known behavior manifest in the form of system output.The problem of modeling boils down to computing a suitably parameterized model,representing the process.The parameters of the model are adjusted to optimize a performanace function,based on error between the given process output and identified process/model output.While the linear system identification is well established with many classical approaches,most of those methods cannot be directly applied for nonlinear system identification.The problem becomes more complex if the system is completely unknown but only the output time series is available.Blind recognition problem is the direct consequence of such a situation.The thesis concentrates on such problems.Capability of Artificial Neural Networks to approximate many nonlinear input-output maps makes it predominantly suitable for building a function for the identification of nonlinear systems,where only the time series is available.The literature is rich with a variety of algorithms to train the Neural Network model.A comprehensive study of the computation of the model parameters,using the different algorithms and the comparison among them to choose the best technique is still a demanding requirement from practical system designers,which is not available in a concise form in the literature.The thesis is thus an attempt to develop and evaluate some of the well known algorithms and propose some new techniques,in the context of Blind recognition of nonlinear systems.It also attempts to establish the relative merits and demerits of the different approaches.comprehensiveness is achieved in utilizing the benefits of well known evaluation techniques from statistics. The study concludes by providing the results of implementation of the currently available and modified versions and newly introduced techniques for nonlinear blind system modeling followed by a comparison of their performance.It is expected that,such comprehensive study and the comparison process can be of great relevance in many fields including chemical,electrical,biological,financial and weather data analysis.Further the results reported would be of immense help for practical system designers and analysts in selecting the most appropriate method based on the goodness of the model for the particular context.

Service quality and reliability assessment of mobile communication infrastructure

The service quality of any sector has two major aspects namely technical and functional. Technical quality can be attained by maintaining technical specification as decided by the organization. Functional quality refers to the manner which service is delivered to customer which can be assessed by the customer feed backs. A field survey was conducted based on the management tool SERVQUAL, by designing 28 constructs under 7 dimensions of service quality. Stratified sampling techniques were used to get 336 valid responses and the gap scores of expectations and perceptions are analyzed using statistical techniques to identify the weakest dimension. To assess the technical aspects of availability six months live outage data of base transceiver were collected. The statistical and exploratory techniques were used to model the network performance. The failure patterns have been modeled in competing risk models and probability distribution of service outage and restorations were parameterized. Since the availability of network is a function of the reliability and maintainability of the network elements, any service provider who wishes to keep up their service level agreements on availability should be aware of the variability of these elements and its effects on interactions. The availability variations were studied by designing a discrete time event simulation model with probabilistic input parameters. The probabilistic distribution parameters arrived from live data analysis was used to design experiments to define the availability domain of the network under consideration. The availability domain can be used as a reference for planning and implementing maintenance activities. A new metric is proposed which incorporates a consistency index along with key service parameters that can be used to compare the performance of different service providers. The developed tool can be used for reliability analysis of mobile communication systems and assumes greater significance in the wake of mobile portability facility. It is also possible to have a relative measure of the effectiveness of different service providers.