Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / "June 2015." Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 85-90). / Developed in the 1970's and 1980's, the Traffic Alert and Collision Avoidance System (TCAS) is the last safety net to prevent an aircraft mid-air collision. Although TCAS has been historically very effective, TCAS logic must adapt to meet the new challenges of our increasingly busy modern airspace. Numerous studies have shown that formulating collision avoidance as a partially-observable Markov decision process (POMDP) can dramatically increase system performance. However, the POMDP formulation relies on a number of design parameters modifying these parameters can dramatically alter system behavior. Prior work tunes these design parameters with respect to a single performance metric. This thesis extends existing work to handle more than one performance metric. We introduce an algorithm for preference elicitation that allows the designer to meaningfully define a utility function. We also discuss and implement a genetic algorithm that can perform multi-objective optimization directly. By appropriately applying these two methods, we show that we are able to tune the POMDP design parameters more effectively than existing work. / by John R. Lepird. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 108-114). / In this thesis, we employ healthcare analytics to inform system-level changes at Massachusetts General Hospital that could lead to a significant reduction in avoidable hospitalization days and improvement in patients outcomes. The first area of focus is around avoidable bed-days in the ICU. Many surgical patients experience non-clinical delays when they transfer from the ICU to a subsequent general care unit where they are expected to continue their recovery. As a result, they spend a longer time in the ICU than necessary. In spite of several studies that suggest out-of-ICU transfer delays are quite common, there is little work that quantifies the impact on patient recovery. Using multiple statistical approaches including regression and matching, we obtain a robust result that suggests that non-clinical transfer delays from the ICU delay the patient's recovery as well as extend the hospital LOS. Specifically, the analysis shows that each day that the patient is delayed in the ICU for non-clinical reasons increases hospital LOS by 0.71 days (p-value < 0.01) and the patient's progress of care by 0.32 days (p-value < 0.01), on average. The second area of focus is concerned with bed-days from heart failure (HF) admissions. Much of the current work in reducing HF hospitalizations promotes interventions after the patient is hospitalized, aiming to prevent subsequent hospitalizations within 30 days. In contrast, we focus on reducing overall hospitalizations from the general HF population. We first analyze the outpatient access for these patients before they are admitted to the hospital (mostly) through the Emergency Department. One of the main findings is that in more than half of these admissions, the patient did not have a completed appointment with any outpatient clinic (Primary Care, Cardiology, or Home Health) during the two weeks prior to hospitalization. This reveals the need for improved outpatient-based preventative measures to manage HF patients. To partially address this challenge, we develop a predictive model using a logistic regression to predict the risk of a HF-related admission within the next six months. The model performs quite well with an out-of-sample AUC of 0.78. / by Jazmin D. Furtado. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 143-149). / The Last Mile Problem refers to the provision of travel service from the nearest public transportation node to a home or office. Last Mile Transportation Systems (LMTS) are critical extensions to traditional public transit systems. We study the LMTS from three perspectives. The first part of this thesis focuses on the design of a LMTS. We study the supply side of LMTS in a stochastic setting, with batch demands resulting from the arrival of groups of passengers at rail stations or bus stops who request last-mile service. Closed-form bounds and approximations are derived for the performance of LMTS as a function of the fundamental design parameters of such systems. It is shown that a particular strict upper bound and an approximate upper bound perform consistently and remarkably well. These expressions can therefore be used for the preliminary planning and design of Last Mile Transportation Systems. The second part of the thesis studies operating strategies for LMTS. Routes and schedules are determined for a multi-vehicle fleet of delivery vehicles with the objective of minimizing the waiting time and riding time of passengers. A myopic operating strategy is introduced first. Two more advanced operating strategies are then described, one based on a metaheuristic using tabu search and the other using an exact Mixed Integer Programming model, which is solved approximately in two stages. It is shown that all three operating strategies greatly outperform the naive strategy of fixed routes and fixed vehicle dispatching schedules. The third part presents a new perspective to the study of passenger utility functions in a LMTS. The unknown parameters of a passenger utility function are treated as unobserved events, and the characteristics of the transportation trips made by the passengers are treated as observed outcomes. We propose a method to identify the probability measures of the events given observations of the frequencies of outcomes by introducing the concept and assumptions of the Core Determining Class. We introduce a combinatorial algorithm in which the noise in the observations data is ignored and a general procedure in which data noise is taken into consideration. / by Hai Wang. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (p. 153-154). / In this thesis, we create a comprehensive model and efficient solution technique for generating air operations plans. Previous air operations models have fallen short in at least one of the following areas: routing. real-time re-planning of aircraft. problem size capability, plan generation speed. and optimal packaging of aircraft. The purpose of the Composite Mission Variable Decomposition (CMVD) approach is to plan and re-plan air operations for a real conflict as it unfolds. Previous model shortcomings were the result of two main reasons: the models were developed for other purposes (typically weapons studies). or developers could not create techniques that can efficiently generate plans while including the listed areas. The application of conventional optimization modeling to an operations problem that includes aspects such as routing and real-time re-planning forms a model that has millions of constraints and a weak linear programming relaxation. The Composite Mission Variable MNodeils the first step in overcoming the above shortcomings because it greatly decreases the number of constraints in the optimization model. and the linear programming relaxation provides tight bounds. The Composite Mission Variable Model combines multiple air operations planning decisions into a composite mission variable. Many complex constraints that are explicitly included in a conventional model are implicitly enforced in the composite mission variables. We apply price coordinated decomposition to generate the composite mission variables. Price coordination reduces the number of variables in the Composite Mission Variable Model and allows for parallel processing of composite mission variable generation. CMVD creates air operations plans in minutes for scenarios with thousands of targets. while including important capabilities such as routing and re-planning of aircraft in air. CMVD is tested in simulated conflicts and its performance validated by comparisons with a heuristic approach for generating plans. / by Christopher D. Barth. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2016. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 176-182). / In the context of a world flooded with data, the Internet of Things (IoT) is exploding. This thesis considers the problem of applying IoT technology to the reduction of costs in the iron ore mining industry, to compensate for the iron ore price slumping observed over the past years. More specifically, we focused on improving the quality of the output in a data-driven iron ore concentration factory. In this plant, mined iron ore goes through a series of complex physical and chemical transformations so as to increase the concentration in iron and reduce the concentration in impurities such as silica. In this thesis, we developed an IoT infrastructure comprising of machines, a network of sensors, a database, a random forest prediction model, an algorithm for adjusting its cutoff parameter dynamically, and a predictive maintenance algorithm. It can preventively detect and maybe fix poor quality events in the iron ore concentration factory, improving the overall quality and decreasing costs. The random forest model was selected among other anomaly detection techniques. It is able, on an independent test data set, with an AUC of about 0.92, to detect 90% of the poor quality events, with a false positive rate of 23.02%, lowered by the dynamic cutoff algorithm. These methods can be applied to any factory in any industry, as long as it has a good infrastructure of sensors, providing sufficiently precise and frequent data. / by Carl Elie Saroufim. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 181-185). / As online retailing - or e-tailing - continues to grow as more and more customers buy physical goods on the internet, finding ways to reduce the cost and environmental impact of outbound shipping in this sector will become increasingly important. We investigate the impact of making poor fulfillment and replenishment decisions using data obtained from a large American online retailer. Then, we propose implementable - i.e., computationally tractable and relatively intuitive - solutions for both the fulfillment and replenishment problems, both tested either on actual data from our industrial partner or on small but realistic models. We first focus on the fulfillment problem, namely, deciding from which warehouse(s) to fulfill a customer's order when several options exist. We propose a heuristic that utilizes the dual values of a transportation linear program to estimate the opportunity cost of depleting inventory from a warehouse. This linear program values inventory at a warehouse due to both its geography and the size of its catalogue. After showing that this linear program is asymptotically optimal - using concepts developed in airline network revenue management - we then test the heuristic on industry data, showing a 1% reduction in outbound shipping costs as compared to a myopic fulfillment policy. The last part of the thesis focuses on replenishment. Every period, for each item, the network places an order to restock all the warehouses. Complicating this decision are two factors. First, the orders will not arrive immediately, but rather require a lead time to be delivered. During this time a random number of customers will place orders with the network. Second, any customer's order may be filled from any warehouse, which becomes important when warehouses stock out of an item. Therefore, it is not trivial to calculate the optimal inventory to order to each warehouse. We show that using a standard replenishment policy - popular in practice - can lead to dynamics that result in increased outbound shipping costs. We propose a replenishment policy heuristic that is intuitive and performs well on examples. This heuristic has two variants: a simpler one that assumes deterministic demand, and a more complicated one that accounts for stochasticity. / by Jason Andrew Acimovic. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 107-112). / We propose new decomposition methods for use on broad families of stochastic and robust optimization problems in order to yield tractable approaches for large-scale real world application. We introduce a new type of a Markov decision problem named the Generalized Rest less Bandits Problem that encompasses a broad generalization of the restless bandit problem. For this class of stochastic optimization problems, we develop a nested policy heuristic which iteratively solves a series of sub-problems operating on smaller bandit systems. We also develop linear-optimization based bounds for the Generalized Restless Bandit problem and demonstrate promising computational performance of the nested policy heuristic on a large-scale real world application of search term selection for sponsored search advertising. We further study the distributionally robust optimization problem with known mean, covariance and support. These optimization models are attractive in their real world applications as they require the model consumer to only rely on those statistics of uncertainty that are known with relative confidence rather than making arbitrary assumptions about the exact dynamics of the underlying distribution of uncertainty. Known to be AP - hard, current approaches invoke tractable but often weak relaxations for real-world applications. We develop a decomposition method for this family of problems which recursively derives sub-policies along projected dimensions of uncertainty and provides a sequence of bounds on the value of the derived policy. In the development of this method, we prove that non-convex quadratic optimization in n-dimensions over a box in two-dimensions is efficiently solvable. We also show that this same decomposition method yields a promising heuristic for the MAXCUT problem. We then provide promising computational results in the context of a real world fixed income portfolio optimization problem. The decomposition methods developed in this thesis recursively derive sub-policies on projected dimensions of the master problem. These sub-policies are optimal on relaxations which admit "tight" projections of the master problem; that is, the projection of the feasible region for the relaxation is equivalent to the projection of that of master problem along the dimensions of the sub-policy. Additionally, these decomposition strategies provide a hierarchical solution structure that aids in solving large-scale problems. / by Adrian Bernard Druke Becker. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. / Includes bibliographical references (p. 83-89). / In the first part, we study the problem of minimizing a separable concave function over a polyhedron. We assume the concave functions are nonnegative nondecreasing on R+, and the polyhedron is in RI' (these assumptions can be relaxed further under suitable technical conditions). We show how to approximate this problem to 1+ E precision in optimal value by a piecewise linear minimization problem so that the number of resulting pieces is polynomial in the input size of the original problem and linear in 1/c. For several concave cost problems, the resulting piecewise linear problem can be reformulated as a classical combinatorial optimization problem. As a result of our bound, a variety of polynomial-time heuristics, approximation algorithms, and exact algorithms for classical combinatorial optimization problems immediately yield polynomial-time heuristics, approximation algorithms, and fully polynomial-time approximation schemes for the corresponding concave cost problems. For example, we obtain a new approximation algorithm for concave cost facility location, and a new heuristic for concave cost multi commodity flow. In the second part, we study several concave cost problems and the corresponding combinatorial optimization problems. We develop an algorithm design technique that yields a strongly polynomial primal-dual algorithm for a concave cost problem whenever such an algorithm exists for the corresponding combinatorial optimization problem. / (cont.) Our technique preserves constant-factor approximation ratios as well as ratios that depend only on certain problem parameters, and exact algorithms yield exact algorithms. For example, we obtain new approximation algorithms for concave cost facility location and concave cost joint replenishment, and a new exact algorithm for concave cost lot-sizing. In the third part, we study a real-time optimization problem arising in the operations of a leading internet retailer. The problem involves the assignment of orders that arrive via the retailer's website to the retailer's warehouses. We model it as a concave cost facility location problem, and employ existing primal-dual algorithms and approximations of concave cost functions to solve it. On past data, we obtain solutions on average within 1.5% of optimality, with running times of less than 100ms per problem. / by Dan Stratila. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2005. / Includes bibliographical references (leaves 157-162). / In this thesis we study different combinatorial optimization problems. These problems arise in many practical settings where there is a need for finding good solutions fast. The first class of problems we study are vehicle routing problems, and the second type of problems are sequencing problems. We study approximation algorithms and local search heuristics for these problems. First, we analyze the Vehicle Routing Problem (VRP) with and without split deliveries. In this problem, we have to route vehicles from the depot to deliver the demand to the customers while minimizing the total traveling cost. We present a lower bound for this problem, improving a previous bound of Haimovich and Rinnooy Kan. This bound is then utilized to improve the worst-case approximation algorithm of the Iterated Tour Partitioning (ITP) heuristic when the capacity of the vehicles is constant. Second, we analyze a particular case of the VRP, when the customers are uniformly distributed i.i.d. points on the unit square of the plane, and have unit demand. We prove that there exists a constant c > 0 such that the ITP heuristic is a 2 - c approximation algorithm with probability arbitrarily close to one as the number of customers goes to infinity. This result improves the approximation factor of the ITP heuristic under the worst-case analysis, which is 2. We also generalize this result and previous ones to the multi-depot case. Third, we study a language to generate Very Large Scale Neighborhoods for sequencing problems. Local search heuristics are among the most popular approaches to solve hard optimization problems. / (cont.) Among them, Very Large Scale Neighborhood Search techniques present a good balance between the quality of local optima and the time to search a neighborhood. We develop a language to generate exponentially large neighborhoods for sequencing problems using grammars. We develop efficient generic dynamic programming solvers that determine the optimal neighbor in a neighborhood generated by a grammar for a list of sequencing problems, including the Traveling Salesman Problem and the Linear Ordering Problem. This framework unifies a variety of previous results on exponentially large neighborhoods for the Traveling Salesman Problem. / by Agustín Bompadre. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2016. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 99-100). / Substantial progress has been made in the estimation of sparse high dimensional precision matrices from scant datasets. This is important because precision matrices underpin common tasks such as regression, discriminant analysis, and portfolio optimization. However, few good algorithms for this task exist outside the space of L1 penalized optimization approaches like GLASSO. This thesis introduces LGM, a new algorithm for the estimation of sparse high dimensional precision matrices. Using the framework of probabilistic graphical models, the algorithm performs robust covariance estimation to generate potentials for small cliques and fuses the local structures to form a sparse yet globally robust model of the entire distribution. Identification of appropriate local structures is done through stochastic discrete optimization. The algorithm is implemented in Matlab and benchmarked against competitor algorithms for an array of synthetic datasets. Simulation results suggest that LGM may outperform GLASSO when model sparsity is especially important and when variables in the dataset belong to a number of closely related (if unknown) groups. / by Peter Alexander Lee. / S.M.