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.

Thesis: S.M., 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 53-55). / We present our work with a hotel company as an example of how machine learning techniques can be used to improve the demand predictions of a hotel property, as well as its pricing and capacity allocation decisions. First, we build a price-sensitive random forest model to predict the number of daily bookings for each customer market segment. We feed these predictions into a mixed integer linear program (MILP) to optimize prices and capacity allocations at the same time. We prove that the MILP can be equivalently solved as a linear program, and then show that it produces upper and lower bounds for the expected revenue maximization Dynamic Program (DP), and that the gap between the bounds depends on the probabilistic distribution of the demand. Thus, for high prediction accuracies, the optimal value of the DP can be closely approximated by the MILP solution. Finally, numerical results show that the optimized decisions are able to generate an increase in revenue compared to the historical policies, and that the fast running time achieved permits real time policy updates. / by Eduardo Candela Garza. / 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 283-293). / The growing availability of data is creating opportunities for making better decisions, but in many circumstances it is yet unknown how to correctly leverage this data in systematic and optimal ways. In this thesis, we investigate new modes of data-driven decision making, enabled by novel connections we uncover between optimization and statistics. We pursue fundamental theory, specific methodologies, and revealing applications that advance data analytics from a tool of understanding to a decision-making engine. In part I, we focus on the interface between predictive and prescriptive analytics. In the first half, we combine ideas from machine learning and operations research to prescribe optimal decisions given historical data and auxiliary, predictive observations. We develop theory on tractability, asymptotic optimality, and performance metrics and apply our methods to leverage large-scale web data to drive a real-world inventory-management system. In the second half, we study the problem of data-driven pricing and show that a naive but common predictive approach leaves money on the table whereas a theoretically-sound prescriptive approach we propose performs well in practice, demonstrated by a novel statistical test applied to data from a loan provider. In part II, we focus on the interface between statistical hypothesis testing and optimization under uncertainty. In the first half, we propose a novel method for data-driven stochastic optimization that combines finite-sample guarantees with larges ample convergence by leveraging new theory linking distributionally-robust optimization and statistical hypothesis testing. In the second half, we develop data-driven uncertainty sets for robust optimization and demonstrate that, when data is available, our sets outperform conventional sets when used in their place in existing applications of robust optimization. In part III, we focus on the interface between controlled experimentation and modern optimization. In the first half, we propose an optimization-based approach to constructing experimental groups with discrepancies in covariate data that are orders-of-magnitude smaller than any randomization-based approach. In the second half, we develop a unified theory of designs that balance covariate data and their optimality. We show no notion of balance exists without structure on outcomes' functional form, whereas with structure expressed using normed spaces, various existing designs emerge as optimal and new designs arise that prove successful in practice. / by Nathan Kallus. / Ph. D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 106). / The effective scheduling of fighter aircraft maintenance in the Air Force is crucial to overall mission accomplishment. An effective maintenance scheduling policy maximizes the use of maintenance resources and aircraft availability. Currently, maintenance scheduling is a time consuming process that is carried out by airmen whose sole responsibility is to manually generate a maintenance schedule that balances maintenance requirements and flying requirements. In this thesis, we seek to represent the maintenance scheduling process using a mathematical model that ultimately generates an optimal maintenance schedule. First, we address the scheduling of phase maintenance, the most significant preventative maintenance action, for fighter aircraft. We use a mixed integer program (MIP) to model the phase maintenance scheduling process. The MIP generates a daily maintenance and flying schedule that ensures that the maintenance workload is evenly distributed across the planning horizon. We find that the computational performance of the MIP formulation is less than desirable for large instances of real-world data. Motivated by the need for improved computational performance, we develop an alternative formulation that disaggregates the original MIP into two subproblems that are solved sequentially. The two-stage formulation of the phase maintenance scheduling problem has significantly better computational performance while generating a feasible daily maintenance and flying schedule. We then address the maintenance scheduling process that is unique to aircraft with low-observable (LO) capabilities. The LO capabilities of an aircraft degrade over time according to a stochastic process and require continuous maintenance attention. We show that the characteristics of the LO maintenance process allow it to be modeled as a variant of the mulitarmed bandit (MAB) problem. We then present a variant of the heuristic proposed by Whittle that has been shown to provide near optimal solutions for MAB problems. Applying Whittle's heuristic to the LO maintenance scheduling problem, we generate a simple index policy that can be used to schedule aircraft for LO maintenance. We then compare the index policy to alternate policies and show by simulation that the index policy leads to relatively better fully mission capable (FMC) rates, a common measure of overall fleet health. / by Philip Y Cho. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2009. / 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. 91). / This research seeks to address potential "passenger-centric" modifications to the way that ground holding delays are allocated in Ground Delay Programs. The allocation of landing slots to arriving flights during time periods when the overall capacity at an airport is reduced due to adverse weather conditions or other circumstances is a well-studied problem in Air Traffic Flow Management, but not from the passenger's perspective. We propose a Passenger-Centric Ground Holding (PCGH) model, which considers both the number of passengers on flights and, notably, when/if they are making connections. In experimental results, PCGH is shown to lead to slot allocations which are significantly different from those in the currently-used first scheduled, first served (FSFS) approach. A systematic analysis is conducted to determine the impact of PCGH on a variety of airport and airline types. Finally, the effects of a maximum-delay-limiting constraint and the convexity of the cost function are investigated. / by Mallory Jo Soldner. / S.M.

Thesis (S.M.)--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. 152-153). / This thesis considers approaches to influencing population opinions during counterinsurgency efforts in Afghanistan. A discrete time, agent-based threshold model is developed to analyze the propagation of beliefs in the social network, whereby each agent has a belief and a threshold value, which indicts the willingness to be influenced by the peers. Agents communicate in stochastic pairwise interactions with their neighbors. A dynamic, two player game is formulated whereby each player strategically controls the placement of one stubborn agent over time in order to maximally influence the network according to one of two different payoff functions. The stubborn agents have opposite, immutable beliefs and exert significant influence in the network. We demonstrate the characteristics of strategies chosen by the players to improve their payoffs through simulation. Determining strategies for the players in large, complex networks in which each stubborn agent has multiple connections is difficult due to exponential increases in the strategy space that is searched. We implement two heuristic methods which are shown to significantly reduce the run time needed to find strategies without significantly reducing the quality of the strategies. Lastly, we introduce population-focused actions, such as economic stimulus projects, which when used by the players result in long-lasting changes in the beliefs of the agents in the network. / by Matthew E. Bradwick. / S.M.

Includes bibliographical references (p. 167-176). / Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / (cont.) In the second part of the thesis, we focus on the design and analysis of simple, possibly non-coordinating contracts in a single-supplier, multi-retailer supply chain where retailers make both pricing and inventory decisions. Specifically, we introduce a buy-back menu contract to improve supply chain efficiency, and compare two systems, one in which the retailers compete against each other, and another in which the retailers coordinate their decisions to maximize total expected retailer profit. In a linear additive demand setting, we show that for either retailer configuration, the proposed buy-back menu guarantees the supplier, and hence the supply chain, at least 50% of the optimal global supply chain profit. In particular, in a coordinated retailers system, the contract guarantees the supply chain at least 75% of the optimal global supply chain profit. We also analyze the impact of retail price caps on supply chain performance in this setting. / In this thesis, we study important facets of two problems in methodological and applied operations research. In the first part of the thesis, motivated by optimization problems that arise in the context of Internet advertising, we explore the performance of the greedy algorithm in solving submodular set function maximization problems over various constraint structures. Most classic results about the greedy algorithm assume the existence of an optimal polynomial-time incremental oracle that identifies in any iteration, an element of maximum incremental value to the solution at hand. In the presence of only an approximate incremental oracle, we generalize the performance bounds of the greedy algorithm in maximizing nondecreasing submodular functions over special classes of matroids and independence systems. Subsequently, we unify and improve on various results in the literature for problems that are specific instances of maximizing nondecreasing submodular functions in the presence of an approximate incremental oracle. We also propose a randomized algorithm that improves upon the previous best-known 2-approximation result for the problem of maximizing a submodular function over a partition matroid. / by Pranava Raja Goundan. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 89-90). / by Loren M. Werner. / S.M.