Radiotherapy is one method of treating di erent diseases like cancer. It requires a treatment plan that clearly delineates target and non-target volumes, and the beams and their intensities to deliver the prescribed dose. Historical treatment plans often contain volume names that are unaccounted for. An approach is applied where desired volumes are detected and renamed to conform to current search standards. The mapped names provide an avenue for searching historical plans when performing outcomes analysis in the future to help improve quality in radiation therapy. A specific form known as intensity modulated radiation therapy is applied to total marrow irradiation, a method to remove all marrow in the body prior to bone marrow transplant. A set-covering approach is used, solved using heuristics and commercial packages to compare outcomes. Constraint programming is used in an attempt to better and to improve on the heuristic solutions.

The harsh competition in the airline industry continuously forces airline carriers to streamline their production and cut back on costs. Manpower constitutes the largest expense in Scandinavian Airline System, closely followed by fuel costs. Thus effective crew planning is vital to face the competition from international actors and low cost carriers. Creating efficient schedules for airline crew is a very complex combinatorial task and the process is heavily dependent on optimization. A large set of constraints comprised of union- and governmental rules as well as company policies and quality factors must be taken into consideration when the schedules are created. This master thesis examines how the distribution of rank in the SAS international pilot corps affects the total cost associated with flight deck crew. Long haul flights at SAS intercontinental are manned with a captain, a first officer and a relief pilot. Pilots may man lower ranking positions on any given flight in order to make efficient use of the pilot corps and to minimize the need of full time equivalents. This work discusses the development and evaluation of a simulation environment developed in order to create and analyze fictitious crew populations with different distributions of rank. Furthermore the solution methods to the scheduling problem implemented at SAS and the optimization theory associated with them are discussed. The project has resulted in an evaluation of the developed simulation environment and a discussion about the difficulties of analyzing crew populations with the systems currently in use at SAS.

Radiotherapy is one method of treating di erent diseases like cancer. It requires a treatment plan that clearly delineates target and non-target volumes, and the beams and their intensities to deliver the prescribed dose. Historical treatment plans often contain volume names that are unaccounted for. An approach is applied where desired volumes are detected and renamed to conform to current search standards. The mapped names provide an avenue for searching historical plans when performing outcomes analysis in the future to help improve quality in radiation therapy. A specific form known as intensity modulated radiation therapy is applied to total marrow irradiation, a method to remove all marrow in the body prior to bone marrow transplant. A set-covering approach is used, solved using heuristics and commercial packages to compare outcomes. Constraint programming is used in an attempt to better and to improve on the heuristic solutions.

Over the last year or so, we have witnessed the global effects and repercussions related to the field of finance. Supposed blue chip stocks and well-established companies have folded and filed for bankruptcy, an event that might have thought to been absurd two years ago. In addition, finance and investment science has grown over the past few decades to include a plethora of investment options and regulations. Now more than ever, developments in the field are carefully examined and researched by potential investors. This thesis involves an investigation and quantitative analysis of key money management problems. The primary area of interest is Portfolio Selection, where we develop advanced financial models that are designed for investment problems of the 21st century. Portfolio selection is the process involved in making large investment decisions to generate a collection of assets. Over the years the selection process has evolved dramatically. Current portfolio problems involve a complex, yet realistic set of managing constraints that are coupled to general historic risk and return models. We identify three well-known portfolio problems and add an array of practical managing constraints that form three different types of Mixed-Integer Programs. The product is advanced mathematical models related to risk-return portfolios, index tracking portfolios, and an integrated stock-bond portfolio selection model. The numerous sources of uncertainty are captured in a Stochastic Programming framework, and Goal Programming techniques are used to facilitate various portfolio goals. The designs require the consideration of modelling elements and variables with respect to problem solvability. We minimize trade-offs in modelling and solvability issues found in the literature by developing problem specific algorithms. The algorithms are tailored to each portfolio design and involve decompositions and heuristics that improve solution speed and quality. The result is the generation of portfolios that have intriguing financial outcomes and perform well with respect to the market. Portfolio selection is as dynamic and complex as the recent economic situation. In this thesis we present and further develop the mathematical concepts related to portfolio construction. We investigate the key financial problems mentioned above, and through quantitative financial modelling and computational implementations we introduce current approaches and advancements in field of Portfolio Optimization.

No description available.

This dissertation addresses optimization of cubic polynomial problems. Heuristics for finding good quality feasible solutions and for improving on existing feasible solutions for a complex industrial problem, involving cubic and pooling constraints among other complicating constraints, have been developed. The heuristics for finding feasible solutions are developed based on linear approximations to the original problem that enforce a subset of the original problem constraints while it tries to provide good approximations for the remaining constraints, obtaining in this way nearly feasible solutions. The performance of these heuristics has been tested by using industrial case studies that are of appropriate size, scale and structure. Furthermore, the quality of the solutions can be quantified by comparing the obtained feasible solutions against upper bounds on the value of the problem. In order to obtain these upper bounds we have extended efficient existing techniques for bilinear problems for this class of cubic polynomial problems. Despite the efficiency of the upper bound techniques good upper bounds for the industrial case problem could not be computed efficiently within a reasonable time limit (one hour). We have applied the same techniques to subproblems with the same structure but about one fifth of the size and in this case, on average, the gap between the obtained solutions and the computed upper bounds is about 3%. In the remaining part of the thesis we look at global optimization of cubic polynomial problems with non-negative bounded variables via branch and bound. A theoretical study on the properties of convex underestimators for non-linear terms which are quadratic in one of the variables and linear on the other variable is presented. A new underestimator is introduced for this class of terms. The final part of the thesis describes the numerical testing of the previously mentioned underestimators together with approximations obtained by considering lifted approximations of the convex hull of the (x x y) terms. Two sets of instances are generated for this test and the descriptions of the procedures to generate the instances are detailed here. By analyzing the numerical results we can conclude that our proposed underestimator has the best behavior in the family of instances where the only non-linear terms present are of the form (x x y). Problems originating from least squares are much harder to solve than the other class of problems. In this class of problems the efficiency of linear programming solvers plays a big role and on average the methods that use these solvers perform better than the others.

We study techniques, approximation algorithms, structural properties and lower bounds related to applications of linear programs in combinatorial optimization. The following "Steiner tree problem" is central: given a graph with a distinguished subset of required vertices, and costs for each edge, find a minimum-cost subgraph that connects the required vertices. We also investigate the areas of network design, multicommodity flows, and packing/covering integer programs. All of these problems are NP-complete so it is natural to seek approximation algorithms with the best provable approximation ratio. Overall, we show some new techniques that enhance the already-substantial corpus of LP-based approximation methods, and we also look for limitations of these techniques. The first half of the thesis deals with linear programming relaxations for the Steiner tree problem. The crux of our work deals with hypergraphic relaxations obtained via the well-known full component decomposition of Steiner trees; explicitly, in this view the fundamental building blocks are not edges, but hyperedges containing two or more required vertices. We introduce a new hypergraphic LP based on partitions. We show the new LP has the same value as several previously-studied hypergraphic ones; when no Steiner nodes are adjacent, we show that the value of the well-known bidirected cut relaxation is also the same. A new partition uncrossing technique is used to demonstrate these equivalences, and to show that extreme points of the new LP are well-structured. We improve the best known integrality gap on these LPs in some special cases. We show that several approximation algorithms from the literature on Steiner trees can be re-interpreted through linear programs, in particular our hypergraphic relaxation yields a new view of the Robins-Zelikovsky 1.55-approximation algorithm for the Steiner tree problem. The second half of the thesis deals with a variety of fundamental problems in combinatorial optimization. We show how to apply the iterated LP relaxation framework to the problem of multicommodity integral flow in a tree, to get an approximation ratio that is asymptotically optimal in terms of the minimum capacity. Iterated relaxation gives an infeasible solution, so we need to finesse it back to feasibility without losing too much value. Iterated LP relaxation similarly gives an O(k^2)-approximation algorithm for packing integer programs with at most k occurrences of each variable; new LP rounding techniques give a k-approximation algorithm for covering integer programs with at most k variable per constraint. We study extreme points of the standard LP relaxation for the traveling salesperson problem and show that they can be much more complex than was previously known. The k-edge-connected spanning multi-subgraph problem has the same LP and we prove a lower bound and conjecture an upper bound on the approximability of variants of this problem. Finally, we show that for packing/covering integer programs with a bounded number of constraints, for any epsilon > 0, there is an LP with integrality gap at most 1 + epsilon.

Several important compiler optimizations such as instruction scheduling and register allocation are fundamentally hard and are usually solved using heuristics or approximate solutions. In contrast, this thesis examines optimal solutions to three combinatorial problems in compiler optimization. The first problem addresses instruction scheduling for clustered architectures, popular in embedded systems. Given a set of instructions the optimal solution gives the best possible schedule for a given clustered architectural model. The problem is solved using a decomposition technique applied to constraint programming which determines the spatial and temporal schedule using an integrated approach. The experiments show that our solver can tradeoff some compile time efficiency to solve most instances in standard benchmarks giving significant performance improvements. The second problem addresses instruction selection in the compiler code generation phase. Given the intermediate representation of code the optimal solution determines the sequence of equivalent machine instructions as it optimizes for code size. This thesis shows that a large number of benchmark instances can be solved optimally using constraint programming techniques. The third problem addressed is the placement of data in memory for efficient cache utilization. Using the data access patterns of a given program, our algorithm determines a placement to reorganize data in memory which would result in fewer cache misses. By focusing on graph theoretic placement techniques it is shown that there exist, in special cases, efficient and optimal algorithms for data placement that significantly improve cache utilization. We also propose heuristic solutions for solving larger instances for which provably optimal solutions cannot be determined using polynomial time algorithms. We demonstrate that cache hit rates can be significantly improved by using profiling techniques over a wide range of benchmarks and cache configurations.

The Kerngen Module in MATLAB can be used to optimize a filter with regards to an ideal filter; while taking into consideration the weighting function and the spatial mask. To be able to remotely do these optimizations from a standard web browser over a TCP/IP network connection would be of interest. This master’s thesis covers the project of doing such a system; along with an attempt to graphically display three-dimensional filters and also save the optimized filter in XML format. It includes defining an appropriate DTD for the representation of the filter. The result is a working system, with a server and client written in the programming language PIKE.

We introduce a very simple but efficient idea for branch & bound (B&B) algorithms in global optimization (GO). As input for our generic algorithm, we need an upper bound algorithm for the GO maximization problem and a branching rule. The latter reduces the problem into several smaller subproblems of the same type. The new B&B approach delivers one global optimizer or, if stopped before finished, improved upper and lower bounds for the problem. Its main difference to commonly used B&B techniques is its ability to approximate the problem from above and from below while traversing the problem tree. It needs no supplementary information about the system optimized and does not consume more time than classical B&B techniques. Experimental results with the maximum clique problem illustrate the benefit of this new method. (author's abstract) / Series: Working Papers on Information Systems, Information Business and Operations