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.

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. 105-111). / This thesis investigates the application of robust optimization in the performance analysis of queueing and inventory systems. In the first part of the thesis, we propose a new approach for performance analysis of queueing systems based on robust optimization. We first derive explicit upper bounds on performance for tandem single class, multiclass single server, and single class multi-server queueing systems by solving appropriate robust optimization problems. We then show that these bounds derived by solving deterministic optimization problems translate to upper bounds on the expected steady-state performance for a variety of widely used performance measures such as waiting times and queue lengths. Additionally, these explicit bounds agree qualitatively with known results. In the second part of the thesis, we propose methods to compute (s,S) policies in supply chain networks using robust and stochastic optimization and compare their performance. Our algorithms handle general uncertainty sets, arbitrary network topologies, and flexible cost functions including the presence of fixed costs. The algorithms exhibit empirically practical running times. We contrast the performance of robust and stochastic (s,S) policies in a numerical study, and we find that the robust policy is comparable to the average performance of the stochastic policy, but has a considerably lower standard deviation across a variety of networks and realized demand distributions. Additionally, we identify regimes when the robust policy exhibits particular strengths even in average performance and tail behavior as compared with the stochastic policy. / by Alexander Anatolyevich Rikun. / 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. 107-110). / In the first part of this thesis we present a new, geometric interpretation of the jump number problem on 2-dimensional 2-colorable (2D2C) partial order. We show that the jump number of a 2D2C poset is equivalent to the maximum cardinality of an independent set in a properly defined collection of rectangles in the plane. We then model the geometric problem as a linear program. Even though the underlying polytope may not be integral, we show that one can always find an integral optimal solution. Inspired by this result and by previous work of A. Frank, T. Jordan and L. Vegh [13, 14, 15] on set-pairs, we derive an efficient combinatorial algorithm to find the maximum independent set and its dual, the minimum hitting set, in polynomial time. The combinatorial algorithm solves the jump number problem on convex posets (a subclass of 2D2C posets) significantly faster than current methods. If n is the number of nodes in the partial order, our algorithm runs in 0((n log n)2.5) time, while previous algorithms ran in at least 0(n9 ) time. In the second part, we present a novel connection between certain sequencing problems that involve the coordination of activities and the problem of factorizing integer numbers. We use this connection to derive hardness results for three different problems: -- The Joint Replenishment Problem with General Integer Policies. -- The Joint Replenishment Problem with Correction Factor. -- The Problem of Optimal Clustering of Frequency-Constrained Maintenance Jobs. Our hardness results do not follow from a standard type of reduction (e.g., we do not prove NP-hardness), and imply that no polynomial-time algorithm exists for the problems above, unless Integer Factorization is solvable in polynomial time.. / by Claudio Telha Cornejo. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / 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-102). / Health care expenditures in the United States have been increasing at unsustainable rates for more than thirty years with no signs of abating. Decisions to accept or reject deceased-donor kidneys offered to patients on the kidney transplantation wait-list currently rely on physician experience and intuition. Scoring rules to determine which end-stage liver disease patients are in most dire need of immediate transplantation have been haphazardly designed and reactively modified in an attempt to decrease waitlist mortality and increase fairness for cancer patients. For each of the above problem settings, we propose a framework that takes real-world data as input and draws upon modern data analytics methods ranging from mixed integer linear optimization to predictive machine learning to yield actionable insights that can add a significant edge over current practice. We describe an approach that, given insurance claims data, leads conservatively to a 10% reduction in health care costs in a study involving a large private US employer. Using historical data for patients on the kidney waitlist and organ match runs, we build a model that achieves an out-of-sample AUC of 0.87 when predicting whether or not a patient will receive a kidney of a particular quality within three, six, or twelve months. Given historical data for patients on the liver waitlist, we create a unified model that is capable of averting an additional 25% of adverse events in simulation compared to current practice without disadvantaging cancer patients. / by Jerry Lai Kung. / Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / 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 111-118). / In this thesis, I address three challenging machine-learning problems. The first problem that we address is the imbalanced data problem. We propose two algorithms to handle highly imbalanced classification problems. The first algorithm uses mixed integer programming to optimize a weighted balance between positive and negative class accuracies. The second method uses an approximation in order to assist with scalability. Specifically, it follows a characterize-then-discriminate approach. The positive class is first characterized by boxes, and then each box boundary becomes a separate discriminative classifier. This method is computationally advantageous because it can be easily parallelized, and considers only the relevant regions of the feature space. The second problem is a density estimation problem for categorical data sets. We present tree- and list- structured density estimation methods for binary/categorical data. We present three generative models, where the first one allows the user to specify the number of desired leaves in the tree within a Bayesian prior. The second model allows the user to specify the desired number of branches within the prior. The third model returns lists (rather than trees) and allows the user to specify the desired number of rules and the length of rules within the prior. Finally, we present a new machine learning approach to estimate personalized treatment effects in the classical potential outcomes framework with binary outcomes. Strictly, both treatment and control outcomes must be measured for each unit in order to perform supervised learning. However, in practice, only one outcome can be observed per unit. To overcome the problem that both treatment and control outcomes for the same unit are required for supervised learning, we propose surrogate loss functions that incorporate both treatment and control data. The new surrogates yield tighter bounds than the sum of the losses for the treatment and control groups. A specific choice of loss function, namely a type of hinge loss, yields a minimax support vector machine formulation. The resulting optimization problem requires the solution to only a single convex optimization problem, incorporating both treatment and control units, and it enables the kernel trick to be used to handle nonlinear (also non-parametric) estimation. / by Siong Thye Goh. / Ph. D.