Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2005. / Includes bibliographical references (p. 144-146). / Autonomous vehicles often operate in environments with imperfect information. This thesis addresses the case of a system of autonomous vehicles and sensors attempting to intercept a moving object of interest that arrives stochastically and moves stochastically after arrival. A sensor array is placed in the area of expected arrivals. As the object of interest moves across the sensor system, the system initially receives perfect information of the object's movements. After the object of interest leaves the sensor system, the algorithm uses statistical estimation techniques to develop confidence intervals about points of expected interception. The algorithm assigns the optimal, autonomous chase vehicle from a set of pre-positioned autonomous vehicles, develops movement commands for the assigned vehicle, and considers reassignment of chase vehicles as appropriate given the stochastic movements of the object of interest. Dynamic programming is employed to optimize system parameters, and the thesis considers a reformulation of the problem that uses dynamic programming as a structural model for the entire algorithm. / by Randal E. Hickman. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 111-125). / The Vehicle Routing Problem with Time Windows (VRPTW) has been widely studied in the Operations Research (OR) literature given its increasingly widespread applications, ranging from school bus scheduling to packages delivery. In the last decades, and in large part due to the surge in e-commerce and shortened promised lead times, the scale of the highly constrained VRPTW instances encountered in real-world applications has significantly increased. Simultaneously, various Machine Learning (ML) methods have been developed to tackle combinatorial problems and to leverage complex data structure, but little research has been done on applying these techniques to the VRPTW. In light of this research gap, our thesis develops a process to solve large-scale VRPTW without classical OR routing by proposing a two-stage algorithm. In the first stage, we design a clustering algorithm leveraging Optimal Classification Trees (OCT), which aims at dividing customers into smaller subsets. In the second stage, we present an actor-critic Reinforcement Learning (RL) approach to solve the VRPTW on these smaller customers clusters. Subsequently, we explore the interactions between ML and OR and develop a framework to overcome the difficulties linked to the differences between the train and test sets, as well as the adversity created by the OR algorithm. We also study the generalization limitations of RL methods. Results show that the clustering approach is competitive with regards to a k-means-based clustering, yielding improvements up to 5% in terms of number of vehicles, and that a RL approach can successfully solve medium-size VRPTW instances, providing optimality results similar to state-of-the-art industrial solvers. / by Julie Poullet. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 83-89). / We first study the sample complexity of one-layer neural networks, namely the number of examples that are needed in the training set for such models to be able to learn meaningful information out-of-sample. We empirically derive quantitative relationships between the sample complexity and the parameters of the network, such as its input dimension and its width. Then, we introduce polynomial regression as a proxy for neural networks through a polynomial approximation of their activation function. This method operates in the lifted space of tensor products of input variables, and is trained by simply optimizing a standard least squares objective in this space. We study the scalability of polynomial regression, and are able to design a bagging-type algorithm to successfully train it. The method achieves competitive accuracy on simple image datasets while being more simple. We also demonstrate that it is more robust and more interpretable that existing approaches. It also offers more convergence guarantees during training. Finally, we empirically show that the widely-used Stochastic Gradient Descent algorithm makes the weights of the trained neural networks converge to the optimal polynomial regression weights. / by Matt V. Emschwiller. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from the official PDF of thesis. / Includes bibliographical references (pages 245-260). / In this thesis, we propose novel formulation optimization methods for four matrix factorization problems in depth: sparse principal component analysis, compressed sensing, discrete component analysis, and latent Dirichlet allocation. For each new formulations, we develop efficient solution algorithms using discrete and robust optimization, and demonstrate tractability and effectiveness in computational experiments. In Chapter 1, we develop a framework for matrix factorization problems and provide a technical introduction to topic modeling with examples. Chapter 2, Certifiably optimal sparse principal component analysis, addresses the sparse principal component analysis (SPCA) problem. We propose a tailored branch-and- bound algorithm, Optimal-SPCA, that enables us to solve SPCA to certifiable optimality. / We apply our methods to real data sets to demonstrate that our approach scales well and provides superior solutions compared to existing methods, explaining a higher proportion of variance and permitting more control over the desired sparsity. Chapter 3, optimal compressed sensing in submodular settings, presents a novel algorithm for compressed sensing that guarantees optimality under submodularity conditions rather than restricted isometry property (RIP) conditions. The algorithm defines submodularity properties of the loss function, derives lower bounds, and generates these lower bounds as constraints for use in a cutting planes algorithm. The chapter also develops a local search heuristic based on this exact algorithm. Chapter 4, Robust topic modeling, develops a new form of topic modeling inspired by robust optimization and by discrete component analysis. / The new approach builds uncertainty sets using one-sided constraints and two hypothesis tests, uses alternating optimization and projected gradient methods, including Adam and mirror descent, to find good local optima. In computational experiments, we demonstrate that these models are better able to avoid over-fitting than LDA and PLSA, and result in more accurate reconstruction of the underlying topic matrices. In Chapter 5, we develop modifications to latent Dirichlet allocation to account for differences in the distribution of topics by authors. The chapter adds author-specific topic priors to the generative process and allows for co-authorship, providing the model with increased degrees of freedom and enabling it to model an enhanced set of problems. The code for the algorithms developed in each chapter in the Julia language is available freely on GitHub at https://github.com/lauren897 / by Lauren Elizabeth Berk. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from the official PDF of thesis. / Includes bibliographical references (pages 241-249). / This thesis revisits a fundamental class of dynamic optimization problems introduced by Dantzig (1955). These decision problems remain widely studied in many applications domains (e.g., inventory management, finance, energy planning) but require access to probability distributions that are rarely known in practice. First, we propose a new data-driven approach for addressing multi-stage stochastic linear optimization problems with unknown probability distributions. The approach consists of solving a robust optimization problem that is constructed from sample paths of the underlying stochastic process. As more sample paths are obtained, we prove that the optimal cost of the robust problem converges to that of the underlying stochastic problem. To the best of our knowledge, this is the first data-driven approach for multi-stage stochastic linear optimization problems which is asymptotically optimal when uncertainty is arbitrarily correlated across time. / Next, we develop approximation algorithms for the proposed data-driven approach by extending techniques from the field of robust optimization. In particular, we present a simple approximation algorithm, based on overlapping linear decision rules, which can be reformulated as a tractable linear optimization problem with size that scales linearly in the number of data points. For two-stage problems, we show the approximation algorithm is also asymptotically optimal, meaning that the optimal cost of the approximation algorithm converges to that of the underlying stochastic problem as the number of data points tends to infinity. Finally, we extend the proposed data-driven approach to address multi-stage stochastic linear optimization problems with side information. The approach combines predictive machine learning methods (such as K-nearest neighbors, kernel regression, and random forests) with the proposed robust optimization framework. / We prove that this machine learning-based approach is asymptotically optimal, and demonstrate the value of the proposed methodology in numerical experiments in the context of inventory management, scheduling, and finance. / by Bradley Eli Sturt. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 53-54). / It is undeniable that recent world events and globalization have transformed online learning into one of the main channels for education. Online learning has become a necessity, not a luxury. Universities, schools, and pre-schools have transformed into the online learning space holding classes of hundreds of students concurrently. However, online learning has yet to reach its full potential. Although educators understand the benefits and effectiveness of online learning platforms, the lack of engagement and evaluation are clear. None the less, these challenges can be solved through machine learning. In this thesis, we present novel, interpretable prescriptive methods to the online learning setting. We apply these techniques to adaptive learning and test them in real online course settings. We show that using an interpretable, optimal tree-based approach improves both the engagement and the learning rates of the learners. We present PLOpt, a full-stack web app that leverages machine learning models and learner, content knowledge to create assignments that best suit each individual learner. We describe the models, how they were tested, and their evaluation. We demonstrate that by using PLOpt, learners achieved higher engagement and proficiency levels. In addition, we show how PLOpt created assignments that matched the correct difficulty level of the learners so that the learner could remain engaged with challenging questions, yet not frustrated by questions too difficult to answer. Altogether, this work demonstrates that applying interpretable machine learning to online learning builds personalized learning platforms and solves the challenges raised in today's online learning world. / by Galit Lukin. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 32-34). / An equitable and flexible mechanism for assigning students to schools is a major concern for many school districts. The school a student attends dramatically impacts the quality of education, access to resources, family and neighborhood cohesion, and transportation costs. Facing this intricate optimization problem, school districts often utilize to stable-matching techniques which only produce stable matchings that do not incorporate these different objectives; this can be expensive and inequitable. We present a new optimization model for the Stable Matching (SM) school choice problem which relies on an algorithm we call Price-Costs-Flexibility-and- Fairness (PCF2). Our model leverages techniques to balance competing objectives using mixed-integer optimization methods. We explore the trade-offs between stability, costs, and preferences and show that, surprisingly, there are stable solutions that decrease transportation costs by 8-17% over the Gale-Shapley solution. / by Justin W. Graham. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from the official PDF of thesis. / Includes bibliographical references (pages 131-142). / With data becoming increasingly available in recent years, black-box algorithms like boosting methods or neural networks play more important roles in the real world. However, interpretability is a severe need for several areas of applications, like health care or business. Doctors or managers often need to understand how models make predictions, in order to make their final decisions. In this thesis, we improve and propose some interpretable machine learning methods by using modern optimization. We also use two examples to illustrate how interpretable machine learning methods help to solve problems in health care. The first part of this thesis is about interpretable machine learning methods using modern optimization. In Chapter 2, we illustrate how to use robust optimization to improve the performance of SVM, Logistic Regression, and Classification Trees for imbalanced datasets. In Chapter 3, we discuss how to find optimal clusters for prediction. we use real-world datasets to illustrate this is a fast and scalable method with high accuracy. In Chapter 4, we deal with optimal regression trees with polynomial function in leaf nodes and demonstrate this method improves the out-of-sample performance. The second part of this thesis is about how interpretable machine learning methods improve the current health care system. In Chapter 5, we illustrate how we use Optimal Trees to predict the risk mortality for candidates awaiting liver transplantation. Then we develop a transplantation policy called Optimized Prediction of Mortality (OPOM), which reduces mortality significantly in simulation analysis and also improves fairness. In Chapter 6, we propose a new method based on Optimal Trees which perform better than original rules in identifying children at very low risk of clinically important traumatic brain injury (ciTBI). If this method is implemented in the electronic health record, the new rules may reduce unnecessary computed tomographies (CT). / by Yuchen Wang. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from the official PDF of thesis. / Includes bibliographical references (pages 145-155). / Urban transit and city logistics have undergone major changes in recent years, including increased peak congestion, shrinking mass transit ridership, and the introduction of ride-sharing and micro-mobility platforms. At the same time, widespread data collection offers transit agencies insight into their riders in unprecedented detail. In this setting, data has the potential to inform decision-making and make meaningful impact on problems of great public interest. This thesis concerns data-driven decision-making for public transit systems, and spans topics from demand estimation to the design and operation of fixed-route systems and paratransit. The first chapter is concerned with origin-destination demand estimation for public transit. Our aim is to estimate demand using aggregated station entrance and exit counts, which can be modeled as the problem of recovering a matrix from its row and column sums. / We recover the demand by assuming that it follows intuitive physical properties such as smoothness and symmetry, and we contrast this approach both analytically and empirically with the maximum entropy method on real-world data. The next two chapters then use this demand data to inform strategic transit planning problems such as network design, frequency-setting, and pricing. These problems are challenging alone and made even more difficult by the complexity of commuter behavior. Our models address operator decision-making in the face of commuter preferences, and our approaches are based on column generation and first-order methods in order to model complex dynamics while scaling to realistic city settings. Finally, we explore tactical decision-making for paratransit. Paratransit is a government-mandated service that provides shared transportation for those who cannot use fixed routes due to disability. / Although paratransit is an essential safety net, it is also expensive and requires large government subsidies. These financial difficulties motivate us to develop large-scale optimization algorithms for vehicle routing in paratransit. We provide an optimization-based heuristic approach to servicing paratransit requests subject to labor constraints; this approach shows strong performance while also being tractable for several thousand daily requests.. / by Julia Yan. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, May, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 89-92). / This thesis presents a method for information fusion for an unmanned underwater vehicle (UUV).We consider a system that fuses contact reports from automated information system (AIS) data and active and passive sonar sensors. A linear assignment problem with learned assignment costs is solved to fuse sonar and AIS data. Since the sensors operate effectively at different depths, there is a time lag between AIS and sonar data collection. A recurrent neural network predicts a contact's future occupancy grid from a segment of its AIS track. Assignment costs are formed by comparing a sonar position with the predicted occupancy grids of relevant vessels. The assignment problem is solved to determine which sonar reports to match with existing AIS contacts. / by Katherine Lee Burnham. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center