Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2005. / Includes bibliographical references (p. 65-67). / This thesis is divided into two parts sharing the common theme of fully polynomial time approximation schemes. In the first part, we introduce a generic approach for devising fully polynomial time approximation schemes for a large class of problems that we call list scheduling problems. Our approach is simple and unifying, and many previous results in the literature follow as direct corollaries of our main theorem. In the second part, we tackle a more difficult problem; the stochastic lot sizing problem, and give the first fully polynomial time approximation scheme for it. Our approach is based on simple techniques that could arguably have wider applications outside of just designing fully polynomial time approximation schemes. / by Mohamed Mostagir. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 66-68). / Myocardial infarction is a derivative of heart disease that is a growing concern in the United States today. With heart disease becoming increasingly predominant, it is important to not only take steps toward preventing myocardial infarction, but also towards predicting future myocardial infarctions. If we can predict that the dynamic pattern of an individual's diagnostic history matches a pattern already identified as high-risk for myocardial infarction, more rigorous preventative measures can be taken to alter that individual's trajectory of health so that it leads to a better outcome. In this paper we utilize classification and clustering data mining methods concurrently to determine whether a patient is at risk for a future myocardial infarction. Specifically, we apply the algorithms to medical claims data from more than 47,000 members over five years to: 1) find different groups of members that have interesting temporal diagnostic patterns leading to myocardial infarction and 2) provide out-of-sample predictions of myocardial infarction for these groups. Using clustering methods in conjunction with classification algorithms yields improved predictions of myocardial infarction over using classification alone. In addition to improved prediction accuracy, we found that the clustering methods also effectively split the members into groups with different and meaningful temporal diagnostic patterns leading up to myocardial infarction. The patterns found can be a useful profile reference for identifying patients at high-risk for myocardial infarction in the future. / by Kimberly N. Shenk. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2005. / Includes bibliographical references (p. 149-151). / Numerous complex real-world applications are either theoretically intractable or unable to be solved in a practical amount of time. Researchers and practitioners are forced to implement heuristics in solving such problems that can lead to highly sub-optimal solutions. Our research focuses on inserting a human "in-the-loop" of the decision-making or problem solving process in order to generate solutions in a timely manner that improve upon those that are generated either scolely by a human or solely by a computer. We refer to this as Human-Machine Collaborative Decision-Making (HMCDM). The typical design process for developing human-machine approaches either starts with a human approach and augments it with decision-support or starts with an automated approach and augments it with operator input. We provide an alternative design process by presenting an 1HMCDM methodology that addresses collaboration from the outset of the design of the decision- making approach. We apply this design process to a complex military resource allocation and planning problem which selects, sequences, and schedules teams of unmanned aerial vehicles (UAVs) to perform sensing (Intelligence, Surveillance, and Reconnaissance - ISR) and strike activities against enemy targets. Specifically, we examined varying degrees of human-machine collaboration in the creation of variables in the solution of this problem. We also introduce an IIHMCDM method that combines traditional goal decomposition with a model formulation into an Iterative Composite Variable Approach for solving large-scale optimization problems. / (cont.) Finally, we show through experimentation the potential for improvement in the quality and speed of solutions that can be achieved through the use of an HMCDM approach. / by Jeremy S. Malasky. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 201-213). / In this thesis, we examine a recent paradigm for solving dynamic optimization problems under uncertainty, whereby one considers decisions that depend directly on the sequence of observed disturbances. The resulting policies, called recourse decision rules, originated in Stochastic Programming, and have been widely adopted in recent works in Robust Control and Robust Optimization; the specific subclass of affine policies has been found to be tractable and to deliver excellent empirical performance in several relevant models and applications. In the first chapter of the thesis, using ideas from polyhedral geometry, we prove that disturbance-affine policies are optimal in the context of a one-dimensional, constrained dynamical system. Our approach leads to policies that can be computed by solving a single linear program, and which bear an interesting decomposition property, which we explore in connection with a classical inventory management problem. The result also underscores a fundamental distinction between robust and stochastic models for dynamic optimization, with the former resulting in qualitatively simpler problems than the latter. In the second chapter, we introduce a hierarchy of polynomial policies that are also directly parameterized in the observed uncertainties, and that can be efficiently computed using semidefinite optimization methods. The hierarchy is asymptotically optimal and guaranteed to improve over affine policies for a large class of relevant problems. To test our framework, we consider two problem instances arising in inventory management, for which we find that quadratic policies considerably improve over affine ones, while cubic policies essentially close the optimality gap. In the final chapter, we examine the problem of dynamically pricing inventories in multiple items, in order to maximize revenues. For a linear demand function, we propose a distributionally robust uncertainty model, argue how it can be constructed from limited historical data, and show how pricing policies depending on the observed model mis-specifications can be computed by solving second-order conic or semidefinite optimization problems. We calibrate and test our model using both synthetic data, as well as real data from a large US retailer. Extensive Monte-Carlo simulations show 3 that adaptive robust policies considerably improve over open-loop formulations, and are competitive with popular heuristics in the literature. / by Dan Andrei Iancu. / Ph.D.

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. 157-165). / Many if not most of the core problems studied in operations management fall into the category of multi-stage stochastic optimization models, whereby one considers multiple, often correlated decisions to optimize a particular objective function under uncertainty on the system evolution over the future horizon. Unfortunately, computing the optimal policies is usually computationally intractable due to curse of dimensionality. This thesis is focused on providing provably near-optimal and tractable policies for some of these challenging models arising in the context of inventory control, capacity planning and revenue management; specifically, on the design of approximation algorithms that admit worst-case performance guarantees. In the first chapter, we develop new algorithmic approaches to compute provably near-optimal policies for multi-period stochastic lot-sizing inventory models with positive lead times, general demand distributions and dynamic forecast updates. The proposed policies have worst-case performance guarantees of 3 and typically perform very close to optimal in extensive computational experiments. We also describe a 6-approximation algorithm for the counterpart model under uniform capacity constraints. In the second chapter, we study a class of revenue management problems in systems with reusable resources and advanced reservations. A simple control policy called the class selection policy (CSP) is proposed based on solving a knapsack-type linear program (LP). We show that the CSP and its variants perform provably near-optimal in the Halfin- Whitt regime. The analysis is based on modeling the problem as loss network systems with advanced reservations. In particular, asymptotic upper bounds on the blocking probabilities are derived. In the third chapter, we examine the problem of capacity planning in joint ventures to meet stochastic demand in a newsvendor-type setting. When resources are heterogeneous, there exists a unique revenue-sharing contract such that the corresponding Nash Bargaining Solution, the Strong Nash Equilibrium, and the system optimal solution coincide. The optimal scheme rewards every participant proportionally to her marginal cost. When resources are homogeneous, there does not exist a revenue-sharing scheme which induces the system optimum. Nonetheless, we propose provably good revenue-sharing contracts which suggests that the reward should be inversely proportional to the marginal cost of each participant. / by Cong Shi. / Ph.D.

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2020 / Cataloged from student-submitted PDF of thesis. / Includes bibliographical references (pages 179-186). / This thesis tackles two major challenges of urban transportation optimization problems: (i) high-dimensionality and (ii) uncertainty in both demand and supply. These challenges are addressed from both modeling and algorithm design perspectives. The first part of this thesis focuses on the formulation of analytical transient stochastic link transmission models (LTM) that are computationally tractable and suitable for largescale network analysis and optimization. We first formulate a stochastic LTM based on the model of Osorio and Flötteröd (2015). We propose a formulation with enhanced scalability. In particular, the dimension of the state space is linear, rather than cubic, in the link's space capacity. We then propose a second formulation that has a state space of dimension two; it scales independently of the link's space capacity. Both link models are validated versus benchmark models, both analytical and simulation-based. The proposed models are used to address a probabilistic formulation of a city-wide signal control problem and are benchmarked versus other existing network models. Compared to the benchmarks, both models derive signal plans that perform systematically better considering various performance metrics. The second model, compared to the first model, reduces the computational runtime by at least two orders of magnitude. The second part of this thesis proposes a technique to enhance the computational efficiency of simulation-based optimization (SO) algorithms for high-dimensional discrete SO problems. The technique is based on an adaptive partitioning strategy. It is embedded within the Empirical Stochastic Branch-and-Bound (ESB&B) algorithm of Xu and Nelson (2013). This combination leads to a discrete SO algorithm that is both globally convergent and has good small sample performance. The proposed algorithm is validated and used to address a high-dimensional car-sharing optimization problem. / by Jing Lu. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Aeronautics and Astronautics; and, (S.M.)--Massachusetts Institute of Technology, Operations Research Center, 2004. / Includes bibliographical references (p. 113-118). / For many vehicles, obstacles, and targets, coordination of a fleet of Unmanned Aerial Vehicles (UAVs) is a very complicated optimization problem, and the computation time typically increases very rapidly with the problem size. Previous research proposed an approach to decompose this large problem into task assignment and trajectory problems, while capturing key features of the coupling between them. This enabled the control architecture to solve an assignment problem first to determine a sequence of waypoints for each vehicle to visit, and then concentrate on designing paths to visit these pre-assigned waypoints. Although this approach greatly simplifies the problem, the task assignment optimization was still too slow for real-time UAV operations. This thesis presents a new approach to the task assignment problem that is much better suited for replanning in a dynamic battlefield. The approach, called the Receding Horizon Task Assignment (RHTA) algorithm, is shown to achieve near-optimal performance with computational times that are feasible for real-time implementation. Further, this thesis extends the RHTA algorithm to account for the risk, noise, and uncertainty typically associated with the UAV environment. This work also provides new insights on the distinction between UAV coordination and cooperation. The benefits of these improvements to the UAV task assignment algorithms are demonstrated in several simulations and on two hardware platforms. / by Mehdi Alighanbari. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Mechanical Engineering; and, (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / "June 2001." / Includes bibliographical references (leaf 67). / by Young Jae Jang. / S.M.

No description available.

Thesis (S.M.)--Massachusetts Institute of Technology, Dept. of Ocean Engineering; and, (S.M.)--Massachusetts Institute of Technology, Operations Research Center, 1997. / Includes bibliographical references (leaves 56-57). / by Te-San Liao. / S.M.