No description available.

<p> The pattern matching calculus introduced by Kahl provides a fine-grained mechanism of modelling non-strict pattern matching in modern functional programming languages. By changing the rule of interpreting the empty expression that results from matching failures, the pattern matching calculus can be transformed into another calculus that abstracts a "more successful" evaluation. Kahl also showed that the two calculi have both a confluent reduction system and a same normalising strategy, which constitute the operational semantics of the pattern matching calculi.</p> <p> As a new technique based on Haskell's language extensions of type-saft cast, arbitrary-rank polymorphism and generalised algebraic data types, type-indexed expressions introduced by Kahl demonstrate a uniform way of defining all expressions as type-indexed to guarantee type safety.</p> <p> In this thesis, we implemented the type-indexed syntax and operational semantics of the pattern matching calculi using type-indexed expressions. Our type-indexed syntax mirrors the definition of the pattern matching calculi. We implemented the operational semantics of the two calculi perfectly and provided reduction and normalisation examples that show that the pattern matching calculus can be a useful basis of modelling non-strict pattern matching.</p> <p> We formalised and implemented the bimonadic semantics of the pattern matching calculi using categorical concepts and type-indexed expressions respectively. The bimonadic semantics employs two monads to reflect two kinds of computational effects, which correspond to the two major syntactic categories of the pattern matching calculi, i.e. expressons and matchings. Thus, the resulting implementation provides the detotational model of non-strict pattern matching with more accuracy.</p> <p> Finally, from a practical programming viewpoint, our implementation is a good demonstration of how to program in the pure type-indexed setting by taking fully advantage of Haskell's language extensions of type-safe cast, arbitrary-rank polymorphism and generalised algebraic data types.</p> / Thesis / Master of Science (MSc)

[pt] A programação de máquinas é um processo de tomada de decisão que desempenha um importante papel na maioria das indústrias de manufatura e serviços. Esta dissertação aborda o problema de programação de máquinas paralelas idênticas sem preempção, considerando características da programação de data de liberação e data limite para execução do início das tarefas, restrição de precedência entre pares de tarefas, elegibilidade e disponibilidade de máquinas. Para resolver este problema, uma formulação de programação linear inteira mista é proposta. O novo modelo, chamado de bucket-indexed (BI), particiona o horizonte de planejamento em períodos de tempos de mesmo tamanho (buckets). O tamanho dos buckets é um par âmetro que varia de acordo com a instância e influencia o porte do modelo, podendo assumir valores entre 1 e o menor tempo de processamento das tarefas. Quanto maior o tamanho do bucket, menor é o número de buckets criados e, consequentemente, menor o porte do modelo. A formulação proposta é testada em instâncias reais referentes ao problema de programação de sondas para construção de poços de petróleo de uma indústria brasileira de óleo e gás. A fim de avaliar os resultados obtidos pela formulação BI, a formulação clássica time-indexed (TI) foi também implementada para comparação dos tempos computacionais e qualidade da solução. Os resultados da formulação proposta apontam um melhor desempenho nas instâncias testadas, reduzindo o tempo computacional em todos os casos e resolvendo instâncias de grande porte não resolvidas pela formulação TI. / [en] Machine scheduling is a decision-making process that plays an important role in most manufacturing and service industries. This dissertation tackles a nonpreemptive identical parallel machine scheduling problem, considering release dates, deadlines, precedences, eligibility, and machine availability constraints. To solve this problem, a mixed-integer linear programming formulation is proposed. The new model, called bucketindexed, partitions the planning horizon in periods of equal length (buckets). The bucket size is a parameter which varies according to instances and influences the model size, assuming values between 1 and the shortest processing time of jobs. The larger the bucket size, the smaller is the number of buckets created and, consequently, the smaller the model size. The proposed formulation is tested in real instances of the rig scheduling problem for a Brazilian oil and gas industry. To evaluate the results obtained by the BI formulation, the classical time-indexed (TI) formulation was also implemented for comparison of computational times and solution quality. The results of the proposed formulation highlight a better performance in all the tested instances, reducing computational time in all cases and solving large instances unsolvable by the TI formulation.

The aim in this thesis is to develop efficient enumeration algorithms to solve certain strongly NP-hard scheduling problems. These algorithms were developed using a combination of ideas from Integer Programming, Constraint Programming and Scheduling Theory. In order to combine different techniques in one algorithm, decomposition methods are applied. The main idea on which the first part of our results is based is to separate the optimality and feasibility components of the problem and let different methods tackle these components. Then IP is ``responsible' for optimization, whereas specific combinatorial algorithms tackle the feasibility aspect. Branch-and-cut and branch-and-price algorithms based on this idea are proposed to solve the single-machine and multi-machine variants of the scheduling problem to minimize the sum of the weights of late jobs. Experimental research shows that the algorithms proposed outperform other algorithms available in the literature. Also, it is shown that these algorithms can be used, after some modification, to solve the problem of minimizing the maximum tardiness on unrelated machines. The second part of the thesis deals with the one-machine scheduling problem to minimize the weighted total tardiness. To tackle this problem, the idea of a partition of the time horizon into intervals is used. A particularity of this approach is that we exploit the structure of the problem to partition the time horizon. This particularity allowed us to propose two new Mixed Integer Programming formulations for the problem. The first one is a compact formulation and can be used to solve the problem using a standard MIP solver. The second formulation can be used to derive lower bounds on the value of the optimal solution of the problem. These lower bounds are of a good quality, and they can be obtained relatively fast.

The Diameter-Constrained Minimum Spanning Tree Problem seeks a least cost spanning tree subject to a (diameter) bound imposed on the number of edges in the tree between any node pair. A traditional multicommodity flow model with a commodity for every pair of nodes was unable to solve a 20-node and 100-edge problem after one week of computation. We formulate the problem as a directed tree from a selected central node or a selected central edge. Our model simultaneously finds a central node or a central edge and uses it as the source for the commodities in a directed multicommodity flow model with hop constraints. The new model has been able to solve the 20-node, 100-edge instance to optimality after less than four seconds. We also present model enhancements when the diameter bound is odd (these situations are more difficult). We show that the linear programming relaxation of the best formulations discussed in this paper always give an optimal integer solution for two special, polynomially-solvable cases of the problem. We also examine the Diameter Constrained Minimum Steiner Tree problem. We present computational experience in solving problem instances with up to 100 nodes and 1000 edges. The largest model contains more than 250,000 integer variables and more than 125,000 constraints.

Protection against inflation is an essential part of the today&#039 / s financial markets, particularly in high-inflation economies. Hence, nowadays inflation indexed instruments are being increasingly popular in the world financial markets. In this thesis, we focus on pricing of the inflation-indexed bonds which are the unique inflation-indexed instruments traded in the Turkish bond market. Firstly, we review the Jarrow-Yildirim model which deals with pricing of the inflation-indexed instruments within the HJM framework. Then, we propose a pricing model that is an extension of the Jarrow-Yildirim model. The model allows instantaneous forward rates, inflation index and bond prices to be driven by both a standard Brownian motion and a finite number of Poisson processes. A closed-form pricing formula for an European call option on the inflation index is also derived.

Inflation-indexed instruments provide a real return and protect investors from the erosion of the purchasing power of money. Hence, inflation-indexed markets grow very fast day by day. In this thesis, we focus on pricing of the inflation-indexed swaps and swaptions which are the most liquid derivative products traded in the inflation-indexed markets. Firstly, we review the Hull-White extended Vasicek model in the HJM framework. Then, we use this model to price inflation-indexed swaps. Also, pricing of inflation-indexed swaptions is given using Black&rsquo / s market model.

Inflation indexed instruments are designed to help protect investors against the changes in the general level of prices. So, they are frequently preferred by investors and they have become increasingly developing part of the market. In this study, firstly, the HJM model and foreign currency analogy used to price of inflation indexed instruments are investigated. Then, the HJM model is extended with finite number of Poisson process. Finally, under the extended HJM model, a pricing derivation of inflation indexed swaps, which are the most liquid ones among inflation indexed instruments in the market, is given.

Do corporate bond spreads reflect fear of debt deflation? Most corporate bonds have fixed nominal face values, so unexpectedly low inflation raises firms' real debt burdens and increases default risk. The first chapter develops a real business cycle model with time-varying inflation risk and optimal, but infrequent, capital structure choice. In this model, more volatile or more procyclical inflation lead to quantitatively important credit spread increases. This is true even with inflation volatility as moderate as that in developed economies since 1970. Intuitively, this result obtains because inflation persistence generates large uncertainty about the price level at long maturities and because firms cannot adjust their capital structure immediately. We find strong empirical support for our model predictions in a panel of six developed economies. Both inflation volatility and the inflation-stock return correlation have varied substantially over time and across countries. They jointly explain as much variation in credit spreads as do equity volatility and the dividend-price ratio. Credit spreads rise by 15 basis points if either inflation volatility or the inflation-stock return correlation increases by one standard deviation. Firms counteract higher debt financing costs by adjusting their capital structure in times of higher inflation uncertainty. The second chapter empirically decomposes excess return predictability in inflation-indexed and nominal government bonds into liquidity, market segmentation, real interest rate risk and inflation risk. This chapter finds evidence for time-varying liquidity premia in Treasury Inflation Protected Securities (TIPS) and for time-varying liquidity premia in TIPS and for time-varying inflation risk premia in nominal bonds. The third chapter develops a pre-test for weak instruments in linear instrumental variable regression that is robust to heteroskedasticity and autocorrelation. Our test statistic is a scaled version of the regular first-stage F statistic. The critical values depend on the long-run variance-covariance matrix of the first stage. We apply our pre-test to the instrumental variable estimation of the Elasticity of Intertemporal Substitution and find that instruments previously considered not to be weak do not exceed our threshold.

Bakgrund: Olika forskare har under åren identifierat problem relaterade till inflation, samt även bidragit med förslag på lösningar på dessa. Begreppet Money Illusion är ett välkänt begrepp inom området som tycks vara en del i förklaringen till allmänhetens motvilja att hantera inflationsrelaterade problem. Det är bestämt i Sverige av Riksbanken att inflationen skall vara låg men positiv och inflationsmålet är satt till två procent. Indexerade beräkningsenheter presenteras av Robert Shiller som lösning på kunskaps- och beteendeproblem förknippade med inflation. Han definierar en indexerad beräkningsenhet som ska fungera parallellt med den lokala valutan. Syfte: Syftet är att diskutera förutsättningar för en implementering av nya indexerade beräkningsenheter, som fungerar parallellt med valutan, i Sverige samt att kritiskt granska Robert Shillers teorier om indexerade beräkningsenheter. Genomförande: Uppsatsen är av kvalitativ karaktär och bygger på semistrukturerade intervjuer med personer inom bank- och försäkringsväsendet samt en universitetslektor i nationalekonomi vid Linköpings Universitet. Intervjuerna har utgått från samma intervjumall. Insamlat intervjumaterial har tillsammans med teorier om inflation, indexering och transaktionskostnader legat till grund för analysen. Slutsats: Slutsatsen i uppsatsen är att den låga inflation som råder i Sverige inte ses som ett tillräckligt stort problem för att motivera en mer vida indexering hos privatpersoner. De kostnader som förknippas med indexering, i form av transaktionskostnader, har även underskattats av Robert Shiller vilket gör att hans förespråkande för indexering i låginflationsländer i själva verket högst troligen är en paradox. / Background: Several scientists have, over the years, identified problems related to inflation and contributed with suggestions to solutions. The term Money Illusion is a well-known phenomenon that explains difficulties of separating nominal value from real value. The central bank of Sweden has decided that inflation should be low but positive and the inflation target is set to two percent. Robert Shiller presents Indexed Units of Account as a solution to problems related to inflation depending on knowledge and behavior. He defines an Indexed Unit of Account that is meant to operate in parallel to the local currency. Aim: The aim is to discuss the prerequisites for an implementation of new indexed units of account, which works in tandem with the currency, in Sweden as well as critically examine the theories of indexed units of account made by Robert Shiller. Completion: The thesis is qualitative in nature and is based on semi-structured interviews with people in banking, insurance and a senior lecturer in economics at the University of Linköping. The interviews have assumed the same interview template. Collected interview data, together with theories of inflation, indexing and transaction costs has formed the basis for the analysis. Conclusion: The conclusion in the paper is that the low inflation prevailing in Sweden is not seen as a big enough problem to warrant a more widespread use of indexation by individuals. Robert Shiller has also underestimated the costs associated with indexing, in the form of transaction costs, which most likely means that his advocacy of indexation is a paradox.