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 203-213). / We study marketplaces in which participants arrive over time, looking to interact with each other. While such interactions have historically been decentralized, the past few years have seen a dramatic increase in the number of internet-enabled platforms which facilitate the process of connecting together, or matching, sets of two or more participants. We will focus mainly on centralized matching markets such as kidney exchange and carpooling platforms. In such platforms, the algorithm which determines whom to match and when to do so plays an important role in the efficiency of the marketplace. In the first part, we study the interface between the participant heterogeneity, the types of matchings that are allowed, and the frequency at which the platform computes the allocations. We provide an empirical analysis of the effect of match frequency based on data from major US Kidney exchange programs. We then study models that enable us to compare the participants' match rates and waiting times under varying matching policies. We show both in theory and in practice that matching quickly can be beneficial, compared to policies which try to increase opportunities for optimization through artificial waiting. Until now, the theory of matching algorithms has focused mostly on static environments and little is known in the case where all participants arrive and depart dynamically. In our second part, we help bridge this gap by introducing a new theoretical problem for dynamic matching when anyone can arrive online. We provide new algorithms with state-of-the-art theoretical guarantees, both in the case of adversarial and random order inputs. Finally, we show that these algorithms perform well on kidney exchange and carpooling data. / by Maximilien Burq. / 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, 2017. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 251-256). / Finding optimal product offerings is a fundamental operational issue in modern retailing, exemplified by the development of recommendation systems and decision support tools. The challenge is that designing an accurate predictive choice model generally comes at the detriment of efficient algorithms, which can prescribe near-optimal decisions. This thesis attempts to resolve this disconnect in the context of assortment and inventory optimization, through theoretical and empirical investigation. First, we tightly characterize the complexity of general nonparametric assortment optimization problems. We reveal connections to maximum independent set and combinatorial pricing problems, allowing to derive strong inapproximability bounds. We devise simple algorithms that achieve essentially best-possible factors with respect to the price ratio, size of customers' consideration sets, etc. Second, we develop a novel tractable approach to choice modeling, in the vein of nonparametric models, by leveraging documented assumptions on the customers' consider-then-choose behavior. We show that the assortment optimization problem can be cast as a dynamic program, that exploits the properties of a bi-partite graph representation to perform a state space collapse. Surprisingly, this exact algorithm is provably and practically efficient under common consider-then-choose assumptions. On the estimation front, we show that a critical step of standard nonparametric estimation methods (rank aggregation) can be solved in polynomial time in settings of interest, contrary to general nonparametric models. Predictive experiments on a large purchase panel dataset show significant improvements against common benchmarks. Third, we turn our attention to joint assortment optimization and inventory management problems under dynamic customer choice substitution. Prior to our work, little was known about these optimization models, which are intractable using modern discrete optimization solvers. Using probabilistic analysis, we unravel hidden structural properties, such as weak notions of submodularity. Building on these findings, we develop efficient and yet conceptually-simple approximation algorithms for common parametric and nonparametric choice models. Among notable results, we provide best-possible approximations under general nonparametric choice models (up to lower-order terms), and develop the first constant-factor approximation under the popular Multinomial Logit model. In synthetic experiments vis-a-vis existing heuristics, our approach is an order of magnitude faster in several cases and increases revenue by 6% to 16%. / by Ali Aouad. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2003. / Includes bibliographical references (p. 83-85). / This thesis studies two operations management topics in online auctions, and is divided into two parts. Motivated by the increasing use of ShopBots to scan Internet auctions, the first part of the thesis analytically examines whether or not two competing auctioneers selling the same commodity should share, or pool, some or all of their bidders. Under pooling, the bidding population is represented by three compartments: bidders dedicated to auction 1, bidders dedicated to auction 2, and pooled bidders participating in both auctions simultaneously. Under a bidder strategy shown to induce a Bayesian equilibrium, a closed form expression for the auctioneers' expected revenue under pooling is found, and pooling is recommended where it produces a greater expected revenue than no pooling (i.e., our objective is revenue maximization). Pooling is generally found to be beneficial as long as the two auctions are not too asymmetric and the underlying valuation distribution has certain concavity characteristics. Asymptotic order statistic arguments are used where explicit characterizations are intractable. The second part of the thesis considers a manufacturer who uses a reverse, or procurement, auction to determine which supplier will be awarded a contract. Each bid consists of a price and a set of non-price attributes (e.g., quality, lead time). The manufacturer is assumed to know the suppliers' cost functions (in terms of the non-price attributes). We analyze how the manufacturer chooses a scoring rule (i.e., a function that ranks the bids in terms of the price and non-price attributes) that attempts to maximize his own utility. Under the assumption that suppliers submit their myopic best-response bids (i.e., they choose their minimum-cost bid to achieve any given score), our proposed scoring rule indeed maximizes the manufacturer's utility within the open-ascending format. / (cont.) The analysis reveals connections between the manufacturer's utility maximization problem and various geometric aspects of the manufacturer's utility and the suppliers' cost functions. / by Damian Ronald Beil. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / 33 / "June 2014." Cataloged from PDF version of thesis. / Includes bibliographical references (pages 51-54). / In this paper we present a mixed integer optimization framework for modeling the shipment of goods between origin destination (O-D) pairs by vehicles of different types over a time-space network. The output of the model is an optimal schedule and routing of vehicle movements and assignment of goods to vehicles. Specifically, this framework allows for: multiple vehicles of differing characteristics (including speed, cost of travel, and capacity), transshipment locations where goods can be transferred between vehicles; and availability times for goods at their origins and delivery time windows for goods at their destinations. The model is composed of three stages: In the first, vehicle quantities, by type, and goods are allocated to routes in order to minimize late deliveries and vehicle movement costs. In the second stage, individual vehicles, specified by vehicle identification numbers, are assigned routes, and goods are assigned to those vehicles based on the results of the first stage and a minimization of costs involved with the transfer of goods between vehicles. In the third stage we reallocate the idle time of vehicles in order to satisfy crew rest constraints. Computational results show that provably optimal or near optimal solutions are possible for realistic instance sizes. / by Nicholas R. Jernigan. / 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. / In an event of a pandemic influenza outbreak such as the great "Spanish Flu" of 1918 and the more recent 2009-2010 H1N1 "Swine Flu" scare, pharmaceutical as well as non-pharmaceutical resources are limited in availability and effectiveness. In this thesis we apply OR methods to evaluate the effectiveness of such resources and the strategies for reducing the number of infections resulting from an outbreak. In the first half of this work, we focus on epidemiological analysis of influenza modeling in a heterogeneous population. The majority of existing epidemiological literature models influenza spread in a statistically homogeneous population, but the model-based inclusion of heterogeneity by contact rate, susceptibility, and infectivity introduces significant effects on disease progression. We introduce a new discrete-time influenza outbreak model for a heterogeneous population and use it to describe the changes in a population's flu-related characteristics over time. This information allows us to evaluate the effectiveness of different vaccine targeting techniques in achieving herd immunity, that is, the point at which there is no further growth in new infections. In the second half of this work we switch to a practical application of OR methods in a pandemic situation. We evaluate the effectiveness of vaccines administered to US states during the 2009-2010 H1N1 pandemic. Since the US is geographically diverse and large, the outbreak progressed at different rates and started at different times in each individual state. We discuss dynamic, multi-regional, vaccine allocation schemes for large geographical entities that take into account the different conditions of the epidemic in each region and maximize the total effect of available vaccines. In addition, we discuss effective strategies for combining vaccines with non-pharmaceutical interventions such as hand-washing and public awareness campaigns to decrease the strain of an outbreak on the population. / by Anna Teytelman. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. / Includes bibliographical references (p. 217-223). / (cont.) Extensions to the core TOTEM model include a demand charge model, used for making daily optimal control decisions when the electric bill includes a charge based on the monthly maximum power draw. The problem of heating, ventilation, and air conditioning (HVAC) control is treated separately since it strongly violates TOTEM's linearity assumptions. Nonetheless, we describe a solution approach to the HVAC problem which operates in conjunction with TOTEM. We also provide an analysis of storage suitability in stochastic supply and demand networks. The node-based approach lends itself well to a software system that uses a drag- and-drop graphical network creation tool. We present a graphical user interface, the XML data representation, and the communication links to and from optimization software. / We develop an extensive yet tractable framework for analyzing and optimally controlling local energy networks. A local energy network is any set of generation, storage, and end-use devices existing to provide energy fulfillment to a building, a group of jointly operated buildings, or a village power system. The software developed is called TOTEM for Total Energy Management, and provides hourly (or sub-hourly) control over the flows in such energy networks. TOTEM manages multiple energy flows such as electricity, chilled water, heat, and steam together, since such energies are often coupled, particularly for networks containing cogeneration turbines (which produce electricity and steam) and absorption chillers (which use steam for driving refrigeration turbines). Due to the large number of interconnected devices in such networks, the model is kept as a linear mixed integer program, able to be solved rapidly with off-the-shelf mathematical optimization packages. Certain nonlinearities, for example input-output relationships for generators, are handled in this linear framework with piecewise linear approximations. Modeling flexibility is achieved by taking a node-centric approach. Each device in the network is represented as a node, and depending on each node's set membership, proper constraint and objective equations are written. Given the network, TOTEM uses hourly electricity and fuel pricing, weather, and demand projections to determine the optimal operating and scheduling strategy for the day, in both deterministic and stochastic settings. MIT's cogeneration plant is used as a case study, with other examples throughout the thesis demonstrate the use of TOTEM for assessing and controlling renewable resources, storage options, and / by David Craft. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. / Includes bibliographical references (p. 149-161). / In this thesis we consider three combinatorial optimization problems. Specifically, we study packing and scheduling questions of relevance in several areas of operations research, including interconnection networks and switch scheduling, VLSI design, and processor scheduling. The first chapter studies a natural edge-coloring question arising from the problem of scheduling packets through an interconnection network. The theoretical model we consider can be seen as a weighted extension of Konig's theorem that states that the minimum number of colors needed to color all edges of a bipartite graph equals the maximum vertex degree. For the weighted generalization, a longstanding open question is to determine the minimum number of colors as a function of n, the maximum total weight adjacent to any vertex. Our main contribution is to show that 2.557n + o(n) colors are sufficient, improving upon earlier work. In the second chapter, we consider the following variant of the classical bin-packing problem: Place a given list of rectangles into the minimum number of unit square bins. In the restricted case where all rectangles are squares, we design an algorithm with an asymptotic performance guarantee arbitrarily close to optimal. In the general case, we give an algorithm that outputs a near-optimal solution, provided it is allowed to use slightly larger bins. Moreover, we extend these algorithmic ideas to handle a number of multidimensional packing problems, obtaining best-known results for several of these. / (cont.) Finally, in the third chapter, we discuss a standard sequencing problem, namely, scheduling precedence-constrained jobs on a single machine to minimize the sum of weighted completion times. We look at the problem from a polyhedral perspective, obtaining, as one of our main results, a generalization of a classical result by Sidney. This new insight allows us to reason that all known 2-approximation algorithms behave similarly. Furthermore, we present a new integer programming model that suggests a strong connection between the scheduling problem and the vertex cover problem. / by José Rafael Correa. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / 85 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 99-104). / Epidemic trajectories and associated social responses vary widely between populations, with severe reactions sometimes observed. When confronted with fatal or novel pathogens, people exhibit a variety of behaviors from anxiety to hoarding of medical supplies, overwhelming medical infrastructure and rioting. We developed a coupled network approach to understanding and predicting social response to disease spread. We couple the disease spread and panic spread processes and model them through local interactions between agents. The behavioral contagion process depends on the prevalence of the disease, its perceived risk and a global media signal. We verify the model by analyzing the spread of disease and social response during the 2009 H1N1 outbreak in Mexico City, the 2003 SARS and 2009 H1N1 outbreaks in Hong Kong and the 2012-2013 Boston influenza season, accurately predicting population-level behavior. The effect of interventions on the disease spread and social response is explored, and we implement an optimization study to determine the least cost intervention, taking into account the costs of the disease itself, the intervention and the social response. We show that the optimal strategy is dependent upon the relative costs assigned to infection with the disease, intervention and social response, as well as the perceived risk of infection. This kind of empirically validated model is critical to exploring strategies for public health intervention, increasing our ability to anticipate the response to infectious disease outbreaks. / by Shannon M. Fast. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2015. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 139-156). / Cancer is a leading cause of death both in the United States and worldwide. In this thesis we use machine learning and optimization to identify effective treatments for advanced cancers and to identify effective screening strategies for detecting early-stage disease. In Part I, we propose a methodology for designing combination drug therapies for advanced cancer, evaluating our approach using advanced gastric cancer. First, we build a database of 414 clinical trials testing chemotherapy regimens for this cancer, extracting information about patient demographics, study characteristics, chemotherapy regimens tested, and outcomes. We use this database to build statistical models to predict trial efficacy and toxicity outcomes. We propose models that use machine learning and optimization to suggest regimens to be tested in Phase II and III clinical trials, evaluating our suggestions with both simulated outcomes and the outcomes of clinical trials testing similar regimens. In Part II, we evaluate how well the methodology from Part I generalizes to advanced breast cancer. We build a database of 1,490 clinical trials testing drug therapies for breast cancer, train statistical models to predict trial efficacy and toxicity outcomes, and suggest combination drug therapies to be tested in Phase II and III studies. In this work we model differences in drug effects based on the receptor status of patients in a clinical trial, and we evaluate whether combining clinical trial databases of different cancers can improve clinical trial toxicity predictions. In Part III, we propose a methodology for decision making when multiple mathematical models have been proposed for a phenomenon of interest, using our approach to identify effective population screening strategies for prostate cancer. We implement three published mathematical models of prostate cancer screening strategy outcomes, using optimization to identify strategies that all models find to be effective. / by John Silberholz. / Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2017. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 175-185). / This thesis presents and evaluates methods for searching and analyzing social media data in order to improve situational awareness. We begin by proposing a method for network vertex search that looks for the target vertex by sequentially examining the neighbors of a set of "known" vertices. Using a dynamic programming approach, we show that there is always an optimal "block" search policy, in which all of the neighbors of a known vertex are examined before moving on to another vertex. We provide a precise characterization of the optimal policy in two specific cases: (1) when the connections between the known vertices and the target vertex are independent, and (2) when the target vertex is connected to at most one known vertex. We then apply this result to the problem of finding new accounts belonging to Twitter users whose previous accounts had been suspended for extremist activity, quantifying the performance of our optimal search policy in this application against other policies. In this application we use thousands of Twitter accounts related to the Islamic State in Iraq and Syria (ISIS) to develop a behavioral models for these extremist users. These models are used to identify new extremist accounts, identify pairs of accounts belonging to the same user, and predict to whom a user will connect when opening an account. We use this final model to inform our network search application. Finally, we develop a more general application of network search and classification that obtains a set of social media users from a specified location or group. We propose an expand -- classify methodology which recursively collects users that have social network connections to users inside the target location, and then classifies all of the users by maximizing the probability over a factor graph model. This factor graph model accounts for the implications of both observed user profile features and social network connections in inferring location. Using geo-located data to evaluate our method, we find that our classification method typically outperforms Twitter's native search methods in building a dataset of Twitter users in a specific location. / by Christopher E. Marks. / Ph. D.