Theses and Dissertations from UMD
Permanent URI for this communityhttp://hdl.handle.net/1903/2
New submissions to the thesis/dissertation collections are added automatically as they are received from the Graduate School. Currently, the Graduate School deposits all theses and dissertations from a given semester after the official graduation date. This means that there may be up to a 4 month delay in the appearance of a give thesis/dissertation in DRUM
More information is available at Theses and Dissertations at University of Maryland Libraries.
Browse
3 results
Search Results
Item Simulating and Optimizing: Military Manpower Modeling and Mountain Range Options(2009) Hall, Andrew Oscar; Fu, Michael C; Business and Management: Decision & Information Technologies; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)In this dissertation we employ two different optimization methodologies, dynamic programming and linear programming, and stochastic simulation. The first two essays are drawn from military manpower modeling and the last is an application in finance. First, we investigate two different models to explore the military manpower system. The first model describes the optimal retirement behavior for an Army officer from any point in their career. We address the optimal retirement policies for Army officers, incorporating the current retirement system, pay tables, and Army promotion opportunities. We find that the optimal policy for taste-neutral Lieutenant Colonels is to retire at 20 years. We demonstrate the value and importance of promotion signals regarding the promotion distribution to Colonel. Signaling an increased promotion opportunity from 50% to 75% for the most competitive officers switches their optimal policy at twenty years to continuing to serve and competing for promotion to Colonel. The second essay explores the attainability and sustainability of Army force profiles. We propose a new network structure that incorporates both rank and years in grade to combine cohort, rank, and specialty modeling without falling into the common pitfalls of small cell size and uncontrollable end effects. This is the first implementation of specialty modeling in a manpower model for U.S. Army officers. Previous specialty models of the U.S. Army manpower system have isolated accession planning for Second Lieutenants and the Career Field Designation process for Majors, but this is the first integration of rank and specialty modeling over the entire officer's career and development of an optimal force profile. The last application is drawn from financial engineering and explores several exotic derivatives that are collectively known Mountain Range options, employing Monte Carlo simulation to price these options and developing gradient estimates to study the sensitivities to underlying parameters, known as "the Greeks". We find that IPA and LR/SF methods are efficient methods of gradient estimation for Mountain Range products at a considerably reduced computation cost compared with the commonly used finite difference methods.Item Column Generation in Infeasible Predictor-Corrector Methods for Solving Linear Programs(2009) Nicholls, Stacey Oneeta; O'Leary, Dianne P.; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Primal &ndash dual interior &ndash point methods (IPMs) are distinguished for their exceptional theoretical properties and computational behavior in solving linear programming (LP) problems. Consider solving the primal &ndash dual LP pair using an IPM such as a primal &ndash dual Affine &ndash Scaling method, Mehrotra's Predictor &ndash Corrector method (the most commonly used IPM to date), or Potra's Predictor &ndash Corrector method. The bulk of the computation in the process stems from the formation of the normal equation matrix, AD2A T, where A \in \Re {m times n} and D2 = S{-1}X is a diagonal matrix. In cases when n >> m, we propose to reduce this cost by incorporating a column generation scheme into existing infeasible IPMs for solving LPs. In particular, we solve an LP problem based on an iterative approach where we select a &ldquo small &rdquo subset of the constraints at each iteration with the aim of achieving both feasibility and optimality. Rather than n constraints, we work with k = |Q| \in [m,n] constraints at each iteration, where Q is an index set consisting of the k most nearly active constraints at the current iterate. The cost of the formation of the matrix, AQ DQ2 AQT, reduces from &theta(m2 n) to &theta(m2 k) operations, where k is relatively small compared to n. Although numerical results show an occasional increase in the number of iterations, the total operation count and time to solve the LP using our algorithms is, in most cases, small compared to other &ldquo reduced &rdquo LP algorithms.Item Applications of Genetic Algorithms, Dynamic Programming, and Linear Programming to Combinatorial Optimization Problems(2008-10-16) Wang, Xia; Golden, Bruce L.; Mathematics; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Combinatorial optimization problems are important in operations research and computer science. They include specific, well-known problems such as the bin packing problem, sequencing and scheduling problems, and location and network design problems. Each of these problems has a wide variety of real-world applications. In addition, most of these problems are inherently difficult to solve, as they are NP-hard. No polynomial-time algorithm currently exists for solving them to optimality. Therefore, we are interested in developing high-quality heuristics that find near-optimal solutions in a reasonable amount of computing time. In this dissertation, we focus on applications of genetic algorithms, dynamic programming, and linear programming to combinatorial optimization problems. We apply a genetic algorithm to solve the generalized orienteering problem. We use a combination of genetic algorithms and linear program to solve the concave cost supply scheduling problem, the controlled tabular adjustment problem, and the two-stage transportation problem. Our heuristics are simple in structure and produce high-quality solutions in a reasonable amount of computing time. Finally, we apply a dynamic programming-based heuristic to solve the shortest pickup planning tour problem with time windows.