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. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 61-62). / A fully polynomial time approximation scheme (FPTAS) is an algorithm that returns ... -optimal solution to a maximization problem of size n, which runs in polynomial time in both ... We develop faster FPTASs for several classes of knapsack problems. In this thesis, we will first survey the relevant literature in FPTASs for knapsack problems. We propose the use of floating point arithmetic rather than the use of geometric rounding in order to simplify analysis. Given a knapsack problem that yield an ... -optimal solution for disjoint subsets S and T of decision variables, we show how to attain ... -optimal solution for the knapsack problem for the set ... We use this procedure to speed up the run-time of FPTASs for: 1. The Integer Knapsack Problem, 2. The Unbounded Integer Knapsack Problem, 3. The Multiple-Choice Knapsack Problem, and, 4. The Nonlinear Integer Knapsack Problem, Using addition ideas, we develop a fast fully polynomial time randomized approximation scheme (FPTAS) for the 0-1 Knapsack Problem, which has the run-time of ... / by Donguk Rhee. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. / Includes bibliographical references (p. 235-239). / Traditionally, industrial buyers have focused on long-term contracts for many of their purchasing needs. Recently, however, some high-tech manufacturers have started looking at more flexible contracts for non-strategic components, which enables them to buy from a variety of suppliers and the spot market. We study this type of strategies in a general framework for supply contracts, in which portfolios of contracts can be analyzed and optimized. We examine a multi-period model where expected profit is optimized, and a single-period model where a mean-variance objective is considered. In addition, we investigate what the consequences of such purchasing behavior might be. For this purpose, we study the game where suppliers compete on price and flexibility for the buyer's orders. We characterize the suppliers' Nash equilibria in pure strategies and show that, when demand is log-concave, there exists one or multiple equilibria, and that in any of these, suppliers bid in clusters against other suppliers with similar technologies. / by Victor Martínez-de-Albéniz. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2006. / Includes bibliographical references (p. 171-176). / In this thesis. we introduce and analyze methods of creating theater-level robust mission plans for Effects Based Operations (EBO) of teams of Unmanned Aerial Vehicles (UAVs), and propose methods of effectively presenting the robust plan to an end user. Recent conflicts have demonstrated the utility of UAVs in performing Intelligence, Surveillance, and Reconnaissance (ISR) and strike missions. As UAVs become more common, high-level pre-planning and task delegation will increase in complexity, requiring computer aided planning. Traditional planning methods, based on deterministic input data, generate plans that become infeasible in uncertain environments. Because military operations tend to contain substantial amounts of uncertainty and re-planning at a theater level is costly, plans should be robust to uncertainty yet still accomplish desired effects. We present an effects-based planning framework in which we connect end effects to tasks, enabling planners to value task assignments based on their ability to achieve desired effects. We apply two robust planning techniques to this framework (Bertsimas/Sim and Chance Constrained Programming) and analyze their performance. / (cont.) We demonstrate how robust planning increases the length of time that a plan remains feasible in execution and achieves better overall value by avoiding re-planning costs. We analyze strengths and weaknesses of each model and suggest when their use is appropriate. Finally, we apply Hlinan Machine Collaborative Decision Making (HMICDM) concepts to propose methods to facilitate human interaction with a robust effects-based planner. / by Corban Harrell Bryant. / 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 student submitted PDF version of thesis. / Includes bibliographical references (p. 151-156). / We study the problem of moments and present two diverse applications that apply both the hierarchy of moment relaxation and the moment duality theory. We then propose a moment-based uncertainty model for stochastic optimization problems, which addresses the ambiguity of probability distributions of random parameters with a minimax decision rule. We establish the model tractability and are able to construct explicitly the extremal distributions. The quality of minimax solutions is compared with that of solutions obtained from other approaches such as data-driven and robust optimization approach. Our approach shows that minimax solutions hedge against worst-case distributions and usually provide low cost variability. We also extend the moment-based framework for multi-stage stochastic optimization problems, which yields a tractable model for exogenous random parameters and affine decision rules. Finally, we investigate the application of data-driven approach with risk aversion and robust optimization approach to solve staffing and routing problem for large-scale call centers. Computational results with real data of a call center show that a simple robust optimization approach can be more efficient than the data-driven approach with risk aversion. / by Xuan Vinh Doan. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. / 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 149-153). / In this thesis, we study online optimization problems in routing and allocation applications. Online problems are problems where information is revealed incrementally, and decisions must be made before all information is available. We design and analyze algorithms for a variety of online problems, including traveling salesman problems with rejection options, generalized assignment problems, stochastic matching problems, and resource allocation problems. We use worst case competitive ratios to analyze the performance of proposed algorithms. We begin our study with online traveling salesman problems with rejection options where acceptance/rejection decisions are not required to be explicitly made. We propose an online algorithm in arbitrary metric spaces, and show that it is the best possible. We then consider problems where acceptance/rejection decisions must be made at the time when requests arrive. For dierent metric spaces, we propose dierent online algorithms, some of which are asymptotically optimal. We then consider generalized online assignment problems with budget constraints and resource constraints. We first prove that all online algorithms are arbitrarily bad for general cases. Then, under some assumptions, we propose, analyze, and empirically compare two online algorithms, a greedy algorithm and a primal dual algorithm. We study online stochastic matching problems. Instances with a fixed number of arrivals are studied first. A novel algorithm based on discretization is proposed and analyzed for unweighted problems. The same algorithm is modified to accommodate vertex-weighted cases. Finally, we consider cases where arrivals follow a Poisson Process. Finally, we consider online resource allocation problems. We first consider the problems with free but fixed inventory under certain assumptions, and present near optimal algorithms. We then relax some unrealistic assumptions. Finally, we generalize the technique to problems with flexible inventory with non-decreasing marginal costs. / by Xin Lu. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2005. / Includes bibliographical references (p. 139-146). / We present three problems motivated by order fulfillment in online retailing. First, we focus on one warehouse or fulfillment center. To optimize the storage space and labor, an e-tailer splits the warehouse into two regions with different storage densities. One is for picking customer orders and the other to hold a reserve stock that replenishes the picking area. Consequently, the warehouse is a two-stage serial system. We investigate an inventory system where demand is stochastic by minimizing the total expected inventory- related costs subject to a space constraint. We develop an approximate model for a periodic review, nested ordering policy. Furthermore, we extend the formulation to account for shipping delays and advance order information. We report on tests of the model with data from a major e-tailer. Second, we focus on the entire network of warehouses and customers. When a customer order occurs, the e-tailer assigns the order to one or more of its warehouses and/or drop- shippers, so as to minimize procurement and transportation costs, based on the available current information. However, this assignment is necessarily myopic as it cannot account for any subsequent customer orders or future inventory replenishments. / (cont.) We examine the benefits from periodically re-evaluating these real-time assignments. We construct near- optimal heuristics for the re-assignment for a large set of customer orders by minimizing the total number of shipments. Finally, we present saving opportunities by testing the heuristics on order data from a major e-tailer. Third, we focus on the inventory allocation among warehouses for low-demand SKUs. A large e-tailer strategically stocks inventory for SKUs with low demand. The motivations are to provide a wide range of selections and faster customer fulfillment service. We assume the e-tailer has the technological capability to manage and control the inventory globally: all warehouses act as one to serve the global demand simultaneously. The e-tailer will utilize its entire inventory, regardless of location, to serve demand. Given we stock certain units of system inventory, we allocate inventory to warehouses by minimizing outbound transportation costs. We analyze a few simple cases and present a methodology for more general problems. / by Ping Josephine Xu. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. / Cataloged from PDF version of thesis. / Includes bibliographical references. / After reviewing prevalent approaches to the modeling pandemic influenza transmission, we present a simple distributional model that captures the most significant population attributes that alter the dynamics of the outbreak. We describe how diversities in activity, susceptibility and infectivity can drive or dampen the spread of infection. We expand the model to show infection spread between several linked heterogeneous communities; this multi-community model is based on analytical calculations and Monte Carlo simulations. Focusing on mitigation strategies for a global pandemic influenza, we use our mathematical models to evaluate the implementation and timing of non-pharmaceutical intervention strategies such as travel restrictions, social distancing and improved hygiene. In addition, as we witnessed with the SARS outbreak in 2003, human behavior is likely to change during the course of a pandemic. We propose several different novel approaches to incorporating reactive social distancing and hygiene improvement and its impact on the epidemic curve. Our results indicate that while a flu pandemic could be devastating; there are non-pharmaceutical coping methods that when implemented quickly and correctly can significantly mitigate the severity of a global outbreak. We conclude with a discussion of the implications of the modeling work in the context of university planning for a pandemic. / by Karima Robert Nigmatulina. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 101-102). / This thesis considers the problem of detecting anomalies in performance data for unmanned underwater vehicles(UUVs). UUVs collect a tremendous amount of data, which operators are required to analyze between missions to determine if vehicle systems are functioning properly. Operators are typically under heavy time constraints when performing this data analysis. The goal of this research is to provide operators with a post-mission data analysis tool that automatically identifies anomalous features of performance data. Such anomalies are of interest because they are often the result of an abnormal condition that may prevent the vehicle from performing its programmed mission. In this thesis, we consider existing one-class classification anomaly detection techniques since labeled training data from the anomalous class is not readily available. Specifically, we focus on two anomaly detection techniques: (1) Kernel Density Estimation (KDE) Anomaly Detection and (2) Local Outlier Factor. Results are presented for selected UUV systems and data features, and initial findings provide insight into the effectiveness of these algorithms. Lastly, we explore ways to extend our KDE anomaly detection algorithm for various tasks, such as finding anomalies in discrete data and identifying anomalous trends in time-series data. / by William Ray Harris. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 133-138). / We propose a novel robust optimization technique, which is applicable to nonconvex and simulation-based problems. Robust optimization finds decisions with the best worst-case performance under uncertainty. If constraints are present, decisions should also be feasible under perturbations. In the real-world, many problems are nonconvex and involve computer-based simulations. In these applications, the relationship between decision and outcome is not defined through algebraic functions. Instead, that relationship is embedded within complex numerical models. Since current robust optimization methods are limited to explicitly given convex problems, they cannot be applied to many practical problems. Our proposed method, however, operates on arbitrary objective functions. Thus, it is generic and applicable to most real-world problems. It iteratively moves along descent directions for the robust problem, and terminates at a robust local minimum. Because the concepts of descent directions and local minima form the building blocks of powerful optimization techniques, our proposed framework shares the same potential, but for the richer, and more realistic, robust problem. / (cont.) To admit additional considerations including parameter uncertainties and nonconvex constraints, we generalized the basic robust local search. In each case, only minor modifications are required - a testimony to the generic nature of the method, and its potential to be a component of future robust optimization techniques. We demonstrated the practicability of the robust local search technique in two realworld applications: nanophotonic design and Intensity Modulated Radiation Therapy (IMRT) for cancer treatment. In both cases, the numerical models are verified by actual experiments. The method significantly improved the robustness for both designs, showcasing the relevance of robust optimization to real-world problems. / by Kwong Meng Teo. / Ph.D.

Thesis: Ph. D., 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 219-225). / We present several contributions at the interface of first-order methods for convex optimization and problems in statistical machine learning. In the first part of this thesis, we present new results for the Frank-Wolfe method, with a particular focus on: (i) novel computational guarantees that apply for any step-size sequence, (ii) a novel adjustment to the basic algorithm to better account for warm-start information, and (iii) extensions of the computational guarantees that hold in the presence of approximate subproblem and/or gradient computations. In the second part of the thesis, we present a unifying framework for interpreting "greedy" first-order methods -- namely Frank-Wolfe and greedy coordinate descent -- as instantiations of the dual averaging method of Nesterov, and we discuss the implications thereof. In the third part of the thesis, we present an extension of the Frank-Wolfe method that is designed to induce near-optimal low-rank solutions for nuclear norm regularized matrix completion and, for more general problems, induces near-optimal "well-structured" solutions. We establish computational guarantees that trade off efficiency in computing near-optimal solutions with upper bounds on the rank of iterates. We then present extensive computational results that show significant computational advantages over existing related approaches, in terms of delivering low rank and low run-time to compute a target optimality gap. In the fourth part of the thesis, we analyze boosting algorithms in linear regression from the perspective modern first-order methods in convex optimization. We show that classic boosting algorithms in linear regression can be viewed as subgradient descent to minimize the maximum absolute correlation between features and residuals. We also propose a slightly modified boosting algorithm that yields an algorithm for the Lasso, and that computes the Lasso path. Our perspective leads to first-ever comprehensive computational guarantees for all of these boosting algorithms, which provide a precise theoretical description of the amount of data-fidelity and regularization imparted by running a boosting algorithm, for any dataset. In the fifth and final part of the thesis, we present several related results in the contexts of boosting algorithms for logistic regression and the AdaBoost algorithm. / by Paul Grigas. / Ph. D.