Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 1999. / Includes bibliographical references (leaves 107-111). / We develop various algorithms for solving mixed integer-quadratic problems. These problems exhibit exponential complexity resulting from the presence of integer variables. Traditional approaches that apply in pure integer programming are not very helpful, since the existence of continuous variables in our problems complicates their use. Vie develop relaxation and heuristic algorithms designed so as to provide tight lower and upper bounds to the optimal solution of the mixed combinatorial problem. In some cases the obtained range, in which the optimum lies, is small enough to be considered satisfactory by itself. This has been accomplished in problems with up to 150 variables. Exact algorithms have also been developed and guarantee the optimal solution upon termination. The idea of Branch and Bound enhanced with the use of lower and upper bounds obtained with the aforementioned methods is implemented for that purpose. Problems with up to 70 variables have been solved. Our ideas and algorithms are applied to the Problem of Index and Portfolio Replication with a limited number of assets. This problem arises in Finance, but, in its more general form, can find application in various areas ranging from Statistics to Optimal Control and Manufacturing. / by Constantine Nikolaos Tziligakis. / S.M.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / 76 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 67-72). / In the event of a pandemic influenza outbreak, such as the 2009-2010 H1N1 "Swine Flu" episode, it is crucial to effectively allocate limited resources in order to minimize the casualties. Design of effective resource allocation strategies requires good understanding of the underlying contact network and of the propagation dynamics. In this thesis we develop a parameter estimation method that learns the network structure, among a family of graphs, and disease dynamics from the recorded infection curve, assuming that the disease dynamics follow an SIR process. We apply the method to data collected during the 2009-2010 H1N1 epidemic and show that the best-fit model, among a scale-free network and a small-world network, indicates the scale-free network. Given the knowledge of the network structure we evaluate different vaccination strategies. As a benchmark, we allow the vaccination decisions to depend on the state of the epidemic and we show that random vaccination (which is the current practice), does not efficiently halt the spread of influenza. Instead, we propose vaccine allocation strategies that exploit the underlying network structure and provide a reduction in the number of infections by over 6 times compared to the current practice. In addition, more realistic scenario involves random encounters between agents. To test this hypothesis, we introduced a dynamic network formation on top of the static network model. We apply the estimation method to the dynamic network model and show a small improvement in estimating the infection dynamics of the 2009-2010 H1N1 influenza. / by Louis Y. Kim. / S.M.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 203-208). / Planning and controlling production in a large make-to-order manufacturing network poses complex and costly operational problems. As customers continually submit customized orders, a centralized decision-maker must quickly allocate each order to production facilities with limited but flexible labor, production capacity, and parts availability. In collaboration with a major desktop manufacturing firm, we study these relatively unexplored problems, the firm's solutions to it, and alternate approaches based on mathematical optimization. We develop and analyze three distinct models for these problems which incorporate the firm's data, testing, and feedback, emphasizing realism and usability. The problem is cast as a Dynamic Program with a detailed model of demand uncertainty. Decisions include planning production over time, from a few hours to a quarter year, and determining the appropriate amount of labor at each factory. The objective is to minimize shipping and labor costs while providing superb customer service by producing orders on-time. Because the stochastic Dynamic Program is too difficult to solve directly, we propose deterministic, rolling-horizon, Mixed Integer Linear Programs, including one that uses recently developed affinely-adjustable Robust Optimization techniques, that can be solved in a few minutes. Simulations and a perfect hindsight upper bound show that they can be near-optimal. Consistent results indicate that these solutions offer several hundred thousand dollars in daily cost saving opportunities by accounting for future demand and repeatedly re-balancing factory loads via re-allocating orders, improving capacity utilization, and improving on-time delivery. / by Gareth Pierce Williams. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2012. / 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 (p. 151-154). / We propose a tractable optimization framework for network Air Traffic Flow Management (ATFM) with an eye towards the future. The thesis addresses two issues in ATFM research: a) fairness and collaboration amongst airlines; and b) uncertainty inherent in capacity forecasts. A unifying attraction of the overall dissertation is that the Collaborative Decision-Making (CDM) paradigm, which is the current philosophy governing the design of new ATFM initiatives, is treated as the starting point in the research agenda. In the first part of the thesis, we develop an optimization framework to extend the CDM paradigm from a single-airport to a network setting by incorporating both fairness and airline collaboration. We introduce different notions of fairness emanating from a) First-Scheduled First-Served (FSFS) fairness; and b) Proportional fairness. We propose exact discrete optimization models to incorporate them. The first fairness paradigm which entails controlling number of reversals and total amount of overtaking is especially appealing in the ATFM context as it is a natural extension of Ration-By-Schedule (RBS). We allow for further airline collaboration by proposing discrete optimization models for slot reallocation. We provide empirical results of the proposed optimization models on national-scale, real world datasets that show interesting tradeoffs between fairness and efficiency. In particular, schedules close to the RBS policy (with single digit reversals) are possible for a less than 10% increase in delay costs. We utilize case studies to highlight the considerable improvements in the internal objective functions of the airlines as a result of slot exchanges. Finally, the proposed models are computationally tractable (running times of less than 30 minutes). In the second part, we address the important issue of capacity uncertainty by presenting the first application of robust and adaptive optimization in the ATFM problem. We introduce a weather-front based approach to model the uncertainty inherent in airspace capacity estimates resulting from the impact of a small number of weather fronts. We prove the equivalence of the robust problem to a modified instance of the deterministic problem; solve the LP relaxation of the adaptive problem using affine policies; and report extensive empirical results to study the inherent tradeoffs. / by Shubham Gupta. / Ph.D.

Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2016. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 49-52). / The rapid growth of the availability of wearable biosensors has created the opportunity for using physiological signals to measure worker performance. An important question is how to use such signals to not just measure, but actually predict worker performance on a task under stressful and potentially high risk conditions. Here we show that the biological signal known as galvanic skin response (GSR) allows such a prediction. We conduct an experiment where subjects answer arithmetic questions under low and high stress conditions while having their GSR monitored. Using only the GSR measured under low stress conditions, we are able to predict which subjects will perform well under high stress conditions with a median accuracy of 75%. If we try to make similar predictions without using any biometric signals, the median accuracy is 50%. Our results suggest that performance in high stress conditions can be predicted using signals obtained from GSR sensors in low stress conditions. / by Lee Carter Mundell. / S.M.

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 233-241). / Motivated by applications in Revenue Management (RM), this thesis studies various problems in sequential decision-making and demand learning. In the first module, we consider a personalized RM setting, where items with limited inventories are recommended to heterogeneous customers sequentially visiting an e-commerce platform. We take the perspective of worst-case competitive ratio analysis, and aim to develop algorithms whose performance guarantees do not depend on the customer arrival process. We provide the first solution to this problem when there are both multiple items and multiple prices at which they could be sold, framing it as a general online resource allocation problem and developing a system of forecast-independent bid prices (Chapter 2). Second, we study a related assortment planning problem faced by Walmart Online Grocery, where before checkout, customers are recommended "add-on" items that are complementary to their current shopping cart (Chapter 3). Third, we derive inventory-dependent priceskimming policies for the single-leg RM problem, which extends existing competitive ratio results to non-independent demand (Chapter 4). In this module, we test our algorithms using a publicly-available data set from a major hotel chain. In the second module, we study bundling, which is the practice of selling different items together, and show how to learn and price using bundles. First, we introduce bundling as a new, alternate method for learning the price elasticities of items, which does not require any changing of prices; we validate our method on data from a large online retailer (Chapter 5). Second, we show how to sell bundles of goods profitably even when the goods have high production costs, and derive both distribution-dependent and distribution-free guarantees on the profitability (Chapter 6). In the final module, we study the Markovian multi-armed bandit problem under an undiscounted finite time horizon (Chapter 7). We improve existing approximation algorithms using LP rounding and random sampling techniques, which result in a (1/2 - eps)- approximation for the correlated stochastic knapsack problem that is tight relative to the LP. In this work, we introduce a framework for designing self-sampling algorithms, which is also used in our chronologically-later-to-appear work on add-on recommendation and single-leg RM. / by Will (Wei) Ma. / 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, 2006. / Includes bibliographical references (p. 155-164). / (cont.) We first address the complexity of finding an optimal minimum cost solution to a congestion game. We consider both network and general congestion games, and we examine several variants of the problem concerning the structure of the game and its associated cost functions. Many of the problem variants are NP-hard, though we do identify several versions of the games that are solvable in polynomial time. We then investigate existence and the price of anarchy of pure Nash equilibria in k-splittable congestion games with linear costs. A k-splittable congestion game is one in which each player may split its flow on at most k different paths. We identify conditions for the existence of equilibria by providing a series of potential functions. For the price of anarchy, we show an asymptotic lower bound of 2.4 for unweighted k-splittable congestion games and 2.401 for weighted k-splittable congestion games, and an upper bound of 2.618 in both cases. / In this thesis we examine four network flow problems arising in the study of transportation, communication, and water networks. The first of these problems is the Integer Equal Flow problem, a network flow variant in which some arcs are restricted to carry equal amounts of flow. Our main contribution is that this problem is not approximable within a factor of 2n(1-epsilon]), for any fixed [epsilon] > 0, where n is the number of nodes in the graph. We extend this result to a number of variants on the size and structure of the arc sets. We next study the Pup Matching problem, a truck routing problem where two commodities ('pups') traversing an arc together in the network incur the arc cost only once. We propose a tighter integer programming formulation for this problem, and we address practical problems that arise with implementing such integer programming solutions. Additionally, we provide approximation and exact algorithms for special cases of the problem where the number of pups is fixed or the total cost in the network is bounded. Our final two problems are on the topic of congestion games, which were introduced in the area of communications networks. / by Carol Meyers. / 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. / 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.