1. |
- Ngulo, Uledi, 1983-
(författare)
-
Decomposition Methods for Combinatorial Optimization
- 2021
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis aims at research in the field of combinatorial optimization. Problems within this field often posses special structures allowing them to be decomposed into more easily solved subproblems, which can be exploited in solution methods. These structures appear frequently in applications. We contribute with both re-search on the development of decomposition principles and on applications. The thesis consists of an introduction and three papers. In Paper I, we develop a Lagrangian meta-heuristic principle, which is founded on a primal-dual global optimality condition for discrete and non-convex optimization problems. This condition characterizes (near-)optimal solutions in terms of near-optimality and near-complementarity measures for Lagrangian relaxed solutions. The meta-heuristic principle amounts to constructing a weighted combination of these measures, thus creating a parametric auxiliary objective function (which is a close relative to a Lagrangian function), and embedding a Lagrangian heuristic in a search procedure in the space of the weight parameters. We illustrate and assess the Lagrangian meta-heuristic principle by applying it to the generalized assignment problem and to the set covering problem. Our computational experience shows that the meta-heuristic extension of a standard Lagrangian heuristic principle can significantly improve upon the solution quality. In Paper II, we study the duality gap for set covering problems. Such problems sometimes have large duality gaps, which make them computationally challenging. The duality gap is dissected with the purpose of understanding its relationship to problem characteristics, such as problem shape and density. The means for doing this is the above-mentioned optimality condition, which is used to decompose the duality gap into terms describing near-optimality in a Lagrangian relaxation and near-complementarity in the relaxed constraints. We analyse these terms for numerous problem instances, including some large real-life instances, and conclude that when the duality gap is large, the near-complementarity term is typically large and the near-optimality term small. The large violation of complementarity is due to extensive over-coverage. Our observations have implications for the design of solution methods, especially for the design of core problems. In Paper III, we study a bi-objective covering problem stemming from a real-world application concerning the design of camera surveillance systems for large-scale outdoor areas. It is prohibitively costly to surveil the entire area, and therefore relevant to be able to present a decision-maker with trade-offs between total cost and the portion of the area that is surveilled. The problem is stated as a set covering problem with two objectives, describing cost and portion of covering constraints that are fulfilled, respectively. Finding the Pareto frontier for these objectives is very computationally demanding and we therefore develop a method for finding a good approximate frontier in a reasonable computing time. The method is based on the ε−constraint reformulation, an established heuristic for set covering problems, and subgradient optimization.
|
|
2. |
- Mwakisisile, Andongwisye John, 1972-
(författare)
-
Asset Liability Management for Tanzania Pension Funds
- 2018
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- This thesis presents a long-term asset liability management for Tanzania pension funds. As an application, the largest pension fund in Tanzania is considered. This is a pay-as-you-go pension fund where the contributions are used to pay current benefits. The Pension plan analyzed is a final salary defined benefit. Two kinds of pension benefit are considered, a commuted (at retirement) and a monthly (old age) pension. A decision factor in the analysis is the increased life expectancy of the members of the pension fund.The presentation is divided into two parts. First is a long-term projection of the fund using a fixed and relatively low return on asset value. Basing on the number of members in 2015, a 50 years projection of members and retirees is done. The corresponding amount of contributions, asset values, benefit payouts, and liabilities are also projected. The evaluation of some possible reforms of the fund is done. Then, the growth of asset values using different asset returns is studied. The projection shows that the fund will not be fully sustainable in a long future due to the increase in life expectancy of its members. The contributions will not cover the benefit payouts and the asset value will not fully cover liabilities. Evaluation of some reforms of the fund shows that they cannot guarantee a long-term sustainability. Higher returns on asset value will improve the asset to liability ratio, but contributions are still insufficient to cover benefit payouts.Second is a management based on stochastic programming. This approach allocates investment in assets with the best return to raise the asset value closer to the level of liabilities. The model is based on work by Kouwenberg in 2001 includes some features from Tanzania pension system. In contrast with most asset liability management models for pension funds by stochastic programming, liabilities are modeled by number of years of life expectancy. Scenario trees are generated by using Monte Carlo simulation. Two models according to different investment guidelines are built. First is using the existing investment guidelines and second is using modified guidelines which are practical and suitable for modeling. Numerical results suggest that, in order to improve a long-term sustainability of the Tanzania pension fund system, it is necessary to make reforms concerning the contribution rate, investment guidelines and formulate target levels (funding ratios) to characterize the pension funds’ solvency situation. These reforms will improve the sustainability of the system.
|
|
3. |
- Morén, Björn, 1987-
(författare)
-
Mathematical Modelling of Dose Planning in High Dose-Rate Brachytherapy
- 2019
-
Licentiatavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Cancer is a widespread type of diseases that each year affects millions of people. It is mainly treated by chemotherapy, surgery or radiation therapy, or a combination of them. One modality of radiation therapy is high dose-rate brachytherapy, used in treatment of for example prostate cancer and gynecologic cancer. Brachytherapy is an invasive treatment in which catheters (hollow needles) or applicators are used to place the highly active radiation source close to or within a tumour.The treatment planning problem, which can be modelled as a mathematical optimization problem, is the topic of this thesis. The treatment planning includes decisions on how many catheters to use and where to place them as well as the dwell times for the radiation source. There are multiple aims with the treatment and these are primarily to give the tumour a radiation dose that is sufficiently high and to give the surrounding healthy tissue and organs (organs at risk) a dose that is sufficiently low. Because these aims are in conflict, modelling the treatment planning gives optimization problems which essentially are multiobjective.To evaluate treatment plans, a concept called dosimetric indices is commonly used and they constitute an essential part of the clinical treatment guidelines. For the tumour, the portion of the volume that receives at least a specified dose is of interest while for an organ at risk it is rather the portion of the volume that receives at most a specified dose. The dosimetric indices are derived from the dose-volume histogram, which for each dose level shows the corresponding dosimetric index. Dose-volume histograms are commonly used to visualise the three-dimensional dose distribution.The research focus of this thesis is mathematical modelling of the treatment planning and properties of optimization models explicitly including dosimetric indices, which the clinical treatment guidelines are based on. Modelling dosimetric indices explicitly yields mixedinteger programs which are computationally demanding to solve. The computing time of the treatment planning is of clinical relevance as the planning is typically conducted while the patient is under anaesthesia. Research topics in this thesis include both studying properties of models, extending and improving models, and developing new optimization models to be able to take more aspects into account in the treatment planning.There are several advantages of using mathematical optimization for treatment planning in comparison to manual planning. First, the treatment planning phase can be shortened compared to the time consuming manual planning. Secondly, also the quality of treatment plans can be improved by using optimization models and algorithms, for example by considering more of the clinically relevant aspects. Finally, with the use of optimization algorithms the requirements of experience and skill level for the planners are lower.This thesis summary contains a literature review over optimization models for treatment planning, including the catheter placement problem. How optimization models consider the multiobjective nature of the treatment planning problem is also discussed.
|
|
4. |
- Morén, Björn, 1987-
(författare)
-
Treatment Planning of High Dose-Rate Brachytherapy - Mathematical Modelling and Optimization
- 2021
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- Cancer is a widespread class of diseases that each year affects millions of people. It is mostly treated with chemotherapy, surgery, radiation therapy, or combinations thereof. High doserate (HDR) brachytherapy (BT) is one modality of radiation therapy, which is used to treat for example prostate cancer and gynecologic cancer. In BT, catheters (i.e., hollow needles) or applicators are used to place a single, small, but highly radioactive source of ionizing radiation close to or within a tumour, at dwell positions. An emerging technique for HDR BT treatment is intensity modulated brachytherapy (IMBT), in which static or dynamic shields are used to further shape the dose distribution, by hindering the radiation in certain directions. The topic of this thesis is the application of mathematical optimization to model and solve the treatment planning problem. The treatment planning includes decisions on catheter placement, that is, how many catheters to use and where to place them, as well as decisions for dwell times. Our focus is on the latter decisions. The primary treatment goals are to give the tumour a sufficiently high radiation dose while limiting the dose to the surrounding healthy organs, to avoid severe side effects. Because these aims are typically in conflict, optimization models of the treatment planning problem are inherently multiobjective. Compared to manual treatment planning, there are several advantages of using mathematical optimization for treatment planning. First, the optimization of treatment plans requires less time, compared to the time-consuming manual planning. Secondly, treatment plan quality can be improved by using optimization models and algorithms. Finally, with the use of sophisticated optimization models and algorithms the requirements of experience and skill level for the planners are lower. The use of optimization for treatment planning of IMBT is especially important because the degrees of freedom are too many for manual planning. The contributions of this thesis include the study of properties of treatment planning models, suggestions for extensions and improvements of proposed models, and the development of new optimization models that take clinically relevant, but uncustomary aspects, into account in the treatment planning. A common theme is the modelling of constraints on dosimetric indices, each of which is a restriction on the portion of a volume that receives at least a specified dose, or on the lowest dose that is received by a portion of a volume. Modelling dosimetric indices explicitly yields mixed-integer programs which are computationally demanding to solve. We have therefore investigated approximations of dosimetric indices, for example using smooth non-linear functions or convex functions. Contributions of this thesis are also a literature review of proposed treatment planning models for HDR BT, including mathematical analyses and comparisons of models, and a study of treatment planning for IMBT, which shows how robust optimization can be used to mitigate the risks from rotational errors in the shield placement.
|
|