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.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2001. / Includes bibliographical references (p. 155-166). / A practical approach for solving computationally intractable problems is to employ heuristic (approximation) algorithms that can find nearly optimal solutions within a reasonable amount of computational time. An improvement algorithm is an approximation algorithm which starts with a feasible solution and iteratively attempts to obtain a better solution. Neighborhood search algorithms (alternatively called local search algorithms) are a wide class of improvement algorithms where at each iteration an improving solution is found by searching the "neighborhood" of the current solution. This thesis concentrates on neighborhood search algorithms where the size of the neighborhood is "very large" with respect to the size of the input data. For large problem instances, it is impractical to search these neighborhoods explicitly, and one must either search a small portion of the neighborhood or else develop efficient algorithms for searching the neighborhood-implicitly. This thesis consists of four parts. Part 1 is a survey of very large scale neighborhood (VLSN) search techniques for combinatorial optimization problems. In Part 2, we concentrate on a VLSN search technique based on compounding independent simple moves such as 2-opts, swaps, and insertions. We show that the search for an improving neighbor can be done by finding a negative cost path on an auxiliary graph. We show how this neighborhood is applied to problems such as the TSP, VRP, and specific single and multiple machine scheduling problems. / (cont.) In Part 3, we discuss dynamic programming approximations for the TSP and a generic set partitioning problem that are based on restricting the state space of the original dynamic programs. Furthermore, we show the equivalence of these restricted DPs to particular neighborhoods that we had considered earlier. Finally, in Part 4, we present the results of a computational study for the compounded independent moves algorithm on the vehicle routing problem with capacity and distance restrictions. These results indicate that our algorithm is competitive with respect to the current heuristics and branch and cut algorithms. / by Özlem Ergun. / Ph.D.

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 171-178). / This thesis discusses optimization problems and equilibrium in networks. There are three major parts of the thesis. In the first part, we discuss optimization in dynamic networks. We focus on two fundamental optimization problems in dynamic networks: the quickest flow problem and the quickest transshipment problem. The quickest flow problem is to find a minimum time needed to send a given amount of flow from one origin to one destination in a dynamic network. The quickest transshipment problem is similar to the quickest flow problem except with multiple origins and multiple destinations. We derive optimality conditions for the quickest flow problems and introduce simplified and more efficient algorithms for the quickest flow problems. For the quickest transshipment problem, we develop faster algorithms for several special cases and apply the approach to approximate an optimal solution more efficiently. In the second part, we discuss equilibrium in dynamic networks. We extend equilibrium results in static networks into dynamic networks and show that equilibria exist in a network where players either have the same origin or the same destination. We also introduce algorithms to compute such an equilibrium. Moreover, we analyze the average convergence speed of the best-response dynamics and connect equilibria in discrete network models to equilibria in continuous network models. In the third part, we introduce a new traffic information exchange system. The new system resolves the dilemma that broadcasting traffic predictions might affect drivers' behaviors and make the predictions inaccurate. We build game theoretic models to prove that drivers have incentives to use this system. In order to further test the effectiveness of such system, we run a series of behavioral experiments through an online traffic game. Experimental results show that drivers who use the system have a lower average travel time than the general public, and the system can help improve the average travel time of all drivers as the number of drivers who use this system increases. / by Maokai Lin. / Ph. D.