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. / What is the right price to charge your customers? Many retailers and researchers are facing this question. In the last three decades, tremendous progress was made, both in the academic and business worlds. In this thesis, we investigate four novel pricing applications. In the first part, we study the promotion optimization problem for supermarket retailers. One needs to decide which products to promote, the depth of price discounts and when to schedule the promotions. To capture the stockpiling behavior of consumers, we propose two general classes of demand functions that can be easily estimated from data. We then develop an approximation that allows us to solve the problem efficiently and derive analytical results on its accuracy. The second part is motivated by the ubiquity of social networking platforms. We consider a setting where a monopolist sells an indivisible good to consumers embedded in a social network. First, the firm designs prices to maximize its profits. Subsequently, consumers choose whether to purchase the item or not. Assuming positive externalities, we show the existence of a pure Nash equilibrium. Using duality theory and integer programming techniques, we reformulate the problem into a linear mixed-integer program. We then derive efficient ways of optimally solving the problem for discriminative and uniform pricing strategies. The third part considers the problem of pricing a product for which demand information is very limited. We impose minimal assumptions on the problem: that is, only the constant marginal cost and the maximal price the firm can set are known. We propose a simple way of pricing the product by approximating the true inverse demand by a linear function. Surprisingly, we show that this approximation yields a good profit performance for a wide range of demand curves. In the final part, we consider green technology products such as electric vehicles. We propose a Stackelberg model where the government offers consumer subsidies in order to encourage the technology adoption, whereas the supplier decides price and production to maximize profits. We address the question: How does demand uncertainty affect the government, the industry and the consumers, when designing policies. / by Maxime C. Cohen. / Ph. D.

Thesis (Ph. D.)--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. 137-140). / This thesis studies the learning problem of a set of agents connected via a general social network. We address the question of how dispersed information spreads in social networks and whether the information is efficiently aggregated in large societies. The models developed in this thesis allow us to study the learning behavior of rational agents embedded in complex networks. We analyze the perfect Bayesian equilibrium of a dynamic game where each agent sequentially receives a signal about an underlying state of the world, observes the past actions of a stochastically-generated neighborhood of individuals, and chooses one of two possible actions. The stochastic process generating the neighborhoods defines the network topology (social network). We characterize equilibria for arbitrary stochastic and deterministic social networks and characterize the conditions under which there will be asymptotic learning -- that is, the conditions under which, as the social network becomes large, the decisions of the individuals converge (in probability) to the right action. We show that when private beliefs are unbounded (meaning that the implied likelihood ratios are unbounded), there will be asymptotic learning as long as there is some minimal amount of expansion in observations. This result therefore establishes that, with unbounded private beliefs, there will be asymptotic learning in almost all reasonable social networks. Furthermore, we provide bounds on the speed of learning for some common network topologies. We also analyze when learning occurs when the private beliefs are bounded. / (cont.) We show that asymptotic learning does not occur in many classes of network topologies, but, surprisingly, it happens in a family of stochastic networks that has infinitely many agents observing the actions of neighbors that are not sufficiently persuasive. Finally, we characterize equilibria in a generalized environment with heterogeneity of preferences and show that, contrary to a nave intuition, greater diversity (heterogeneity) 3 facilitates asymptotic learning when agents observe the full history of past actions. In contrast, we show that heterogeneity of preferences hinders information aggregation when each agent observes only the action of a single neighbor. / by Ilan Lobel. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2004. / Includes bibliographical references (p. 103-107). / In the first part of the thesis we combine ideas from cutting plane and interior point methods to solve variational inequality problems efficiently. In particular, we introduce "smarter" cuts into two general methods for solving these problems. These cuts utilize second order information on the problem through the use of a gap function. We establish convergence results for both methods, as well as complexity results for one of the methods. Finally, we compare the performance of an approach that combines affine scaling and cutting plane methods with other methods for solving variational inequalities. The second part of the thesis considers a supply chain setting where several capacitated suppliers compete for orders from a single retailer in a multi-period environment. At each period the retailer places orders to the suppliers in response to the prices and capacities they announce. Our model allows the retailer to carry inventory. Furthermore, suppliers can expand their capacity at an additional cost; the retailer faces exogenous, price-dependent, stochastic demand. We analyze discrete as well as continuous time versions of the model: (i) we illustrate the existence of equilibrium policies; (ii) we characterize the structure of these policies; (iii) we consider coordination mechanisms; and (iv) we present some computational results. We also consider a modified model that uses option contracts and finally present some extensions. / by Marina Zaretsky. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2002. / Includes bibliographical references (p. 137-141). / An important issue in real-world optimization problems is how to treat uncertain coefficients. Robust optimization is a modeling methodology that takes a deterministic view: the optimal solution is required to remain feasible for any realization of the uncertain coefficients within prescribed uncertainty sets. The focus of this thesis is on robust linear programming problems in which the uncertainty sets are polytopes. The assumption of polyhedral uncertainty leads to compact, efficiently solvable linear formulations. In the first part of the thesis, we study special types of polyhedral uncertainty sets that allow for incorporating moment information about the distribution of the uncertain coefficients, and for controlling the tradeoff between robustness and optimality. We provide probabilistic guarantees on the feasibility of optimal solutions obtained with such uncertainty sets for any realization of the uncertain coefficients. We then illustrate the versatility of robust polyhedral formulations by studying three financial applications: single period portfolio optimization, multiperiod portfolio management, and credit risk estimation. In the area of single period portfolio optimization, we propose ways of modeling inaccuracy in parameter estimates, and explore the benefits of robust optimal strategies through computational experiments with the statistical estimation of a particular measure of portfolio risk - sample shortfall. We emphasize the advantages of linear, as opposed to nonlinear, robust formulations in large portfolio problems with integrality constraints. / (cont.) In the area of multiperiod portfolio management, we propose robust polyhedral formulations that use some minimal information about long-term direction of movement of asset returns to make informed decisions about portfolio rebalancing over the short term. The suggested formulations allow for including considerations of transaction costs and taxes while keeping the dimension of the problem low. In the area of credit risk estimation, we propose a model for estimating the survival probability distribution and the fair prices of credit risky bonds from market prices of similar credit risky securities. We address the issue of uncertainty in key parameters of the model, such as discount factors, by using robust optimization modeling. We also suggest a method for classification of credit risky bonds based on integer programming techniques. / by Dessislava A. Pachamanova. / Ph.D.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2000. / Includes bibliographical references (p. 81-82). / This thesis explores the benefits of increasing communication and collaboration between airlines and air traffic controllers during the arrival process at hub airports. In particular, this study estimates operational improvements, measured in passenger minutes of delay saved, from providing airlines with more accurate landing time estimates and from allowing airlines to influence the sequence of incoming traffic. To estimate these potential benefits, the Airline Sequencing model was developed to simulate airline decisions regarding ground operations. The model has been calibrated and validated to reflect airline decision making. Scenario analyses were conducted using the model to estimate the delay savings that an airline could realize through the use of more accurate landing time estimates although the potential ability to influence the sequence of arriving traffic. The current results indicate that. increased communication and collaboration could significantly decrease delays. Over a time horizon of 3.25 hours, a decrease in the standard deviation in landing time estimate errors of two minutes could prevent between 500 and 2000 passenger minutes of delay. Allowing an airline to shift each arriving aircraft's landing time up to 5 minutes can save between 4000 and 7000 passenger minutes of delay over a time period of 3.25 hours. The potential savings depend on the delay conditions of the time horizon considered in the model. These results indicate that the potential reduction in delay could be significant. Further investigation into the feasibility of the communication and collaboration suggested in this thesis is warranted. / by Kari Andersson. / S.M.

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 165-170). / There are many benefits of owning a battery electric vehicle, including zero tailpipe emissions, potential independence from oil, lower fuel costs, and the option to recharge the battery at home. However, a significant concern about owning a battery electric vehicle is range anxiety: the fear that the battery will run out of charge before the driver reaches his or her destination. We address range anxiety by providing a robust optimization framework to give drivers confidence that they can reach their destinations in a reasonable amount of time with enough energy in the battery, even when there is uncertainty in travel time and energy consumption on the roads. The robust optimization appropriately incorporates uncertainty without significantly increasing the complexity of the problem. This thesis describes that optimization framework and how to use it on real-world examples to find appropriate routes, with a central part being the application of robust optimization to the problem. We develop an energy model, an optimization-based formulation using robust optimization, and algorithms to quickly find good routes for battery electric vehicles. The combination of using robust optimization, the A-Star algorithm to find shortest paths, and Lagrangian relaxation allows us to solve the problem in seconds or less. For one example start and destination, our algorithms required less than 2 seconds for each instance (energy consumption limit). In addition, for example trips, we compute a Pareto frontier to illustrate the time-energy tradeoff from driving different routes. We use Lagrangian relaxation to provide lower bounds and estimates that suggest that our algorithms produce near-optimal solutions. We apply our methodology to example trips in Massachusetts and Michigan to demonstrate its practicality and its potential for real-world use. Future work could continue to improve the modeling accuracy and include algorithmic enhancements to further improve running time, especially for larger networks. / by Matthew William Fontana. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / 117 / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 173-180). / The last decade has seen an explosion in the availability of data. In this thesis, we propose new techniques to leverage these data to tractably model uncertainty and behavior. Specifically, this thesis consists of three parts: In the first part, we propose a novel schema for utilizing data to design uncertainty sets for robust optimization using hypothesis testing. The approach is flexible and widely applicable, and robust optimization problems built from our new data driven sets are computationally tractable, both theoretically and practically. Optimal solutions to these problems enjoy a strong, finite-sample probabilistic guarantee. Computational evidence from classical applications of robust optimization { queuing and portfolio management { confirm that our new data-driven sets significantly outperform traditional robust optimization techniques whenever data is available. In the second part, we examine in detail an application of the above technique to the unit commitment problem. Unit commitment is a large-scale, multistage optimization problem under uncertainty that is critical to power system operations. Using real data from the New England market, we illustrate how our proposed data-driven uncertainty sets can be used to build high-fidelity models of the demand for electricity, and that the resulting large-scale, mixed-integer adaptive optimization problems can be solved efficiently. With respect to this second contribution, we propose new data-driven solution techniques for this class of problems inspired by ideas from machine learning. Extensive historical back-testing confirms that our proposed approach generates high quality solutions that compare with state-of-the-art methods. In the third part, we focus on behavioral modeling. Utility maximization (single agent case) and equilibrium modeling (multi-agent case) are by far the most common behavioral models in operations research. By combining ideas from inverse optimization with the theory of variational inequalities, we develop an efficient, data-driven technique for estimating the primitives of these models. Our approach supports both parametric and nonparametric estimation through kernel learning. We prove that our estimators enjoy a strong generalization guarantee even when the model is misspecified. Finally, we present computational evidence from applications in economics and transportation science illustrating the effectiveness of our approach and its scalability to large-scale instances. / by Vishal Gupta. / 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 137-142). / In this thesis, we design and analyze algorithms for robust combinatorial optimization in various settings. First, we consider the problem of simultaneously maximizing multiple objectives, all monotone submodular, subject to a cardinality constraint. We focus on the case where the number of objectives is super-constant yet much smaller than the cardinality of the chosen set. We propose several algorithms (including one with the best achievable asymptotic guarantee for the problem). Experiments on synthetic data show that a heuristic based on our more practical and fast algorithm outperforms current practical algorithms in all cases considered. Next, we study the problem of robust maximization of a single monotone submodular function in scenarios where after choosing a feasible set of elements, some elements from the chosen set are adversarially removed. Under some restriction on the number of elements that can be removed, we give the first constant factor approximation algorithms as well as the best possible asymptotic approximation in certain cases. We also give a black box result for the much more general setting of deletion-robust maximization subject to an independence system. Lastly, we consider a robust appointment scheduling problem where the goal is to design simple appointment systems that try to achieve both high server utilization as well as short waiting times, under uncertainty in job processing times. When the order of jobs is fixed and one seeks to find optimal appointment duration for jobs, we give a simple heuristic that achieves the first constant factor (2) approximation. We also give closed form optimal solutions in various special cases that supersede previous work. For the setting where order of jobs is also flexible and under-utilization costs are homogeneous, it was previously shown that an EPTAS exists. We instead focus on simple and practical heuristics, and find a ratio based ordering which is 1.0604 approximate, improving on previous results for similarly practical heuristics. / by Rajan Udwani. / 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 59-60). / In this thesis, I design and implement a novel method of schedule and path selection between predetermined waypoints for unmanned underwater vehicles under uncertainty. The problem is first formulated as a mixed-integer optimization model and subsequently uncertainty is addressed using a robust optimization approach. Solutions were tested through simulation and computational results are presented which indicate that the robust approach handles larger problems than could previously be solved in a reasonable running time while preserving a high level of robustness. This thesis demonstrates that the robust methods presented can solve realistic-sized problems in reasonable runtimes - a median of ten minutes and a mean of thirty minutes for 32 tasks - and that the methods perform well both in terms of expected reward and robustness to disturbances in the environment. The latter two results are obtained by simulating solutions given by the deterministic method, a naive robust method, and finally the two restricted affine robust policies. The two restricted affine policies consistently show an expected reward of nearly 100%, while the deterministic and naive robust methods achieve approximately 50% of maximum reward possible. / by Emily Anne Frost. / S.M.

Thesis: Ph. D., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2014. / 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-257). / This thesis considers problems in two areas in the healthcare operations: Kidney Paired Donation (KPD) and scheduling medical residents in hospitals. In both areas, we explore the implications of policy change through high fidelity simulations. We then build stochastic models to provide strategic insight into how policy decisions affect the operations of these healthcare systems. KPD programs enable patients with living but incompatible donors (referred to as patient-donor pairs) to exchange kidneys with other such pairs in a centrally organized clearing house. Exchanges involving two or more pairs are performed by arranging the pairs in a cycle, where the donor from each pair gives to the patient from the next pair. Alternatively, a so called altruistic donor can be used to initiate a chain of transplants through many pairs, ending on a patient without a willing donor. In recent years, the use of chains has become pervasive in KPD, with chains now accounting for the majority of KPD transplants performed in the United States. A major focus of our work is to understand why long chains have become the dominant method of exchange in KPD, and how to best integrate their use into exchange programs. In particular, we are interested in policies that KPD programs use to determine which exchanges to perform, which we refer to as matching policies. First, we devise a new algorithm using integer programming to maximize the number of transplants performed on a fixed pool of patients, demonstrating that matching policies which must solve this problem are implementable. Second, we evaluate the long run implications of various matching policies, both through high fidelity simulations and analytic models. Most importantly, we find that: (1) using long chains results in more transplants and reduced waiting time, and (2) the policy of maximizing the number of transplants performed each day is as good as any batching policy. Our theoretical results are based on introducing a novel model of a dynamically evolving random graph. The analysis of this model uses classical techniques from Erdos-Renyi random graph theory as well as tools from queueing theory including Lyapunov functions and Little's Law. In the second half of this thesis, we consider the problem of how hospitals should design schedules for their medical residents. These schedules must have capacity to treat all incoming patients, provide quality care, and comply with regulations restricting shift lengths. In 2011, the Accreditation Council for Graduate Medical Education (ACGME) instituted a new set of regulations on duty hours that restrict shift lengths for medical residents. We consider two operational questions for hospitals in light of these new regulations: will there be sufficient staff to admit all incoming patients, and how will the continuity of patient care be affected, particularly in a first day of a patients hospital stay, when such continuity is critical? To address these questions, we built a discrete event simulation tool using historical data from a major academic hospital, and compared several policies relying on both long and short shifts. The simulation tool was used to inform staffing level decisions at the hospital, which was transitioning away from long shifts. Use of the tool led to the following strategic insights. We found that schedules based on shorter more frequent shifts actually led to a larger admitting capacity. At the same time, such schedules generally reduce the continuity of care by most metrics when the departments operate at normal loads. However, in departments which operate at the critical capacity regime, we found that even the continuity of care improved in some metrics for schedules based on shorter shifts, due to a reduction in the use of overtime doctors. We develop an analytically tractable queueing model to capture these insights. The analysis of this model requires analyzing the steady-state behavior of the fluid limit of a queueing system, and proving a so called "interchange of limits" result. / by Ross Michael Anderson. / Ph. D.