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 187-191). / Online retail has grown rapidly in the last decade. Consumers enjoy the convenience of online shopping and home delivery, as well as a vast product assortment. From the business perspective, serving customers directly from warehouses reduces investment needed in physical storefronts. In this thesis, we consider operations management problems that are important to the effective and efficient operations in the warehouse of a large online retailer. We first consider the decision of stocking inventory in the warehouse, for products in the long tail of the online retail assortment. Motivated by real world business practice, we assume the underlying demand distribution is a mixture of known distributions, but with unknown weights. We propose a robust optimization model to decide on inventory levels given a few samples of demand, outperforming standard robust optimization methods in the relevant settings. The next two models are motivated by our collaboration with a large online retailer that operates multiple warehouses. We study a setting in which a warehouse has to fulfill a sequence of orders, each including multiple items. Pickers pick items in batches, and partially completed orders take up space on a sorting area called the wall. This gives rise to a fundamental tradeoff between picking efficiency and sorting efficiency. We propose a batch scheduling model, generalizing existing models by allowing for more general batch processing time functions, as well as incorporating an objective related to multi-item orders. We show hardness results, and propose both approximation algorithms and Integer Programming formulations. Finally, we build a simulation of the warehouse picking process, using data from a large online retailer. We propose a picking policy that better balances the tradeoff between picking and sorting efficiency, achieving a 42% decrease in average wall utilization and a 60% decrease in average order cycle time. We propose a model allowing us to analyze the tradeoffs between two heuristic policies representing the current policy and our proposed policy, and characterize a condition under which our proposed policy makes a small sacrifice in picking efficiency in return for a larger increase in sorting efficiency. This explains the empirical success of our policy. / by Chongli Daniel Chen. / Ph. D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2000. / Includes bibliographical references (leaves 103-112). / This thesis describes two applications of Operations Research to the field of industrial procurement, addressing problems encountered in supplier selection and supplier control, respectively. The first part addresses the problem of designing multi-item procurement auctions in capacity-constrained environments. Using insights from classical auction theory, we construct an optimization based auction mechanism ("Smart Market") relying on the dynamic resolution of a linear program minimizing the buyer's cost under the suppliers' capacity constraints. Based on the optimal allocation corresponding to each set of bids, suppliers can respond by modifying their offers, giving rise to a dynamic competitive bidding process. A first contribution of our work is the solution we develop to assist suppliers, a bidding suggestion device based on a myopic best response (MBR) calculation solving an inverse optimization problem. The second main contribution is the analytical study of the bid profile sequences arising in this smart market within a game-theoretic framework assuming linear costs for the suppliers. Under a particularly weak behavioral assumption and some symmetry requirements, we establish an explicit upper bound for the winning bids when the auction terminates as a function of the market environment parameters. This bound constitutes a performance guarantee from the buyer's perspective, and provides insights on how capacity constraints affect relative market power. We then formulate a complete behavioral model and solution methodology based on the MBR rationale and the concept of local Nash Equilibrium, and argue its realism. We derive analytically some structural and convergence properties of the MBR dynamics in the simplest non-trivial market environment, suggesting further possible design improvements, and obtain insights on market behavior, efficiency and incentive compatibility issues through numerical simulations. In particular, experiments tend to show that suppliers might be relied upon to provide their own capacity information when procurement contracts are properly designed. The second part is motivated by a strategic challenge faced in particular by electronic goods manufacturing companies. Because most of their assembly operations are highly automated, procurement delays typically account for most of the total production lead-time, and have a major impact on inventory costs. However, in an increasingly global outsourcing environment, these delays can be both long and uncertain. This leads us to examine the problem of optimally procuring components in a single-product stochastic assembly system. We consider a model where product demand follows a stationary Poisson process, assembly is instantaneous, and unsatisfied demand is backordered. The suppliers are uncapacitated and the components have independent but non-identically distributed stochastic procurement delays. The following class of policies is considered: The finished goods inventory is initially filled to its base stock level, and each customer order triggers a replenishment order for a component after a component-dependent postponement lead time. The objective is to minimize the sum of holding and backorder costs in steady-state over this class of replenishment policies. To keep the analysis tractable, we assume that no mixing occurs between component orders (synchronization assumption). Combining classical queueing network theory with original results concerning a distributional property we call closure under maximization and translation (CMT), we obtain a near-optimal solution in closed-form. We then demonstrate through simulation, using industrial data from a Hewlett-Packard facility, that the policy we derived significantly outperforms other policies commonly used in practice. In addition, we show that it is quite robust with respect to various model assumptions, except the synchronization one. We thus conclude that this work is potentially amenable to implementation in the settings where this assumption is not exceedingly demanding. Moreover, we believe that the CMT distributions we introduce could also prove useful in a variety of applications beyond the context of supply chains, such as project management, reliability analysis, and the study of natural extreme phenomena. / by Jérémie Gallien. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics; and, (Ph.D.)--Massachusetts Institute of Technology, Operations Research Center, 1999. / Includes bibliographical references (p. 144-151). / The unifying contribution of this thesis is to show that optimization is a very powerful tool that provides unexpected insights and impact on a variety of domains, such as probability, finance and revenue management. The thesis has two parts: In the first part, we use optimization models and techniques to derive optimal bounds for moment type problems in probability and finance. In the probability framework , we derive optimal inequalities for P(X E S), for a multivariate random variable X that has a given collection of moments, and an arbitrary set S. We provide a complete characterization of the problem of finding optimal bounds, from a complexity standpoint. We propose an efficient algorithm to compute tight bounds when S is a union of a polynomial number of convex sets, and up to second order moments of X are known. We show that it is NP-hard to obtain such bounds if the domain of X is Rn+, or if moments of third or higher order are given. Using convex optimization methods, we prove explicit tight bounds that generalize the classical Markov and Chebyshev inequalities, when the set S is convex. We examine implications to the law of large numbers, and the central limit theorem. In the finance framework, we investigate the applicability of such moment methods to obtain optimal bounds on financial quantities, when information about related instruments is available. We investigate the relation of option and stock prices just based on the no-arbitrage assumption, without assuming any model for the underlying price dynamics. We introduce convex optimization methods, duality and complexity theory to shed new light to this relation. We propose efficient algorithms for finding best possible bounds on option prices on multiple assets, based on the mean and variance of the underlying asset prices and their correlations and identify cases under which the derivation of such bounds is NP-hard. Conversely, given observable option prices, we provide best possible bounds on the moments of the underlying assets as well as prices of other options on the same asset. Our methods naturally extend for the case of transactions costs. The second part of this thesis applies dynamic and linear optimization methods to network revenue management applications. We investigate dynamic policies for allocating inventory to correlated, stochastic demand for multiple classes, in a network environment so as to maximize total expected revenues. We design a new efficient algorithm, based on approximate dynamic programming that provides structural insights into the optimal policy by using adaptive, non-additive bid-prices from a linear programming relaxation. Under mild restrictions on the demand process, our algorithm is asymptotically optimal as the number of periods in the time horizon increases, capacities being held fixed. In contrast, we prove that this is not true for additive bid-price mechanisms. We provide computational results that give insight into the performance of these algorithms, for several networks and demand scenarios. We extend these algorithms to handle cancellations and no-shows by incorporating overbooking decisions in the underlying mathematical programming formulation. / by Ioana Popescu. / Ph.D.

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 183-190). / Optimization under uncertainty forms the foundation for many of the fundamental problems the operations research community seeks to solve. In this thesis, we develop and analyze algorithms that incorporate ideas from machine learning to optimize uncertain objectives directly from data. In the first chapter, we consider problems in which the decision affects the observed outcome, such as in personalized medicine and pricing. We present a framework for using observational data to learn to optimize an uncertain objective over a continuous and multi-dimensional decision space. Our approach accounts for the uncertainty in predictions, and we provide theoretical results that show this adds value. In addition, we test our approach on a Warfarin dosing example, and it outperforms the leading alternative methods. / In the second chapter, we develop an approach for solving dynamic optimization problems with covariates that uses machine learning to approximate the unknown stochastic process of the uncertainty. We provide theoretical guarantees on the effectiveness of our method and validate the guarantees with computational experiments. In the third chapter, we introduce a distributionally robust approach for incorporating covariates in large-scale, data-driven dynamic optimization. We prove that it is asymptotically optimal and provide a tractable general-purpose approximation scheme that scales to problems with many temporal stages. Across examples in shipment planning, inventory management, and finance, our method achieves improvements of up to 15% over alternatives. In the final chapter, we apply the techniques developed in previous chapters to the problem of optimizing the operating room schedule at a major US hospital. / Our partner institution faces significant census variability throughout the week, which limits the amount of patients it can accept due to resource constraints at peak times. We introduce a data-driven approach for this problem that combines machine learning with mixed integer optimization and demonstrate that it can reliably reduce the maximal weekly census. / by Christopher George McCord. / 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 213-221). / The availability and prevalence of data have provided a substantial opportunity for decision makers to improve decisions and outcomes by effectively using this data. In this thesis, we propose approaches that start from data leading to high-quality decisions and predictions in various application areas. In the first chapter, we consider problems with observational data, and propose variants of machine learning (ML) algorithms that are trained by taking into account decision quality. The traditional approach to such a task has often focused on two-steps, separating the estimation task from the subsequent optimization task which uses these estimated models. Consequently, this approach can miss out on potential improvements in decision quality by considering these tasks jointly. Crucially, this leads to stronger prescriptive performance, particularly for smaller training set sizes, and improves the decision quality by 3 - 5% over other state-of-the-art methods. / We introduce the idea of uncertainty penalization to control the optimism of these methods which improves their performance, and propose finite-sample regret bounds. Through experiments on real and synthetic data sets, we demonstrate the value of this approach. In the second chapter, we consider observational data with decision-dependent uncertainty; in particular, we focus on problems with a finite number of possible decisions (treatments). We present our method of prescriptive trees, that prescribes the best treatment option by learning from observational data while simultaneously predicting counterfactuals. We demonstrate the effectiveness of such an approach using real data for the problem of personalized diabetes management. In the third chapter, we consider stochastic optimization problems when the sample average approximation approach is computationally expensive. / We introduce a novel measure, called the Prescriptive divergence which takes into account the decision quality of the scenarios, and consider scenario reduction in this context. We demonstrate the power of this optimization-based approach on various examples. In the fourth chapter, we present our work on a problem in predictive analytics where we focus on ML problems from a modern optimization perspective. For sparse shape-constrained regression problems, we propose modern optimization based algorithms that are scalable, and recover the true support with high accuracy and low false positive rates. / by Nishanth Mundru. / 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: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2019 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 82-90). / Social networks have given us the ability to spread messages and influence large populations very easily. Malicious actors can take advantage of social networks to manipulate opinions using artificial accounts, or bots. It is suspected that the 2016 U.S. presidential election was the victim of such social network interference, potentially by foreign actors. Foreign influence bots are also suspected of having attacked European elections. The bots main action was the sharing of politically polarized content in an effort to shift opinions. In this work we present a method to identify coordinated influence campaigns, and quantify the impact of bots on the opinions of users in a social network. First, we provide evidence that modern bots in the social network Twitter coordinate their attacks. They do not create original content, but rather amplify certain human users by disproportionately retweeting them. We design a new algorithm for bot detection, and utilize the Ising model from statistical physics to model the network structure and bot labels. Then, we leverage a model for opinion dynamics in a social network, which we validate by showing that the user opinions predicted by the model align with the opinions of these users' based on their social media posts. Finally, we use the opinion model to calculate how the opinions shift when we remove the bots from the network. Our high level finding is that a small number of bots can have a disproportionate impact on the network opinions. / by Nicolas Guenon des Mesnards / 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: 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

No description available.