This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2019 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 85-90). / The goal of this thesis was to develop a data type agnostic classification algorithm best suited for problems where there are a large number of similar labels (e.g., classifying a port versus a shipyard). The most common approach to this issue is to simply ignore it, and attempt to fit a classifier against all targets at once (a "flat" classifier). The problem with this technique is that it tends to do poorly due to label similarity. Conversely, there are other existing approaches, known as hierarchical classifiers (HCs), which propose clustering heuristics to group the labels. However, the most common HCs require that a "flat" model be trained a-priori before the label hierarchy can be learned. The primary issue with this approach is that if the initial estimator performs poorly then the resulting HC will have a similar rate of error. / To solve these challenges, we propose three new approaches which learn the label hierarchy without training a model beforehand and one which generalizes the standard HC. The first technique employs a k-means clustering heuristic which groups classes into a specified number of partitions. The second method takes the previously developed heuristic and formulates it as a mixed integer program (MIP). Employing a MIP allows the user to have greater control over the resulting label hierarchy by imposing meaningful constraints. The third approach learns meta-classes by using community detection algorithms on graphs which simplifies the hyper-parameter space when training an HC. Finally, the standard HC methodology is generalized by relaxing the requirement that the original model must be a "flat" classifier; instead, one can provide any of the HC approaches detailed previously as the initializer. / By giving the model a better starting point, the final estimator has a greater chance of yielding a lower error rate. To evaluate the performance of our methods, we tested them on a variety of data sets which contain a large number of similar labels. We observed the k-means clustering heuristic or community detection algorithm gave statistically significant improvements in out-of-sample performance against a flat and standard hierarchical classifier. Consequently our approach offers a solution to overcome problems for labeling data with similar classes. / by Zachary D. Blanks. / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

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, 2019 / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 273-284). / This thesis focuses on impactful applications of large-scale optimization in transportation and machine learning. Using both theory and computational experiments, we introduce novel optimization algorithms to overcome the tractability issues that arise in real world applications. We work towards the implementation of these algorithms, through software contributions, public policy work, and a formal study of machine learning interpretability. Our implementation in Boston Public Schools generates millions of dollars in yearly transportation savings and led to important public policy consequences in the United States. This work is motivated by large-scale transportation problems that present significant optimization challenges. In particular, we study the problem of ride-sharing, the online routing of hundreds of thousands of customers every day in New York City. / We also contribute to travel time estimation from origin-destination data, on city routing networks with tens of thousands of roads. We additionally consider the problem of school transportation, the scheduling of hundreds of buses to send tens of thousands of children to school everyday. This transportation problem is related to the choice of school start times, for which we also propose an optimization framework. Building on these applications, we present methodological contributions in large- scale optimization. We introduce state-of-the-art algorithms for scheduling problems with time-window (backbone) and for school bus routing (BiRD). Our work on travel time estimation tractably produces solutions to the inverse shortest path length problem, solving a sequence of second order cone problems. We also present a theoretical and empirical study of the stochastic proximal point algorithm, an alternative to stochastic gradient methods (the de-facto algorithm for large-scale learning). / We also aim at the implementation of these algorithms, through software contributions, public policy work (together with stakeholders and journalists), and a collaboration with the city of Boston. Explaining complex algorithms to decision-makers is a difficult task, therefore we introduce an optimization framework to decomposes models into a sequence of simple building blocks. This allows us to introduce formal measure of the "interpretability" of a large class of machine learning models, and to study tradeoffs between this measure and model performance, the price of interpretability. / by Sébastien Martin. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

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, 2019 / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 191-198). / Big data and the internet are shifting the paradigm in promotional pricing and advertising. The amount of readily available data from both point-of-sale systems and web cookies has grown, enabling a shift from qualitative design to quantitative tools. In this work, we address how firms can utilize the power of analytics to maximize profits in both their offline and online channels. First, we consider an online setting, in which an advertiser can target ads to the customer in question. The goal of the advertiser is to determine how to target the right audience with their ads. We study this problem as a Multi-Armed Bandit problem with periodic budgets, and develop an Optimistic-Robust Learning algorithm with bounded expected regret. Practically, simulations on synthetic and real-world ad data show that the algorithm reduces regret by at least 10-20% compared to benchmarks. / Second, we consider an offline setting, in which a retailer can boost profits through the use of promotion vehicles such as flyers and commercials. The goal of the retailer is to decide how to schedule the right promotion vehicles for their products. We model the problem as a non-linear bipartite matching-type problem, and develop provably-good algorithms: a greedy algorithm and an approximate integer program of polynomial size. From a practical perspective, we test our methods on actual data and show potential profit increases of 2-9%. Third, we explore a supply chain setting, in which a supplier offers vendor funds to a retailer who promotionally prices the product to the customer. Vendor funds are trade deals in which a supplier offers a retailer a short-term discount on a specific product, encouraging the retailer to discount the product. / We model the problem as a bilevel optimization model and show that a pass-through constrained vendor fund mitigates forward-buying and coordinates the supply chain on the short term. Finally, we present a pilot study on the impact of promotional pricing on retail profits. We assess the potential impact of our promotion planning tool on historical data from a large retailer. Our results suggest a 9.94% profit improvement for the retailer. / by Lennart Baardman. / 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, September, 2020 / Cataloged from student-submitted PDF of thesis. / Includes bibliographical references (pages 261-268). / Sales promotions are a popular type of marketing strategy. When undertaking a sales promotion, products are promoted using short-term price reductions to stimulate their demand and increase their sales. These sales promotions are widely used in practice by retailers. When undertaking a sales promotion, retailers must take into consideration both the direct and indirect effects of price promotions on consumers, and as a result, on the demand. In this thesis, we consider the impact of two of these indirect effects on the planning process of promotions. First, we consider the problem of the promotion planning process for fast-moving consumer goods. The main challenge when considering the promotion planning problem for fast-moving consumer goods is the negative indirect effect of promotions on future sales. While temporary price reductions substantially increase demand, in the following periods after a temporary price reduction, retailers observe a slowdown in sales. / To capture this post promotion slowdown, we suggest a new set of past prices (namely, the last seen as well as the minimum price seen within a limited number of past periods) as features in the demand model. We refer to demand models that use this set of past prices as Bounded Memory Peak-End models. When tested on realworld data, our suggested demand model improved the estimation quality relative to a traditional estimation approach through a relative improvement in WMAPE by approximately 1 - 19%. In addition to the improvement in prediction accuracy, we analyze the sensitivity of our proposed Bounded Memory Peak-End demand model to demand misspecification. Through statistical analysis, and using principles from duality theory, we establish that even in the face of demand misspecification, the proposed Bounded Memory Peak-End model can capture the demand with provably low estimation error, and with low impact on the resulting optimal pricing policy. / The structure of the new proposed demand model allows us to derive fast algorithms that can find the optimal solution to the problem of promotion planning for a single item. For the case of promotion planning for multiple items, although we show that the problem is NP-hard in the strong sense, we propose a Polynomial Time Approximation Scheme that can solve the problem efficiently. Overall, we show that using our proposed approach, the retailer can obtain an increase of 4 - 15.6% in profit compared to current practice. Second, we consider the promotion targeting problem for trendy commodities. In the case of trendy commodities, the demand is driven, among other factors, by social trends. Examples of trendy commodities include fashion items, wearable electronics, and smartphones. To capture the demand with high accuracy, retailers must understand how the purchasing behavior of customers can impact the future purchasing behavior of other customers. / Social media can be instrumental in learning how consumers can impose trends on one another. Unfortunately, many retailers are unable to obtain this information due to high costs and privacy issues. This has motivated us to develop a model that detects customer relationships based only on transaction data history. Incorporating the customer to customer trend in the demand estimation, we observe a significant improvement of 12% in the WMAPE forecasting metric. The proposed customer to customer trend-based demand model subsequently allows us to formulate the promotion targeting optimization problem in a way that consider the indirect effect of targeted promotions through trends. We show that the problem of finding the personalized promotion policy that would maximize the profit function is NP-hard. Nonetheless, we introduce an adaptive greedy algorithm that is intuitive to implement and can find a provably near-optimal personalized promotion policy. / We tested our approach on Oracle data and observed a 5-12% improvement in terms of profit. / by Tamar Cohen-Hillel. / 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, September, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 119-123). / Industrial control systems (ICS) are pervasive in modern society and increasingly under threat of cyber attack. Due to the critical nature of these systems, which govern everything from power and wastewater plants to refineries and manufacturing, a successful ICS cyber attack can result in serious physical consequences. This thesis evaluates multiple anomaly detection methods to quickly and accurately detect ICS cyber attacks. Two fundamental challenges in developing ICS cyber attack detection methods are the lack of historical attack data and the ability of attackers to make their malicious activity appear normal. The goal of this thesis is to develop methods which generalize well to anomalies that are not included in the training data and to increase the sensitivity of detection methods without increasing the false alarm rate. The thesis presents and analyzes a baseline detection method, the multivariate Shewhart control chart, and four extensions to the Shewhart chart which use machine learning or optimization methods to improve detection performance. Two of these methods, stationary subspace analysis and maximized ratio divergence analysis, are based on dimensionality reduction techniques, and an additional model-based method is implemented using residuals from LASSO regression models. The thesis also develops an ensemble method which uses an optimization formulation to combine the output of multiple models in a way that minimizes detection delay. When evaluated on 380 samples from the Kasperskey Tennessee Eastman process dataset, a simulated chemical process that includes disruptions from cyber attacks, the ensemble method reduced detection delay on attack data by 12% (55 minutes) on average when compared to the baseline method and was 9% (42 minutes) faster on average than the method which performed best on training data. / by Jessamyn Liu. / 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, September, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 127-134). / During the past decade an increasing trend in the Data Center Network's traffic has been observed. This traffic is characterized mostly by many small bursty flows (mice) that last for less than few milliseconds as well as a few heavier more persistent (elephant) flows between certain number of nodes. As a result many relatively underutilized network links become momentarily hotspots with increased chance of packet loss. A potential solution could be given by Reconfigurable Optical Data Centers, due to higher traffic aggregation links and topology adaptation capabilities. An example is a novel two level hierarchical WDM-Based scalable Data Center Network architecture, RHODA, which is based on the interconnection of high speed equal sized clusters of Racks. We study the traffic based dynamic cluster membership reconfiguration of the Racks. Main goal is to maintain a near optimal network operation with respect to minimization of the inter cluster traffic, while emphasising better link utilization and network scalability. We present four algorithms, two deterministic greedy and two stochastic iterative, and discuss the tradeoffs of their use. Our results draw two main conclusion: 1) Stochastic iterative algorithms are more suitable for dynamic traffic based reconfiguration 2) Fast algorithmic deployments come at a price of reduced optimality / by Georgia Dimaki. / 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, September, 2020 / Cataloged from student-submitted PDF of thesis. / Includes bibliographical references (pages 187-203). / Networks offer a unified, conceptual formalism for reasoning about complex, relational systems. While pioneering work in network science focused primarily on the ability of "universal" models to explain the features of observed systems, contemporary research increasingly focuses on challenges and opportunities for data analysis in complex systems. In this thesis we study four problems, each of which is informed by the need for theory-informed modeling in network data science. The first chapter is a study of binary-state adaptive voter models (AVMs). AVMs model the emergence of global opinion-based network polarization from localized decision-making, doing so through a simple coupling of node and edge states. This coupling yields rich behavior, including phase transitions and low-dimensional quasistable manifolds. However, the coupling also makes these models extremely difficult to analyze. / Exploiting a novel asymmetry in the local dynamics, we provide low-dimensional approximations of unprecedented accuracy for one AVM variant, and of competitive accuracy for another. In the second chapter, we continue our focus on fragmentation in social systems with a study of spatial segregation. While the question of how to measure and quantify segregation has received extensive treatment in the sociological literature, this treatment tends to be mathematically disjoint. This results in scholars often re-proving the same results for special cases of measures, and grappling with incomparable methods for incorporating the role of space in their analyses. We provide contributions to address each of these issues. With respect to the first, we unify a large body of extant segregation measures through the calculus of Bregman divergences, showing that the most popular measures are instantiations of generalized mutual informations. / We then formulate a microscopic measure of spatial structure - the local information density - and prove a novel information-geometric result in order to measure it on real data in the common case in which the data is embedded in planar network. Using these tools, we are then able to formulate and evaluate several network-based regionalization algorithms for multiscale spatial analysis. We then take up two questions in null random graph modeling. The first of these develops a family of null random models for hypergraphs, the natural mathematical representation of polyadic networks in which multiple entities interact simultaneously. We formulate two distributions over spaces of hypergraphs subject to fixed node degree and edge dimension sequences, and provide Markov Chain Monte Carlo algorithms for sampling from them. We then conduct a sequence of experiments to highlight the role of hypergraph configuration models in the data science of polyadic networks. / We show that (a) the use of hypergraph nulls can lead to directionally different hypothesis-testing than the use of traditional nulls and that (b) polyadic nulls support richer and more complex measurements of graph structure. We close with a formulation of a novel measure of correlation in hypergraphs, as well as an asymptotic formula for estimating its expectations under one of our configuration models. In the final chapter, we study the expected adjacency matrix of a uniformly random multigraph with a fixed degree sequence. This matrix is an input into several common network analyses, including community-detection and mean-field theories of spreading properties on contact networks. The actual structure of this matrix, however, is not well understood. The main issues are (a) the combinatorial complexity of the space on which this random graph is defined and (b) an erroneous folk-theorem among network scientists which stems from confusion with related models. / By studying the dynamics of a Markov chain sampler, we prove a sequence of approximations that allow us to estimate the expected adjacency matrix - and other elementwise moments - using a fast numerical scheme with qualified uniqueness guarantees. We illustrate using a series of experiments on primary and secondary school contact networks, showing order-of-magnitude improvements over extant methods. We conclude with a description of several directions of future work. / by Philip S. Chodrow. / 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, September, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 197-203). / Stochastic traffic simulators are widely used in the transportation community to model real-world urban road networks in applications ranging from real-time congestion routing and control to traffic state prediction. Online calibration of these simulators plays a crucial role in achieving high accuracy in the replication and prediction of streaming traffic data (i.e., link flows, densities). In order to be relevant in a real-time context, the problem must also be solved within a strict computational budget. The primary goal of this thesis is to develop an algorithm that adequately solves the online calibration problem for high-dimensional cases and on large-scale networks. In the first half, a new online calibration algorithm is proposed that incorporates structural information from an analytical metamodel into a general-purpose extended Kalman filter framework. / The metamodel is built around a macroscopic network model that relates calibration parameters to field measurements in an analytical, computationally tractable, and differentiable way. Using the metamodel as an analytical approximation of the traffic simulator improves the computational efficiency of the linearization step of the extended Kalman filter, making it suitable for use in large-scale calibration problems. The embedded analytical network model provides a secondary benefit of making the algorithm more robust to simulator stochasticity compared with traditional black-box calibration methods. In the second half, the proposed algorithm is adapted for the case study of online calibration of travel demand as defined by a set of time-dependent origin-destination matrices. First, an analytical network model relating origin-destination demand to link measurements is formulated and validated on the Singapore expressway network. / Next, the proposed algorithm is validated on a synthetic toy network, where its flexibility in calibrating to multiple sources of field data is demonstrated. The empirical results show marked improvement over the baseline of offline calibration and comparable performance to multiple benchmark algorithms from the literature. Finally, the proposed algorithm is applied to a problem of dimension 4,050 on the Singapore expressway network to evaluate its feasibility for large-scale problems. Empirical results confirm the real-time performance of the algorithm in a real-world setting, with strong accuracy in the estimation of sensor counts. / by Kevin Zhang. / 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, September, 2020 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 213-219). / With the rapid advancement of information technology and accelerated development of data science, the importance of integrating data into decision-making has never been stronger. In this thesis, we propose data-driven algorithms to incorporate learning from data in three operations problems, concerning both online learning and offline learning settings. First, we study a single product pricing problem with demand censoring in an offline data-driven setting. In this problem, a retailer is given a finite level of inventory, and faces a random demand that is price sensitive in a linear fashion with unknown parameters and distribution. Any unsatisfied demand is lost and unobservable. The retailer's objective is to use offline censored demand data to find an optimal price, maximizing her expected revenue with finite inventories. / We characterize an exact condition for the identifiability of near-optimal algorithms, and propose a data-driven algorithm that guarantees near-optimality in the identifiable case and approaches best-achievable optimality gap in the unidentifiable case. Next, we study the classic multi-period joint pricing and inventory control problem in an offline data-driven setting. We assume the demand functions and noise distributions are unknown, and propose a data-driven approximation algorithm, which uses offline demand data to solve the joint pricing and inventory control problem. We establish a polynomial sample complexity bound, the number of data samples needed to guarantee a near-optimal profit. A simulation study suggests that the data-driven algorithm solves the dynamic program effectively. Finally, we study an online learning problem for product selection in urban warehouses managed by fast-delivery retailers. We distill the problem into a semi-bandit model with linear generalization. / There are n products, each with a feature vector of dimension T. In each of the T periods, a retailer selects K products to offer, where T is much greater than T or b. We propose an online learning algorithm that iteratively shrinks the upper confidence bounds within each period. Compared to the standard UCB algorithm, we prove the new algorithm reduces the most dominant regret term by a factor of d, and experiments on datasets from Alibaba Group suggest it lowers the total regret by at least 10%.. / by Li 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, September, 2020 / Page 236 blank. Cataloged from PDF version of thesis. / Includes bibliographical references (pages 223-235). / The upstream parts of the agricultural supply chain consists of millions of smallholder farmers who continue to suffer from extreme poverty. The first stream of research in this thesis focuses on online agri-platforms which have been launched to connect geographically isolated markets in many developing countries. This work is in close collaboration with the state government of Karnataka in India which launched the Unified Market Platform (UMP). Leveraging both public data and platform data, a difference-in-differences analysis in Chapter 2 suggests that the implementation of the UMP has significantly increased modal price of certain commodities (5.1%-3.5%), while prices for other commodities have not changed. The analysis provides evidence that logistical challenges, bidding efficiency, market concentration, and price discovery process are important factors explaining the variable impact of UMP on prices. / Based on the insights, Chapter 3 describes the design, analysis and field implementation of a new two-stage auction mechanism. From February to May 2019, commodities worth more than $6 million (USD) had been traded under the new auction. Our empirical analysis suggests that the implementation has yielded a significant 4.7% price increase with an impact on farmer profitability ranging 60%-158%, affecting over 10,000 farmers who traded in the treatment market. The second stream of research work in the thesis turns to consumer welfare and identifies effective policies to tackle structural challenges of food safety and food security that arise in traditional agricultural markets. In Chapter 4, we develop a new modeling framework to investigate how quality uncertainty, supply chain dispersion, and imperfect testing capabilities jointly engender suppliers' adulteration behavior. / The results highlight the limitations of only relying on end-product inspection to deter EMA and advocate a more proactive approach that addresses fundamental structural problems in the supply chain. In Chapter 5, we analyze the issue of artificial shortage, the phenomenon that leads to food security risks where powerful traders strategically withhold inventory of essential commodities to create price surge in the market. The behavioral game-theoretic models developed allow us to examine the effectiveness of common government interventions. The analysis demonstrates the disparate effects of different interventions on artificial shortage; while supply allocation schemes often mitigate shortage, cash subsidy can inadvertently aggravate shortage in the market. Further, using field data from onion markets of India, we structurally estimate that 10% of the total supply is being hoarded by the traders during the lean season. / by Somya Singhvi. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center