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 185-193). / This thesis proposes a unified framework to capture the temporal and longitudinal variation across multiple instances of sequential data. Examples of such data include sales of a product over a period of time across several retail locations; trajectories of scores across cricket games; and annual tobacco consumption across the United States over a period of decades. A key component of our work is the latent variable model (LVM) which views the sequential data as a matrix where the rows correspond to multiple sequences while the columns represent the sequential aspect. The goal is to utilize information in the data within the sequence and across different sequences to address two inferential questions: (a) imputation or "filling missing values" and "de-noising" observed values, and (b) forecasting or predicting "future" values, for a given sequence of data. Using this framework, we build upon the recent developments in "matrix estimation" to address the inferential goals in three different applications. First, a robust variant of the popular "synthetic control" method used in observational studies to draw causal statistical inferences. Second, a score trajectory forecasting algorithm for the game of cricket using historical data. This leads to an unbiased target resetting algorithm for shortened cricket games which is an improvement upon the biased incumbent approach (Duckworth-Lewis-Stern). Third, an algorithm which leads to a consistent estimator for the time- and location-varying demand of products using censored observations in the context of retail. As a final contribution, the algorithms presented are implemented and packaged as a scalable open-source library for the imputation and forecasting of sequential data with applications beyond those presented in this work. / by Muhammad Jehangir Amjad. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2000. / Includes bibliographical references (leaves 45-46). / In this thesis, we considered the costs and benefits of implementing Positive Passenger Bag Match (PPBM) - an anti-terrorist measure to keep bombs out of checked luggage - on US domestic passenger flights. We constructed a stochastic model for comparing the cost-effectiveness of three alternative approaches to PPBM: no PPBML implementation; a PPBM implementation that is applied to 5% of passengers; and a full (100%) implementation of PPBM. We made ranges of estimates concerning the level of terrorist risk, the costs of PPBM operation, the consequences of successful terrorist bombings, and the anti-terrorist effectiveness of both the partial and full PPBM implementations. Calculations showed that there were circumstances under which each policy was the most cost-effective of the three. Of the three options, not implementing PPBM at all was the most cost-effective approach for the largest percentage of the scenarios considered. We found that 5% PPBM captured the next largest portion of the scenarios, and was generally the optimal strategy when annual PPBMI operation costs were low, when 5% PPBM anti-terrorist effectiveness was high, and when the consequences of successful bombings were severe. We found 100%(. PPBM to be the optimal strategy for most scenarios which involved highly costly terrorist bombings, a high level of terrorist risk, and a 100% PPBM policy that provided much added security over 5% PPBM. / by Jonathan E.W. Cohen. / S.M.

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 139-141). / In the era of Big Data, online retailers have access to a large amount of data about their customers. This data can include demographic information, shopping carts, transactions and browsing history. In the last decade, online retailers have been leveraging this data to build a personalized shopping experience for their customers with targeted promotions, discounts and personalized item recommendations. More recently, some online retailers started having access to social media data: more accurate demographic and interests information, friends, social interactions, posts and comments on social networks, etc. Social media data allows to understand, not only what customers buy, but also what they like, what they recommend to their friends, and more importantly what is the impact of these recommendations. This work is done in collaboration with an online marketplace in Canada with an embedded social network on its website. We study the impact of incorporating social media data on demand forecasting and we design an optimized and transparent social loyalty program to reward socially active customers and maximize the retailer's revenue. The first chapter of this thesis builds a demand estimation framework in a setting of heterogeneous customers. We want to cluster the customers into categories according to their social characteristics and jointly estimate their future consumption using a distinct logistic demand function for each category. We show that the problem of joint clustering and logistic regression can be formulated as a mixed-integer concave optimization problem that can be solved efficiently even for a large number of customers. We apply our algorithm using the actual online marketplace data and study the impact of clustering and incorporating social features on the performance of the demand forecasting model. In the second chapter of this thesis, we focus on price sensitivity estimation in the context of missing data. We want to incorporate a price component in the demand model built in the previous chapter using recorded transactions. We face the problem of missing data: for the customers who make a purchase we have access to the price they paid, but for customers who visited the website and decided not to make a purchase, we do not observe the price they were offered. The EM (Expectation Maximization) algorithm is a classical approach for estimation with missing data. We propose a non-parametric alternative to the EM algorithm, called NPM (Non-Parametric Maximization). We then show analytically the consistency of our algorithm in two particular settings. With extensive simulations, we show that NPM is a robust and flexible algorithm that converges significantly faster than EM. In the last chapter, we introduce and study a model to incorporate social influence among customers into the demand functions estimated in the previous chapters. We then use this demand model to formulate the retailer' revenue maximization problem. We provide a solution approach using dynamic programming that can deal with general demand functions. We then focus on two special structures of social influence: the nested and VIP models and compare their performance in terms of optimal prices and profit. Finally, we develop qualitative insights on the behavior of optimal price strategies under linear demand and illustrate computationally that these insights still hold for several popular non-linear demand functions. / by Ludovica Rizzo. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2002. / Includes bibliographical references (p. 59-60). / We develop two classes of optimization models in order to maximize revenue in a restaurant, while controlling average waiting time as well as perceived fairness, that may violate the first-come-first-serve (FCFS) rule. In the first class of models, we use integer programming, stochastic programming and approximate dynamic programming methods to decide dynamically when, if at all, to seat an incoming party during the day of operation of a restaurant that does not accept reservations. In a computational study with simulated data, we show that optimization based methods enhance revenle relative to the industry practice of FCFS by 0.11% to 2.22% for low load factors, by 0.16% to 2.96% for medium load factors, and by 7.65% to 13.13% for high load factors, without increasing and occasionally decreasing waiting times compared to FCFS. The second class of models addresses reservations. We propose a two step procedure: use a stochastic gradient algorithm to decide a priori how many reservations to accept for a future time and then use approximate dynamic programming methods to decide dynamically when, if at all, to seat an incoming party during the day of operation. In a computational study involving real data from an Atlanta restaurant, the reservation model improves revenue relative to FCFS by 3.5% for low load factors and 7.3% for high load factors. / by Romy Shioda. / S.M.

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 193-201). / The global airline industry is a multi-stakeholder stochastic system whose performance is the outcome of complex interactions between its multiple decisions-makers under a high degree of uncertainty. Inadequate understanding of uncertainty and stakeholder preferences leads to adverse effects including airline losses, delays and disruptions. This thesis studies a set of topics in airline scheduling and air traffic control to mitigate some of these issues. The first part of the thesis focuses on building aircraft schedules that are robust against delays. We develop a robust optimization approach for building aircraft routes. The goal is to mitigate propagated delays, which are defined as the delays caused by the late arrival of aircraft from earlier flights and are the top cause of flight delays in the United States air transportation system. The key feature of our model is that it allows us to handle correlation in flight delays explicitly that existing approaches cannot handle efficiently. We propose an efficient decomposition algorithm to solve the robust model and present the results of numerical experiments, based on data from a major U.S. airline, to demonstrate its effectiveness compared to existing approaches. The second part of the thesis focuses on improving the planning of air traffic flow management (ATFM) programs by incorporating airline preferences into the decision-making process. We develop a voting mechanism to gather airline preferences of candidate ATFM designs. A unique feature of this mechanism is that the candidates are drawn from a domain with infinite cardinality described by polyhedral sets. We conduct a detailed case study based on actual schedule data at San Francisco International Airport to assess its benefits in planning of ground delay programs. Finally, we study an integrated airline network planning model which incorporates passenger choice behavior. We model passenger demand using a multinomial logit choice model and integrate it into a fleet assignment and schedule design model. To tackle the formidable computational challenge associated with solving this model, we develop a reformulation, decomposition and approximation scheme. Using data from a major U.S. airline, we prove that the proposed approach brings significant profit improvements over existing methods. / by Chiwei Yan. / 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 163-166). / In this thesis, we study data-driven decision making in operation management contexts, with a focus on both theoretical and practical aspects. The first part of the thesis analyzes the well-known newsvendor model but under the assumption that, even though demand is stochastic, its probability distribution is not part of the input. Instead, the only information available is a set of independent samples drawn from the demand distribution. We analyze the well-known sample average approximation (SAA) approach, and obtain new tight analytical bounds on the accuracy of the SAA solution. Unlike previous work, these bounds match the empirical performance of SAA observed in extensive computational experiments. Our analysis reveals that a distribution's weighted mean spread (WMS) impacts SAA accuracy. Furthermore, we are able to derive distribution parametric free bound on SAA accuracy for log-concave distributions through an innovative optimization-based analysis which minimizes WMS over the distribution family. In the second part of the thesis, we use spread information to introduce new families of demand distributions under the minimax regret framework. We propose order policies that require only a distribution's mean and spread information. These policies have several attractive properties. First, they take the form of simple closed-form expressions. Second, we can quantify an upper bound on the resulting regret. Third, under an environment of high profit margins, they are provably near-optimal under mild technical assumptions on the failure rate of the demand distribution. And finally, the information that they require is easy to estimate with data. We show in extensive numerical simulations that when profit margins are high, even if the information in our policy is estimated from (sometimes few) samples, they often manage to capture at least 99% of the optimal expected profit. The third part of the thesis describes both applied and analytical work in collaboration with a large multi-state gas utility. We address a major operational resource allocation problem in which some of the jobs are scheduled and known in advance, and some are unpredictable and have to be addressed as they appear. We employ a novel decomposition approach that solves the problem in two phases. The first is a job scheduling phase, where regular jobs are scheduled over a time horizon. The second is a crew assignment phase, which assigns jobs to maintenance crews under a stochastic number of future emergencies. We propose heuristics for both phases using linear programming relaxation and list scheduling. Using our models, we develop a decision support tool for the utility which is currently being piloted in one of the company's sites. Based on the utility's data, we project that the tool will result in 55% reduction in overtime hours. / by Joline Ann Villaranda Uichanco. / 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 243-250). / In this thesis, I study how data-driven optimization can be used to improve school choice. In a typical school choice system, each student receives a set of school options, called the student's menu. Based on his/her menu, each student submits a preference ranking of schools in the menu. Based on the submitted preferences, a centralized algorithm determines the assignment. In Boston, New York City, Chicago, Denver, New Orleans,Washington DC, among other cities, the assignment algorithm is the student-proposing deferred acceptance (DA) algorithm, which can also incorporate a priority for each student at each school. These priorities may contain a deterministic as well as a random component. An advantage of this algorithm is incentive-compatibility, meaning that no student has incentives to misreport his/her preferences. The first research question of this thesis is how to optimize the menus and priorities so that students have equitable chances to go to the schools they want, while the city's school busing costs are controlled. The second question is how the assignment algorithm can be modified to keep the same assignment probability of every student to every school, while improving neighbors' chances of going to the same school. To answer these questions, I build a multinomial logit (MNL) model to predict how students will rank schools under new menus, and validate the predictive accuracy of this model out of sample. I also propose a simple plan for menus and priorities, called the Home-Based plan, and compare with other proposals using the MNL model. (As a result of this analysis, the Home-Based plan was adopted by Boston in 2013.) I then show how one can further optimize the menus and priorities under the MNL model, by developing a new theoretical connection between stable matching and assortment planning, as well as methodologies on solving a new type of assortment planning problem, in which the objective is social welfare rather than revenue. Finally, I show how to further optimize the correlations between students' assignments to improve neighbors' chances of going to the same school. / by Peng Shi. / Ph. D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 95-97). / End-stage liver disease is one of the leading causes of death in the United States, and the only viable treatment is liver transplantation. Since the quality of a donor liver decreases with transportation time, United States organ policy prioritizes transplants within geographic regions. However, the boundaries of these regions were defined mostly by informal relationships between transplant centers many decades ago, which has created local imbalances in supply and demand. As a result, candidates on the waiting list for donor livers face drastically different odds of receiving a transplant. Policy makers have noticed this geographic inequity and are considering proposals for alternative liver allocation approaches. This thesis uses mathematical optimization to redesign liver allocation regions by modeling and including several key elements of the allocation process directly in the optimization formulation. Specifically, we use a fluid approximation to model the dynamics of the wait-list progression and liver allocation. The model is fit using historical data of wait-list candidates and donors. Then, we propose two optimization formulations to reduce geographic inequality. The first directly minimizes the variation in median level of illness at the time of transplant across geographical areas, which is a key metric used by policy makers in addressing geographic inequality. The second approach minimizes the liver transport distance, subject to a certain allowable level of geographic variation. We discuss how these models can flexibly incorporate additional policy constraints to create more realistic models to reduce geographic variation. The region configurations are evaluated on key metrics relating to fairness and system efficiency using a standardized, validated, simulation approach widely accepted by policymakers. Finally, we propose a region design that significantly reduces geographic inequality without any substantial impact on the system's efficiency. / by Timothy Scully. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 201-207). / Modern probability theory, whose foundation is based on the axioms set forth by Kolmogorov, is currently the major tool for performance analysis in stochastic systems. While it offers insights in understanding such systems, probability theory, in contrast to optimization, has not been developed with computational tractability as an objective when the dimension increases. Correspondingly, some of its major areas of application remain unsolved when the underlying systems become multidimensional: Queueing networks, auction design in multi-item, multi-bidder auctions, network information theory, pricing multi-dimensional financial contracts, among others. We propose a new approach to analyze stochastic systems based on robust optimization. The key idea is to replace the Kolmogorov axioms and the concept of random variables as primitives of probability theory, with uncertainty sets that are derived from some of the asymptotic implications of probability theory like the central limit theorem. In addition, we observe that several desired system properties such as incentive compatibility and individual rationality in auction design and correct decoding in information theory are naturally expressed in the language of robust optimization. In this way, the performance analysis questions become highly structured optimization problems (linear, semidefinite, mixed integer) for which there exist efficient, practical algorithms that are capable of solving problems in high dimensions. We demonstrate that the proposed approach achieves computationally tractable methods for (a) analyzing queueing networks (Chapter 2) (b) designing multi-item, multi-bidder auctions with budget constraints, (Chapter 3) (c) characterizing the capacity region and designing optimal coding and decoding methods in multi-sender, multi-receiver communication channels (Chapter 4). / by Chaithanya Bandi. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2003. / Includes bibliographical references (p. 160-168). / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / We propose new models and optimization methods for airline revenue management and pricing. In the first part of this thesis, we study the dynamic inventory control problem for a single flight under imperfect market segmentation, when customers book the lowest available class whose restrictions they can satisfy and whose fare they are willing to pay. We derive theoretical properties of the value functions and optimal policy for a generic single-resource revenue management problem, of which this problem is a special case. Numerical examples show that adjusting the booking policy for imperfections of the market segmentation leads to significant revenue gains. In the second part, we study the impact of dynamic capacity management on airline seat inventory control. Through better matching the supply and demand for seats the airline is able to carry more passengers, and the revenue management policy should be adjusted accordingly. We propose a derivative of the widely used EMSRb booking limit calculation method that takes into account the effect of future capacity changes, which can lead to significant revenue gains. In the third part, we propose a simulation-based optimization approach for seat inventory control in a network environment. Starting with any nested booking-limit policy, we combine a stochastic gradient algorithm and approximate dynamic programming ideas to improve the initial booking limits. Numerical experiments suggest that the proposed algorithm can lead to practically significant revenue enhancements. In the fourth part, -we study a joint pricing and resource allocation probleml in a network with applications to production planning and airline revenue management. We show that the objective function reduces to a convex optimization problem for certain types of demand distributions, which is tractable for large instances. / (cont.) We propose several approaches for dynamic picing and resource allocation. Numerical experiments suggest that coordination of pricing and resource allocation policies in a network while taking into account the uncertainty of demand can lead to significant revenue gains. Finally, in our conclusions we propose an integrated approach to airline revenue management that combines all four aspects that we studied here, and suggest directions for future research. / by Sanne Vincent de Boer. / Ph.D.