Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references. / The online market has expanded tremendously over the past two decades across all industries ranging from retail to travel. This trend has resulted in the growing availability of information regarding consumer preferences and purchase behavior, sparking the development of increasingly more sophisticated product recommendation systems. Thus, a competitive edge in this rapidly growing sector could be worth up to millions of dollars in revenue for an online seller. Motivated by this increasingly prevalent problem, we propose an innovative model that selects, prices and recommends a personalized bundle of products to an online consumer. This model captures the trade-off between myopic profit maximization and inventory management, while selecting relevant products from consumer preferences. We develop two classes of approximation algorithms that run efficiently in real-time and provide analytical guarantees on their performance. We present practical applications through two case studies using: (i) point-of-sale transaction data from a large U.S. e-tailer, and, (ii) ticket transaction data from a premier global airline. The results demonstrate that our approaches result in significant improvements on the order of 3-7% lifts in expected revenue over current industry practices. We then extend this model to the setting in which consumer demand is subject to uncertainty. We address this challenge using dynamic learning and then improve upon it with robust optimization. We first frame our learning model as a contextual nonlinear multi-armed bandit problem and develop an approximation algorithm to solve it in real-time. We provide analytical guarantees on the asymptotic behavior of this algorithm's regret, showing that with high probability it is on the order of O([square root of] T). Our computational studies demonstrate this algorithm's tractability across various numbers of products, consumer features, and demand functions, and illustrate how it significantly out performs benchmark strategies. Given that demand estimates inherently contain error, we next consider a robust optimization approach under row-wise demand uncertainty. We define the robust counterparts under both polynomial and ellipsoidal uncertainty sets. Computational analysis shows that robust optimization is critical in highly constrained inventory settings, however the price of robustness drastically grows as a result of pricing strategies if the level of conservatism is too high. / by Anna Papush. / Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 219-230). / Two principles at the forefront of modern machine learning and statistics are sparse modeling and robustness. Sparse modeling enables the construction of simpler statistical models, with examples including the Lasso and matrix completion. At the same time, statistical models need to be robust--they should perform well when data is noisy--in order to make reliable decisions. While sparsity and robustness are often closely related, the exact relationship and subsequent trade-offs are not always transparent. For example, convex penalties like the Lasso are often motivated by sparsity considerations, yet the success of these methods is also driven by their robustness. In this thesis, we develop new statistical methods for sparse and robust modeling and clarify the relationship between these two principles. The first portion of the thesis focuses on a new methodological approach to the old multivariate statistical problem of Factor Analysis: finding a low-dimensional description of covariance structure among a set of random variables. Here we propose and analyze a practically tractable family of estimators for this problem. Our approach allows us to exploit bilinearities and eigenvalue structure and thereby show that convex heuristics obtain optimal estimators in many instances. In the latter portion of the thesis, we focus on developing a unified perspective on various penalty methods employed throughout statistical learning. In doing so, we provide a precise characterization of the relationship between robust optimization and a more traditional penalization approach. Further, we show how the threads of optimization under uncertainty and sparse modeling come together by focusing on the trimmed Lasso, a penalization approach to the best subset selection problem. We also contextualize the trimmed Lasso within the broader penalty methods literature by characterizing the relationship with usual separable penalty approaches; as a result, we show that this estimation scheme leads to a richer class of models. / by Martin Steven Copenhaver. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (p. 91-95). / The Departure Planner (DP) is a concept for a decision-aiding tool that is aimed at improving the performance of departure operations at major congested airports. In order to support the development of DP tools and other improved methods for departure operations, this thesis is an effort to gain a deep understanding of the underlying dynamics of the departure process based on field observations and data analysis conducted at Boston Logan International Airport. It was observed that the departure process is a complex interactive queuing system and a highly controlled system as the air traffic controllers manage the traffic. Based on these observations, a core departure process abstraction was posed which consists of a queuing element that represents the delays and a control element that represents the air traffic controller actions. Namely, the abstraction represents the control element by blocking the flow of aircraft in order to maintain the safe operation of the airport resources according to the A TC rules and procedures and to regulate the outbound flow to constrained downstream resources. Based on this physical abstraction, an analytical queuing framework was posed and used to analyze the departure process dynamics under different scenarios: the overall departure process between pushback and takeoff, departure sub-processes between controller/pilot communication events and under the effect of downstream restrictions. Passing was used as a manifestation of the control behavior, where passing results mainly from sequencing of aircraft and their suspension under special circumstances such as downstream restrictions. Insights about the departure process queuing dynamics and control behavior are discussed. In particular it was observed that at Logan airport there is a high level of uncertainty and a limited level of sequencing control, hindering the ability of the air traffic controllers to manage the traffic efficiently and in compliance with restrictions. / by Husni Rifat Idris. / S.M.

Thesis: S.M., 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 69-71). / An agent wants to form a connection with a predetermined set of target users over social media. Because forming a connection is known as "following" in social networks such as Twitter, we refer to this as the follow-back problem. The targets and their friends form a directed graph which we refer to as the "friends graph." The agent's goal is to get the targets to follow it, and it is allowed to interact with the targets and their friends. To understand what features impact the probability of an interaction resulting in a follow-back, we conduct an empirical analysis of several thousand interactions in Twitter. We build a model of the follow-back probabilities based upon this analysis which incorporates features such as the friend and follower count of the target and the neighborhood overlap of the target with the agent. We find optimal policies for simple network topologies such as directed acyclic graphs. For arbitrary directed graphs we develop integer programming heuristics that employ network centrality measures and a graph score we define as the follow-back score. We show that these heuristic policies perform well in simulation on a real Twitter network. / by Krishnan Rajagopalan. / S.M.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, Operations Research Center, 1999. / Includes bibliographical references (p. 177-180). / This thesis proposes methods of allocating airport capacity to the users of the National Airspace System (NAS) during periods in which demand for the resources exceeds capacity. A metric by which the proposed methods are judged is the value that the users of the N AS are able to realize through the allocation. Maximization of this metric produces notably different results from minimization of flight-minutes of delay and similar objectives employed in related works. The heart of this approach is the treatment of the Federal Aviation Administration (FAA) and the NAS users as solvers of subproblems in a decomposition of the overall problem of determining how to operate the system. The best possible capacity allocation method would allow the users, to achieve the same result collectively that a single omniscient entity in control of all decisions in the system could achieve. The typical approach to decomposition employed in optimization, that of modifying the subproblem objectives through a penalty function determined by a master "dual" problem, is employed in the Objective-Based Allocation Method (OBAM). It is shown that the proper choice of penalty function results in a method that performs well dynamically and, assuming each user operates to maximize its operating objectives through the allocation, achieves the optimal solution that an omniscient single controller would achieve. OBAM requires complete communication of user objectives and constraints to achieve optimality. It also requires that the penalty functions used to coordinate the subproblem solutions be added to the user objective functions through assessment of fees. The second part of this thesis addresses the improvement of the decomposition by changing the nature of the allocation without these requirements. Rather than allocate airport arrival capacity alone, a more general notion of airport capacity that captures the interactions between arrival and departure processes at an airport is allocated. This allows the users the flexibility to adjust the operations mix of the airport according to their objectives and improves the ability of the system to match demand to forecast airport capacity. Through simulation, it is shown that this approach could improve significantly on the primary metric of achieving user value. In addition, the approach facilitates side benefits, such as the reduction of fuel consumption, the reduction of harmful emissions into the environment, and the improvement of service reliability for the flying public. / by William D. Hall. / 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 105-111). / In this thesis, we present a system to make personalized lifestyle and health decisions for diabetes management, as well as for general health and diet management. In particular, we address the following components of the system: (a) eciently learning preferences through a dynamic questionnaire that accounts for human behavior; (b) modeling blood glucose behavior and updating these models to match individual measurements; and (c) using the learned preferences and blood glucose models to generate an overall diet and exercise plan using mixed-integer robust optimization. In the first part, we propose a method to address (a) above, using integer and robust optimization. Despite the importance of personalization for successful lifestyle modification, current systems for diabetes and dieting do not attempt to use individual preferences to make suggestions. We present a general approach to learning preferences, that includes an efficient and dynamic questionnaire that accounts for response errors, and robust optimization models using risk measures to account for the commonly seen human behavior of loss aversion. We then address part (b) of our system, by first modeling blood glucose behavior as a function of food consumed and exercise performed. We rely on known attributes of dierent foods as well as individual data to build these models. We also show how we use optimization to dynamically update the parameters of the model using new data as it becomes available. In the third part of this thesis, we address (c) by using mixed-integer optimization to nd an optimal meal and exercise plan for the user that minimizes blood glucose levels while maximizing preferences. We then present a robust counterpart to the formulation, that minimizes blood glucose levels subject to uncertainty in the blood glucose models. We have implemented our system as an online application, and conclude by showing a demonstration of the overall program. / by Allison Kelly O'Hair. / 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 143-154). / Public transportation is undeniably an effective way to move a large number of people in a city. Its ineffectiveness, such as long travel times, poor coverage, and lack of direct services, however, makes it unappealing to many commuters. In this thesis, we address some of the shortcomings and propose solutions for making public transportation more preferable. The first part of this thesis is focused on improving existing bus services to provide higher levels of service. We propose an optimization model to determine limited-stop service to be operated in parallel with local service to maximize total user welfare. Theoretical properties of the model are established and used to develop an efficient solution approach. We present numerical results obtained using real-world data and demonstrate the benefits of limited-stop services. The second part of this thesis concerns the design of integrated vehicle-sharing and public transportation services. One-way vehicle-sharing services can provide better access to existing public transportation and additional options for trips beyond those provided by public transit. The contributions of this part are twofold. First, we present a framework for evaluating the impacts of integrating one-way vehicles haring service with existing public transportation. Using publicly available data, we construct a graph representing a multi-modal transportation service. Various evaluation metrics based on centrality indices are proposed. Additionally, we introduce the notion of a transfer tree and develop a visualization tool that enables us to easily compare commuting patterns from different origins. The framework is applied to assess the impact of Hubway (a bike-sharing service) on public transportation service in the Boston metropolitan area. Second, we present an optimization model to select a subset of locations at which installing vehicle-sharing stations minimizes overall travel time over the integrated network. Benders decomposition is used to tackle large instances. While a tight formulation generally generates stronger Benders cuts, it requires a large number of variables and constraints, and hence, more computational effort. We propose new algorithms that produce strong Benders cuts quickly by aggregating various variables and constraints. Using data from the Boston metropolitan area, we present computational experiments that confirm the effectiveness of our solution approach. / by Virot Chiraphadhanakul. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / Cataloged from PDF version of thesis. / Includes bibliographical references. / The thesis applies optimization theory to three problems in operations management. In the first part of the thesis, we investigate the impact of inventory control on the availability of drugs to patients at public health facilities in Zambia. We present consistent empirical data and simulation results showing that, because of its failure to properly anticipate seasonal variations in demand and supply lead-times, this system leads to predictable patient-level stock-outs even when there is ample inventory available in the central warehouse. Secondly, we propose an alternative inventory control system relying on mobile devices and mathematical optimization, and present results from a validated simulation model suggesting that its implementation would lead to a substantial improvement of patient access to drugs relative to the current system. In the second part of the thesis, we investigate the impact of returning customers on pricing for fashion Internet retailers. Our analysis of clickstream data from an online fashion retailer shows that a significant proportion of sales is due to returning customers, i.e. customers who first visit an item at a particular price, but purchase the item in a later visit at a lower price. We propose a markdown pricing model that explicitly incorporates returning customers. We propose a model for quantifying the value of the returning pricing model relative to a pricing model that does not distinguish between first-time and returning customers, and determine the value of returning pricing both exactly and through developing bounds. Based on real data from a fashion Internet retailer, we estimate the parameters of the returning demand model and determine the value of the returning pricing model. Lastly, we study the promotion optimization problem faced by grocery retailers, i.e. deciding which items to promote and at what price. Our formulation includes several business rules that arise in practice. We build demand models from data in order to capture the stockpiling behavior through dependence on past prices. This gives rise to a hard problem. For general additive and multiplicative demand structures, we propose efficient LP based methods, show theoretical performance guarantees and validate our results using real data. / by Ngai-Hang Zachary Leung. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 91-93). / We investigate two distinct problems in military radio networking. In the first problem, we study a mobile airborne multi-hop wireless network. The mobility of the nodes leads to dynamic link capacities requiring changes to the topology by adding and removing links. Changes are intended to minimize maximum link load. Mixed integer linear programming is used to periodically find topological modifications resulting in optimal performance. To reduce computation and the rate of changes to the topology, we design and employ heuristic algorithms. We present several such algorithms of differing levels of complexity, and model performance using each. A comparison of the results of each method is given. In the second problem, we study a ground multi-hop wireless network. Scalability is an issue for such ground tactical radio networks, as increasing numbers of nodes and flows compete for the capacity of each link. The introduction of a relay node allows additional routes for traffic flows. Greater benefit is achieved by fixing the relay node at a higher elevation to allow it to broadcast to all other nodes simultaneously, thereby reducing the number of hops packets must travel. We use a combination of linear programming (LP) and novel bounds on the achievable network performance to investigate the benefits of such a relay node. We show that a relay node provides moderate improvement under an all-to-all unicast traffic model and more substantial improvement for broadcast traffic patterns. / by Zachary S. Bunting. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 139-147). / This thesis addresses three issues faced by firms and policy-makers when deciding how to price products and properly incentivize consumers. In the first part of the thesis, we focus on a firm attempting to dynamically adjust prices to maximize profits when facing uncertain demand, as for example airlines selling flights or hotels booking rooms. In particular, we develop a robust sampling-based optimization framework that minimizes the worst-case regret and dynamically adjusts the price according to the realization of demand. We propose a tractable optimization model that uses direct demand samples, where the confidence level of this solution can be obtained from the number of samples used. We further demonstrate the applicability of this approach with a series of numerical experiments and a case study using airline ticketing data. In the second part of the thesis, we propose a model for the adoption of solar photovoltaic technology by residential consumers. Using this model, we develop a framework for policy makers to find optimal subsidy levels in order to achieve a desired adoption target. The technology adoption process follows a discrete choice model, which is reinforced by network effects such as information spread and learning-by-doing. We validate the model through an empirical study of the German solar market, where we estimate the model parameters, generate adoption forecasts and demonstrate how to solve the policy design problem. We use this framework to show that the current policies in Germany could be improved by higher subsidies in the near future and a faster phase-out of the subsidy program. In the third part of the thesis, we model the interaction between a government and an industry player in a two-period game setting under uncertain demand. We show how the timing of decisions will affect the production levels and the cost of the subsidy program. In particular, we show that when the government commits to a fixed policy, it signals to the supplier to produce more in the beginning of the horizon. Consequently, a flexible policy is on average more expensive for the government than a committed policy. / by Ruben Lobel. / Ph.D.