| 1. |
- Amankwah, Henry, 1969-
(författare)
-
Mathematical Optimization Models and Methods for Open-Pit Mining
- 2011
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Open-pit mining is an operation in which blocks from the ground are dug to extract the ore contained in them, and in this process a deeper and deeper pit is formed until the mining operation ends. Mining is often a highly complex industrial operation, with respect to both technological and planning aspects. The latter may involve decisions about which ore to mine and in which order. Furthermore, mining operations are typically capital intensive and long-term, and subject to uncertainties regarding ore grades, future mining costs, and the market prices of the precious metals contained in the ore. Today, most of the high-grade or low-cost ore deposits have already been depleted, and to obtain sufficient profitability in mining operations it is therefore today often a necessity to achieve operational efficiency with respect to both technological and planning issues.In this thesis, we study the open-pit design problem, the open-pit mining scheduling problem, and the open-pit design problem with geological and price uncertainty. These problems give rise to (mixed) discrete optimization models that in real-life settings are large scale and computationally challenging.The open-pit design problem is to find an optimal ultimate contour of the pit, given estimates of ore grades, that are typically obtained from samples in drill holes, estimates of costs for mining and processing ore, and physical constraints on mining precedence and maximal pit slope. As is well known, this problem can be solved as a maximum flow problem in a special network. In a first paper, we show that two well known parametric procedures for finding a sequence of intermediate contours leading to an ultimate one, can be interpreted as Lagrangian dual approaches to certain side-constrained design models. In a second paper, we give an alternative derivation of the maximum flow problem of the design problem.We also study the combined open-pit design and mining scheduling problem, which is the problem of simultaneously finding an ultimate pit contour and the sequence in which the parts of the orebody shall be removed, subject to mining capacity restrictions. The goal is to maximize the discounted net profit during the life-time of the mine. We show in a third paper that the combined problem can also be formulated as a maximum flow problem, if the mining capacity restrictions are relaxed; in this case the network however needs to be time-expanded.In a fourth paper, we provide some suggestions for Lagrangian dual heuristic and time aggregation approaches for the open-pit scheduling problem. Finally, we study the open-pit design problem under uncertainty, which is taken into account by using the concept of conditional value-atrisk. This concept enables us to incorporate a variety of possible uncertainties, especially regarding grades, costs and prices, in the planning process. In real-life situations, the resulting models would however become very computationally challenging.
|
|
| 2. |
- Holm, Åsa
(författare)
-
Mathematical Optimization of HDR Brachytherapy
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- One out of eight deaths throughout the world is due to cancer. Developing new treatments and improving existing treatments is hence of major importance. In this thesis we have studied how mathematical optimization can be used to improve an existing treatment method: high-dose-rate (HDR) brachytherapy.HDR brachytherapy is a radiation modality used to treat tumours of for example the cervix, prostate, breasts, and skin. In HDR brachytherapy catheters are implanted into or close to the tumour volume. A radioactive source is moved through the catheters, and by adjusting where the catheters are placed, called catheter positioning, and how the source is moved through the catheters, called the dwelling time pattern, the dose distribution can be controlled.By constructing an individualized catheter positioning and dwelling time pattern, called dose plan, based on each patient's anatomy, it is possible to improve the treatment result. Mathematical optimization has during the last decade been used to aid in creating individualized dose plans. The dominating optimization model for this purpose is a linear penalty model. This model only considers the dwelling time pattern within already implanted catheters, and minimizes a weighted deviation from dose intervals prescribed by a physician.In this thesis we show that the distribution of the basic variables in the linear penalty model implies that only dwelling time patterns that have certain characteristics can be optimal. These characteristics cause troublesome inhomogeneities in the plans, and although various measures for mitigating these are already available, it is of fundamental interest to understand their cause.We have also shown that the relationship between the objective function of the linear penalty model and the measures commonly used for evaluating the quality of the dose distribution is weak. This implies that even if the model is solved to optimality there is no guarantee that the generated plan is optimal with respect to clinically relevant objectives, or even near-optimal. We have therefore constructed a new model for optimizing the dwelling time pattern. This model approximates the quality measures by the concept conditional value-at-risk, and we show that the relationship between our new model and the quality measures is strong. Furthermore, the new model generates dwelling time patterns that yield high-quality dose distributions.Combining optimization of the dwelling time pattern with optimization of the catheter positioning yields a problem for which it is rarely possible to find a proven optimal solution within a reasonable time frame. We have therefore developed a variable neighbourhood search heuristic that outperforms a state-of-the-art optimization software (CPLEX). We have also developed a tailored branch-and-bound algorithm that is better at improving the dual bound than a general branch-and-bound algorithm. This is a step towards the development of a method that can find proven optimal solutions to the combined problem within a reasonable time frame.
|
|
| 3. |
- Ndengo Rugengamanzi, Marcel, 1964-
(författare)
-
Term structure estimation based on a generalized optimization framework
- 2013
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The current work is devoted to estimating the term structure of interest rates based on a generalized optimization framework. To x the ideas of the subject, we introduce representations of the term structure as they are used in nance: yield curve, discount curve and forward rate curve.Yield curves are used in empirical research in nance and macroeconomic to support nancial decisions made by governments and/or private nancial institutions. When governments (or nancial corporations) need fundings, they issue to the public (i.e. the market) debt securities (bills, bonds, notes, etc ) which are sold at the discount rate at the settlement date and promise the face value of the security at the redemption date, known as maturity date. Bills, notes and bonds are usually sold with maximum maturity of 1 year, 10 years and 30 years respectively.Let us assume that the government issues to the market zero-coupon bonds, which provide a single payment at maturity of each bond. To determine the price of the security at time of settlement, a single discount factor is used. Thus, the yield can be dened as the discount rate which makes the present value of the security issued (the zero-coupon bond) equal to its initial price. The yield curve describes the relationship between a particular yield and a bond's maturity. In general, given a certain number of bonds with dierent time to maturity, the yield curve will describe the one-to-one relationship between the bond yields and their corresponding time to maturity. For a realistic yield curve, it is important to use only bonds from the same class of issuer or securities having the same degree of liquidity when plotting the yields.Discount factors, used to price bonds, are functions of the time to maturity. Given that yields are positive, these functions are assumed to be monotonically decreasing as the time to maturity increases. Thus, a discount curve is simply the graph of discount factors for dierent maturities associated with dierent securities.Another useful curve uses the forward rate function which can be deduced from both the discount factor and the yield function. The forward rate is the rate of return for an investment that is agreed upon today but which starts at some time in the future and provides payment at some time in the future as well. When forward rates are used, the resulting curve is referred to as the forward rate curve. Thus, any of these curves, that is, the yield curve, the discount curve or the forward rate curve, can be used to represent what is known as the term structure of interest rate. The shapes that the term structure of interest rates can assume include upward sloping, downward sloping, atness or humped, depending on the state of the economy. When the expectations of market participants are incorporated in the construction of these curves representing the term structure, their shapes capture and summarize the cost of credit and risks associated with every security traded.However, constructing these curves and the choice of an appropriate representation of the term structure to use is not a straightforward task. This is due to the complexity of the market data, precisely, the scarcity of zero-coupon bonds which constitutes the backbone of the term structure. The market often provides coupons alongside market security prices for a small number of maturities. This implies that, for the entire maturity spectrum, yields can not be observed on the market. Based on available market data, yields must be estimated using traditional interpolation methods. To this end, polynomial splines as well as parsimonious functions are the methods mostly used by nancial institutions and in research in nance. However, it is observed in literature that these methods suer from the shape constraints which cause them to produce yield curves that are not realistic with respect to the market observations. Precisely, the yield curves produced by these methods are characterized by unrealistic t of the market data, either in the short end or in the long end of the term structure of interest rate.To ll the gap, the current research models the yield curve using a generalized optimization framework. The method is not shape constrained, which implies that it can adapt to any shape the yield curve can take across the entire maturity spectrum. While estimating the yield curve using this method in comparison with traditional methods on the Swedish and US markets, it is shown that any other traditional method used is a special case of the generalized optimization framework. Moreover, it is shown that, for a certain market consistency, the method produces lower variances than any of the traditional methods tested. This implies that the method produces forward rate curve of higher quality compared to the existing traditional methods.Interest rate derivatives are instruments whose prices depend or are derived from the price of other instruments. Derivatives instruments that are extensively used include the forward rate agreement (FRA) contracts where forward rate is used and the interest rate swap (IRS) where LIBOR rate is used as oating rate. These instruments will only be used to build up the term structure of interest rates. Since the liquidity crisis in 2007, it is observed that discrepancies in basis spread between interest rates applied to dierent interest rate derivatives have grown so large that a single discount curve is no longer appropriate to use for pricing securities consistently. It has been suggested that the market needs new methods for multiple yield curves estimation to price securities consistently with the market. As a response, the generalized optimization framework is extended to a multiple yield curves estimation. We show that, unlike the cubic spline for instance, which is among the mostly used traditional method, the generalized framework can produce multiple yield curves and tenor premium curves that are altogether smooth and realistic with respect to the market observations.U.S. Treasury market is, by size and importance, a leading market which is considered as benchmark for most xed-income securities that are traded worldwide. However, existing U.S. Treasury yield curves that are used in the market are of poor quality since they have been estimated by traditional interpolation methods which are shape constrained. This implies that the market prices they imply contain lots of noise and as such, are not safe to use. In this work, we use the generalized optimization framework to estimate high-quality forward rates for the U.S. Treasury yield curve. Using ecient frontiers, we show that the method can produce low pricing error with low variance as compared to the least squares methods that have been used to estimate U.S. Treasury yield curves.We nally use the high-quality U.S. Treasury forward rate curve estimated by the generalized optimization framework as input to the essentially ane model to capture the randomness property in interest rates and the time-varying term premium. This premium is simply a compensation that is required for additional risks that investors are exposed to. To determine optimal investment in the U.S. Treasury market, a two-stage stochastic programming model without recourse is proposed, which model borrowing, shorting and proportional transaction cost. It is found that the proposed model can provide growth of wealth in the long run. Moreover, its Sharpe ratio is better than the market index and its Jensen's alpha is positive. This implies that the Stochastic Programming model proposed can produce portfolios that perform better than the market index.
|
|
| 4. |
- Quttineh, Nils-Hassan, 1979-
(författare)
-
Models and Methods for Costly Global Optimization and Military Decision Support Systems
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- The thesis consists of five papers. The first three deal with topics within costly global optimization and the last two concern military decision support systems.The first part of the thesis addresses so-called costly problems where the objective function is seen as a “black box” to which the input parameter values are sent and a function value is returned. This means in particular that no information about derivatives is available. The black box could, for example, solve a large system of differential equations or carry out timeconsuming simulation, where a single function evaluation can take several hours! This is the reason for describing such problems as costly and why they require customized algorithms. The goal is to construct algorithms that find a (near)-optimal solution using as few function evaluations as possible. A good example of a real life application comes from the automotive industry, where the development of new engines utilizes advanced mathematical models that are governed by a dozen key parameters. The objective is to optimize the engine by changing these parameters in such a way that it becomes as energy efficient as possible, but still meets all sorts of demands on strength and external constraints. The first three papers describe algorithms and implementation details for these costly global optimization problems.The second part deals with military mission planning, that is, problems that concern logistics, allocation and deployment of military resources. Given a fleet of resource, the decision problem is to allocate the resources against the enemy so that the overall mission success is optimized. We focus on the problem of the attacker and consider two separate problem classes. In the fourth paper we introduce an effect oriented planning approach to an advanced weapon-target allocation problem, where the objective is to maximize the expected outcome of a coordinated attack. We present a mathematical model together with efficient solution techniques. Finally, in the fifth paper, we introduce a military aircraft mission planning problem, where an aircraft fleet should attack a given set of targets. Aircraft routing is an essential part of the problem, and the objective is to maximize the expected mission success while minimizing the overall mission time. The problem is stated as a generalized vehicle routing model with synchronization and precedence side constraints.
|
|
| 5. |
- Rönnberg, Elina, 1981-
(författare)
-
Contributions within two topics in integer programming : nurse scheduling and column generation
- 2012
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Integer programming can be used to provide solutions to complex decision and planning problems occurring in a wide variety of situations. The application of integer programming to solve real world problems requires a modelling phase in which the problem at hand is translated into a mathematical description of the problem, and a solution phase that aims at developing methods for producing solutions to the mathematical formulation of the problem.The first two papers of this thesis have their focus on the modelling phase, and the application of integer programming for solving nurse scheduling problems. Common to both papers is that the research has been conducted in collaboration with health care representatives, and that the models presented can be used for providing schedules that can be used by nurses. In the latter paper, a meta-heuristic approach is suggested for providing the schedules.The last three papers address method development and specifically the design of column generation methods. The first of these papers presents optimality conditions that are useful in methods where columns are generated using dual solutions that are not necessarily optimal with respect to a linear programming relaxation, and the usefulness of these conditions are illustrated by examples from the literature.Many applications of column generation yield master problems of a set partitioning type, and the fourth and fifth paper present methodologies for solving such problems. The characteristics of these methodologies are that all solutions derived are feasible and integral, where the preservation of integrality is a major distinction from other column generation methods presented in the literature.
|
|
