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.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 115-120). / We study multi-product revenue management problems, focusing on the role of uncertainty in both the seller and the customer decision processes. We begin by considering a logit model framework for personalized revenue management problems where utilities are functions of customer attributes, so that data for any one customer can be generalized to others via regression. We establish finite-sample convergence guarantees on the model parameters. The parameter convergence guarantees are then extended to out-of-sample performance guarantees in terms of revenue, in the form of a high-probability bound on the gap between the expected revenue of the best action taken under the estimated parameters and the revenue generated by a decision-maker with full knowledge of the choice model. In the second chapter, we study the static assortment optimization problem under weakly rational choice. This setting applies to most choice models studied and used in practice. We give a mixed-integer linear optimization formulation and present two branch-and-bound algorithms for solving this optimization problem. The formulation and algorithms require only black-box access to purchase probabilities, and thus provide exact solution methods for a general class of discrete choice models, in particular those models without closed-form choice probabilities. We give approximation results for our algorithms in two special cases, and test the performance of our algorithms with heuristic stopping criteria. The third section, motivated by data from an online retailer, describes sales of durable goods online, focusing on the effects of uncertainty about product quality and learning from customer reviews. We describe the nature of the tradeoff between learning product quality over time and substitution effects between products offered in the same category on the same website. Specifically, small differences in product release tines can be magnified substantially over time. The learning process takes longer in markets with more products. The process also takes longer in markets with higher price because customers take more risk in these markets when purchasing under uncertainty. This results in both smaller demand for new products in high-priced markets and more market concentration around fewer, well-established products. We discuss operational implications and show application to a break-even analysis. / by Clark Pixton. / Ph. D.

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 85-87). / Given a set of target detections over several time periods, this paper addresses the multi-target tracking problem (MTT) of optimally assigning detections to targets and estimating the trajectory of the targets over time. MTT has been studied in the literature via predominantly probabilistic methods. In contrast to these approaches, we propose the use of mixed integer optimization (MIO) models and local search algorithms that are (a) scalable, as they provide near optimal solutions for six targets and ten time periods in milliseconds to seconds, (b) general, as they make no assumptions on the data, (c) robust, as they can accommodate missed and false detections of the targets, and (d) easily implementable, as they use at most two tuning parameters. We evaluate the performance of the new methods using a novel metric for complexity of an instance and find that they provide high quality solutions both reliably and quickly for a large range of scenarios, resulting in a promising approach to the area of MTT. / by Zachary Clayton Saunders. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 173-180). / In this thesis, we propose algorithms for solving revenue maximization and inventory control problems in data-driven settings. First, we study the choice-based network revenue management problem. We propose the Approximate Column Generation heuristic (ACG) and Potential Based algorithm (PB) for solving the Choice-based Deterministic Linear Program, an LP relaxation to the problem, to near-optimality. Both algorithms only assume the ability to approximate the underlying single period problem. ACG inherits the empirical efficiency from the Column Generation heuristic, while PB enjoys provable efficiency guarantee. Building on these tractability results, we design an earning-while-learning policy for the online problem under a Multinomial Logit choice model with unknown parameters. The policy is efficient, and achieves a regret sublinear in the length of the sales horizon. Next, we consider the online dynamic pricing problem, where the underlying demand function is not known to the monopolist. The monopolist is only allowed to make a limited number of price changes during the sales horizon, due to administrative constraints. For any integer m, we provide an information theoretic lower bound on the regret incurred by any pricing policy with at most m price changes. The bound is the best possible, as it matches the regret upper bound incurred by our proposed policy, up to a constant factor. Finally, we study the data-driven capacitated stochastic inventory control problem, where the demand distributions can only be accessed through sampling from offline data. We apply the Sample Average Approximation (SAA) method, and establish a polynomial size upper bound on the number of samples needed to achieve a near-optimal expected cost. Nevertheless, the underlying SAA problem is shown to be #P hard. Motivated by the SAA analysis, we propose a randomized polynomial time approximation scheme which also uses polynomially many samples. To complement our results, we establish an information theoretic lower bound on the number of samples needed to achieve near optimality. / by Wang Chi Cheung. / Ph. D.