Computer Science Theses and Dissertations
Permanent URI for this collectionhttp://hdl.handle.net/1903/2756
Browse
18 results
Search Results
Item Stabilizing Column Generation via Dual Optimal Inequalities with Applications in Logistics and Robotics(2020) Haghani, Naveed; Balan, Radu; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This work addresses the challenge of stabilizing column generation (CG) via dual optimal inequalities (DOI). We present two novel classes of DOI for the general context of set cover problems. We refer to these as Smooth DOI (S-DOI) and Flexible DOI (F-DOI). S-DOI can be interpreted as allowing for the undercovering of items at the cost of overcovering others and incurring an objective penalty. SDOI leverage the fact that dual values associated with items should change smoothly over space. F-DOI can be interpreted as offering primal objective rewards for the overcovering of items. We combine these DOI to produce a joint class of DOI called Smooth-Flexible DOI (SF-DOI). We apply these DOI to three classical problems in logistics and operations research: the Single Source Capacitated Facility Location Problem, the Capacitated p-Median Problem, and the Capacitated Vehicle Routing Problem. We prove that these DOI are valid and are guaranteed to not alter the optimal solution of CG. We also present techniques for their use in the case of solvingCG with relaxed column restrictions. This work also introduces a CG approach to Multi-Robot Routing (MRR). MRR considers the problem of routing a fleet of robots in a warehouse to collectively complete a set of tasks while prohibiting collisions. We present two distinct formulations that tackle unique problem variants. The first we model as a set packing problem, while the second we model as a set cover problem. We show that the pricing problem for both approaches amounts to an elementary resource constrained shortest path problem (ERCSPP); an NP-hard problem commonly studied in other CG problem contexts. We present an efficient implementation of our CG approach that radically reduces the state size of the ERCSPP. Finally, we present a novel heuristic algorithm for solving the ERCSPP and offer probabilistic guarantees forits likelihood to deliver the optimal solution.Item Compartmental and Simulation Models for Evaluating MedKit Prepositioning Strategies for Anthrax Attack Response(2011) Houck, Michelle Lee; Herrmann, Jeffrey W; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Since the 2001 anthrax attacks, public health officials have become concerned with planning for a potential large scale attack. Researchers have worked to model attack scenarios in order to evaluate various response policies. One response policy that has been proposed is to preemptively distribute antibiotics to the public in the form of MedKits before an attack occurs. Despite numerous models and studies, there has not been a model to study the effect of distributing MedKits on the expected number of deaths in an attack. We develop a discrete-time compartmental difference equation model to analyze the policy. The results show that distributing any number of MedKits reduces the number of deaths expected in all scenarios tested. We analyze under what circumstances the MedKits have the largest life-saving impact. We also develop a stochastic transition model to demonstrate the accuracy of the MedKits model results.Item Prioritizing Patients: Stochastic Dynamic Programming for Surgery Scheduling and Mass Casualty Incident Triage(2011) Herring, William L.; Herrmann, Jeffrey W; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The research presented in this dissertation contributes to the growing literature on applications of operations research models to problems in healthcare through the development and analysis of mathematical models for two fundamental problems facing nearly all hospitals: the single-day surgery scheduling problem and planning for triage in the event of a mass casualty incident. Both of these problems can be understood as sequential decision-making processes aimed at prioritizing between different classes of patients under significant uncertainty and are modeled using stochastic dynamic programming. Our study of the single-day surgery scheduling problem represents the first model to capture the sequential nature of the operating room (OR) manager's decisions during the transition between the generality of cyclical block schedules (which allocate OR time to surgical specialties) and the specificity of schedules for a particular day (which assign individual patients to specific ORs). A case study of the scheduling system at the University of Maryland Medical Center highlights the importance of the decision to release unused blocks of OR time and use them to schedule cases from the surgical request queue (RQ). Our results indicate that high quality block release and RQ decisions can be made using threshold-based policies that preserve a specific amount of OR time for late-arriving demand from the specialties on the block schedule. The development of mass casualty incident (MCI) response plans has become a priority for hospitals, and especially emergency departments and trauma centers, in recent years. Central to all MCI response plans is the triage process, which sorts casualties into different categories in order to facilitate the identification and prioritization of those who should receive immediate treatment. Our research relates MCI triage to the problem of scheduling impatient jobs in a clearing system and extends earlier research by incorporating the important trauma principle that patients' long-term (post-treatment) survival probabilities deteriorate the longer they wait for treatment. Our results indicate that the consideration of deteriorating survival probabilities during MCI triage decisions, in addition to previously studied patient characteristics and overall patient volume, increases the total number of expected survivors.Item COMPUTATIONALLY TRACTABLE STOCHASTIC INTEGER PROGRAMMING MODELS FOR AIR TRAFFIC FLOW MANAGEMENT(2010) Glover, Charles N.; Ball, Michael O; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)A primary objective of Air Traffic Flow Management (ATFM) is to ensure the orderly flow of aircraft through airspace, while minimizing the impact of delays and congestion on airspace users. A fundamental challenge of ATFM is the vulnerability of the airspace to changes in weather, which can lower the capacities of different regions of airspace. Considering this uncertainty along with the size of the airspace system, we arrive at a very complex problem. The development of efficient algorithms to solve ATFM problems is an important and active area of research. Responding to predictions of bad weather requires the solution of resource allocation problems that assign a combination of ground delay and route adjustments to many flights. Since there is much uncertainty associated with weather predictions, stochastic models are necessary. We address some of these problems using integer programming (IP). In general, IP models can be difficult to solve. However, if "strong" IP formulations can be found, then problems can be solved quickly by state of the art IP solvers. We start by describing a multi-period stochastic integer program for the single airport stochastic dynamic ground holding problem. We then show that the linear programming relaxation yields integer optimal solutions. This is a fairly unusual property for IP formulations that can significantly reduce the complexity of the corresponding problems. The proof is achieved by defining a new class of matrices with the Monge property and showing that the formulation presented belongs to this class. To further improve computation times, we develop alternative compact formulations. These formulations are extended to show that they can also be used to model different concepts of equity and fairness as well as efficiency. We explore simple rationing methods and other heuristics for these problems both to provide fast solution times, but also because these methods can embody inherent notions of fairness. The initial models address problems that seek to restrict flow into a single airport. These are extended to problems where stochastic weather affects en route traffic. Strong formulations and efficient solutions are obtained for these problems as well.Item Integer Programming-Based Heuristics for Vehicle Routing Problems(2010) Gulczynski, Damon John; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The vehicle routing problem (VRP) has been an active field of study by operations researchers for over 50 years. Many practical applications have been presented in the literature, and many solution techniques have been developed. We discuss, develop, and computationally test integer programming-based heuristics for several variants of the standard VRP. We use integer programming to model the split delivery VRP with minimum delivery amounts, the multi-depot split delivery VRP, the period VRP, the standard VRP, and the multi-depot VRP. We apply our heuristics to benchmark problems from the literature and generate many new problems with high-quality, visually-estimated solutions. Our heuristics produce high-quality solutions in a reasonable amount of computer time. Overall, our new IP-based heuristics are very competitive with the best methods found in the VRP literature to date.Item On the Routing and Location of Mobile Facilities(2010) Halper, Russell David; Raghavan, Subramanian; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)Mobile facilities play important roles in many applications, including health care, public services, telecommunications, and humanitarian relief logistics. While mobile facilities operate in different manners, it is generally considered important for a decision maker to be capable of efficiently deploying mobile facilities. This dissertation discusses two problems on the use of mathematical models and algorithms for determining efficient deployments of mobile facilities. First we discuss the mobile facility routing problem (MFRP), which effectively models the operations of a wide class of mobile facilities that have significant relocation times and cannot service demand during transit. Chapter 2 discusses the single MFRP (SMFRP), which is to determine a route for a single mobile facility to maximize the demand serviced during a continuous-time planning horizon. We present two exact algorithms, and supporting theoretical results, when the rate demand is generated is modeled using piecewise constant functions. The first is a dynamic program that easily extends to solve cases where the demand functions take on more general forms. The second exact algorithm has a polynomial worst-case runtime. Chapter 3 discusses the MFRP, which addresses the situation when multiple mobile facilities are operating in an area. In such a case, mobile facilities at different locations may provide service to a single event, necessitating the separation of the events generating demand from the locations mobile facilities may visit in our model. We show that the MFRP is NP-hard, present several heuristics for generating effective routes, and extensively test these heuristics on a variety of simulated data sets. Chapter 4 discusses formulations and local search heuristics for the (minisum) mobile facility location problem (MFLP). This problem is to relocate a set of existing facilities and assign clients to these facilities while minimizing the movement costs of facilities and clients. We show that in a certain sense the MFLP generalizes the uncapacitated facility location and p-median problems. We observe that given a set of facility destinations, the MFLP decomposes into two polynomially solvable subproblems. Using this decomposition observation, we propose a new, compact IP formulation and novel local search heuristics. We report results from extensive computational experiments.Item Applications of Operations Research Models to Problems in Health Care(2009) Price, Carter Claiborne; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)This dissertation is divided into two parts. In the first portion, we study inflection points in biobjective variants of the traveling salesman problem (TSP) related to health care applications. In the second portion, we use a variety of techniques from operations research to improve hospital efficiency. We used a TSP variant that prioritizes the ability to return to the depot, in addition to the standard distance, to study the collection of blood from remote collection sites. In an application related to emergency response, we looked into behavior of tours generated using the target visitation problem, a TSP variant that also includes node priority in the objective function. Working with the University of Maryland Medical Center, we did three projects related to hospital efficiency. We used stochastic modeling and simulation to optimize the throughput of a cardiac surgery post-operative unit. We found that altering the mix of post-operative beds could significant increase the effective capacity. After unsuccessfully attempting to use data mining and survival analysis to predict hospital census, we performed a statistical analysis of patient length of stay patterns and discovered surgeons were improving their chances of having available beds for incoming cases by adjusting their discharge practices by day of week. In the final project, we used integer programming and heuristics to develop schedules that match incoming surgical patients with the discharge of earlier patients. The results indicate that altering the surgical schedule can substantially improve the flow of patients through the hospital.Item THE VEHICLE ROUTING PROBLEM WITH DEMAND RANGES(2009) Cornick, Namrata Uppal; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The classic Capacitated Vehicle Routing Problem (CVRP) has been studied in the Operations Research field for over 5 decades. This thesis formulates the vehicle routing problem with a variation that has not been studied in detail. It is called the Vehicle Routing Problem with Demand Ranges (VRPDR). With increasing competition, corporations are looking to minimize costs. This problem aims to reduce the cost of distributing goods by allowing flexibility in the delivered or dropped off quantity. This benefits the customer as well, by reducing storage and other inventory costs. We solve the VRPDR problem where the customer gives the distributor a demand range. The distributor is rewarded for delivering more. A metaheuristic, record-to-record travel with demand range (RTRDR), is developed which is capable of solving large problem instances. The metaheuristic is a modification of a successful CVRP metaheuristic used in the past. In this thesis, we report results on problems ranging in size from 560 to 1200 customers. The developed metaheuristic uses the Clarke-Wright procedure to get initial solutions and then applies record-to-record travel in conjunction with two-opt moves, one point moves, and two point moves. Since the problem has not been studied yet from a computational point of view, we have developed a comparison algorithm, which takes advantage of the demand range flexibility of this problem only after the algorithm has optimized for distance alone. We use the results from this algorithm as a benchmark to compare with our proposed metaheuristic RTRDR.Item Parallel and Serial Algorithms for Vehicle Routing Problems(2008) Groer, Christopher Sebastian; Golden, Bruce; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The vehicle routing problem (VRP) is a widely studied combinatorial optimization problem that has many applications. Due to its intrinsic difficulty and the size of problems encountered in practice, most solution methods for the VRP are heuristic in nature and lead to high quality, yet probably not optimal solutions. When one considers the additional constraints that can be encountered in practice, the need for high quality heuristic methods is clear. We present two new variations of the VRP suggested to us by industry contacts, the Consistent VRP and the Balanced Billing Cycle VRP. We develop solution algorithms that incorporate heuristic methods as well as integer programming. Additionally, we develop a highly effective cooperative parallel algorithm for the classical VRP that generates new best solutions to a number of well-studied benchmark instances. We present extensive computational results and describe the C/C++ library that we developed to solve these vehicle routing problems. We describe the features and design philosophy behind this library and discuss how the framework can be used to implement additional heuristic algorithms and incorporate additional constraints.Item Global Optimization of Finite Mixture Models(2007-05-31) Heath, Jeffrey Wells; Fu, Michael; Jank, Wolfgang; Applied Mathematics and Scientific Computation; Digital Repository at the University of Maryland; University of Maryland (College Park, Md.)The Expectation-Maximization (EM) algorithm is a popular and convenient tool for the estimation of Gaussian mixture models and its natural extension, model-based clustering. However, while the algorithm is convenient to implement and numerically very stable, it only produces solutions that are locally optimal. Thus, EM may not achieve the globally optimal solution in Gaussian mixture analysis problems, which can have a large number of local optima. This dissertation introduces several new algorithms designed to produce globally optimal solutions for Gaussian mixture models. The building blocks for these algorithms are methods from the operations research literature, namely the Cross-Entropy (CE) method and Model Reference Adaptive Search (MRAS). The new algorithms we propose must efficiently simulate positive definite covariance matrices of the Gaussian mixture components. We propose several new solutions to this problem. One solution is to blend the updating procedure of CE and MRAS with the principles of Expectation-Maximization updating for the covariance matrices, leading to two new algorithms, CE-EM and MRAS-EM. We also propose two additional algorithms, CE-CD and MRAS-CD, which rely on the Cholesky decomposition to construct the random covariance matrices. Numerical experiments illustrate the effectiveness of the proposed algorithms in finding global optima where the classical EM fails to do so. We find that although a single run of the new algorithms may be slower than EM, they have the potential of producing significantly better global solutions to the model-based clustering problem. We also show that the global optimum matters in the sense that it significantly improves the clustering task. Furthermore, we provide a a theoretical proof of global convergence to the optimal solution of the likelihood function of Gaussian mixtures for one of the algorithms, namely MRAS-CD. This offers support that the algorithm is not merely an ad-hoc heuristic, but is systematically designed to produce global solutions to Gaussian mixture models. Finally, we investigate the fitness landscape of Gaussian mixture models and give evidence for why this is a difficult global optimization problem. We discuss different metrics that can be used to evaluate the difficulty of global optimization problems, and then apply them to the context of Gaussian mixture models.