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. 151-157). / The electricity industry has been experiencing fundamental changes over the past decade. Two of the arguably most significant driving forces are the integration of renewable energy resources into the electric power system and the creation of the deregulated electricity markets. Many new challenges arise. In this thesis, we focus on two important ones: How to reliably operate the power system under high penetration of intermittent and uncertain renewable resources and uncertain demand: and how to design an electricity market that considers both efficiency and fairness. We present some new advances in these directions. In the first part of the thesis, we focus on the first issue in the context of the unit commitment (UC) problem, one of the most critical daily operations of an electric power system. Unit commitment in large scale power systems faces new challenges of increasing uncertainty from both generation and load. We propose an adaptive robust model for the security constrained unit commitment problem in the presence of nodal net load uncertainty. We develop a practical solution methodology based on a combination of Benders decomposition type algorithm and outer approximation techniques. We present an extensive numerical study on the real-world large scale power system operated by the ISO New England (ISO-NE). Computational results demonstrate the advantages of the robust model over the traditional reserve adjustment approach in terms of economic efficiency, operational reliability, and robustness to uncertain distributions. In the second part of the thesis, we are concerned with a geometric characterization of the performance of adaptive robust solutions in a multi-stage stochastic optimization problem. We study the notion of finite adaptability in a general setting of multi-stage stochastic and adaptive optimization. We show a significant role that geometric properties of uncertainty sets, such as symmetry, play in determining the power of robust and finitely adaptable solutions. We show that a class of finitely adaptable solutions is a good approximation for both the multi-stage stochastic as well as the adaptive optimization problem. To the best of our knowledge, these are the first approximation results for multi-stage problems in such generality. Moreover, the results and the proof techniques are quite general and extend to include important constraints such as integrality and linear conic constraints. In the third part of the thesis, we focus on how to design an auction and pricing scheme for the day-ahead electricity market that achieves both economic efficiency and fairness. The work is motivated by two outstanding problems in the current practice - the uplift problem and equitable selection problem. The uplift problem is that the electricity payment determined by the electricity price cannot fully recover the production cost (especially the fixed cost) of some committed generators, and therefore the ISOs make side payments to such generators to make up the loss. The equitable selection problem is how to achieve fairness and integrity of the day-ahead auction in choosing from multiple (near) optimal solutions. We offer a new perspective and propose a family of fairness based auction and pricing schemes that resolve these two problems. We present numerical test result using ISO-NE's day-ahead market data. The proposed auction- pricing schemes produce a frontier plot of efficiency versus fairness, which can be used as a vaulable decision tool for the system operation. / by Xu Andy Sun. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2011. / 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. 101-107). / This thesis presents efficient algorithms that give optimal or near-optimal solutions for problems with non-linear objective functions that arise in discrete, continuous and robust optimization. First, we present a general framework for designing approximation schemes for combinatorial optimization problems in which the objective function is a combination of more than one function. Examples of such problems include those in which the objective function is a product or ratio of two or more linear functions, parallel machine scheduling problems with the makespan objective, robust versions of weighted multi-objective optimization problems, and assortment optimization problems with logit choice models. For many of these problems, we give the first fully polynomial time approximation scheme using our framework. Next, we present approximation schemes for optimizing a rather general class of non-linear functions of low rank over a polytope. In contrast to existing results in the literature, our approximation scheme does not require the assumption of quasi-concavity of the objective function. For the special case of minimizing a quasi-concave function of low-rank, we give an alternative algorithm which always returns a solution which is an extreme point of the polytope. This algorithm can also be used for combinatorial optimization problems where the objective is to minimize a quasi-concave function of low rank. We also give complexity-theoretic results with regards to the inapproximability of minimizing a concave function over a polytope. Finally, we consider the problem of appointment scheduling in a robust optimization framework. The appointment scheduling problem arises in many service operations, for example health care. For each job, we are given its minimum and maximum possible execution times. The objective is to find an appointment schedule for which the cost in the worst case scenario of the realization of the processing times of the jobs is minimized. We present a global balancing heuristic, which gives an easy to compute closed form optimal schedule when the underage costs of the jobs are non-decreasing. In addition, for the case where we have the flexibility of changing the order of execution of the jobs, we give simple heuristics to find a near-optimal sequence of the jobs. / by Shashi Mittal. / Ph.D.

Thesis: S.M., 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 109-111). / In this thesis, we explore wire routing strategies for new paradigms in chip design. Where current chip design techniques involve multi-layered techniques to prevent wire crossings and electrical interference, we work with new technology that utilizes coaxial wires, allowing the construction of single-layered chips. Though the single layer lends itself well to optimization techniques, this approach generates novel challenges of its own. We design and implement multiple global routing algorithms appropriate for the new technology, and we discuss how these algorithms address technical constraints introduced by dierent variations of the routing problem. We cover three approaches using dierent techniques; these include simulated annealing, local heuristics, and global mixed-integer optimization. We demonstrate the performance of these algorithms on physical chip designs and existing layouts, including metrics of total wire length, overall routability, and running time. We also discuss our process of algorithm design, specically in context of satisfying engineering requirements decided by an external technical team. Finally, we describe our ideas for future areas of research, tailored towards improvement of our approaches and addressing technical problems that will be introduced as the new technology develops. / by Austin Donald Herrling. / S.M.

Thesis (S.M.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2010. / Cataloged from PDF version of thesis. / Includes bibliographical references (p. 135-143). / Poor management of the patient flow in intensive care units (ICUs) causes service rejections and presents significant challenges from the standpoint of capacity planning and management in ICUs. This thesis reports on the development of a simulation framework to study admission control polices that aim to decrease the rejection rate in the ICU at Children's Hospital Boston (CHB), and to provide predictions for the future state of the ICU system. To understand the patient flow process, we extensively analyze the arrival and length of stay (LOS) data from the ICU census. The simulation model for the ICU is developed based on the results from this statistical analysis as well as the currently-practiced scheduling and admission policies of the ICU at CHB. The model is validated to provide accurate estimates for important performance metrics such as rejection rates in the ICU. The simulation model is used to study the performance of many admission control policies. The policies of our interest exploit "caps" to control the number of scheduled patients who are allowed to enter the ICU on a single day. In particular, we consider two cap-based policies: the uniform cap policy (UCP), which is the existing policy in CHB, and the service-specific cap policy (SSCP), which is originally proposed in this thesis. While the UCP implements caps on the total census of surgical patients, the SSCP utilizes the service-oriented heterogeneity of surgical patients' LOS and enforces caps on separate groups of surgical patients based on their average LOS. We show that the UCP can reduce the rejection rate in the ICU at the expense of extra waiting time of scheduled patients. The SSCP is shown to further decrease the rejection rate while increasing the waiting time compared to the UCP. We also demonstrate that the performance of both policies depends on the level of system utilization. In order to validate our results theoretically, a discrete-time queueing model for the ICU is developed and verified to provide estimates for performance measures that are consistent with the results from simulation. Finally, we introduce the notion of state-dependent prediction, which aims to identify the likelihood of the future state of the ICU conditional on the information of a current state. Several experiments are conducted by simulation to study the impact of a current state on a state in the future. According to our results, current state information can be useful in predicting the state of the ICU in the near future, but its impact gradually diminishes as the time difference between the present and future grows. Our major finding is that the probability of unit saturation at a certain future time can be determined almost entirely by the number of current patients who will leave the ICU after that time, regardless of the total number of patients who are currently staying in the unit. These results imply the potential development of adaptive cap-based policies that dynamically adjust caps according to the outcomes of state-dependent predictions. / by Wongsakorn Chaiwanon. / S.M.

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 187-191). / Online retail has grown rapidly in the last decade. Consumers enjoy the convenience of online shopping and home delivery, as well as a vast product assortment. From the business perspective, serving customers directly from warehouses reduces investment needed in physical storefronts. In this thesis, we consider operations management problems that are important to the effective and efficient operations in the warehouse of a large online retailer. We first consider the decision of stocking inventory in the warehouse, for products in the long tail of the online retail assortment. Motivated by real world business practice, we assume the underlying demand distribution is a mixture of known distributions, but with unknown weights. We propose a robust optimization model to decide on inventory levels given a few samples of demand, outperforming standard robust optimization methods in the relevant settings. The next two models are motivated by our collaboration with a large online retailer that operates multiple warehouses. We study a setting in which a warehouse has to fulfill a sequence of orders, each including multiple items. Pickers pick items in batches, and partially completed orders take up space on a sorting area called the wall. This gives rise to a fundamental tradeoff between picking efficiency and sorting efficiency. We propose a batch scheduling model, generalizing existing models by allowing for more general batch processing time functions, as well as incorporating an objective related to multi-item orders. We show hardness results, and propose both approximation algorithms and Integer Programming formulations. Finally, we build a simulation of the warehouse picking process, using data from a large online retailer. We propose a picking policy that better balances the tradeoff between picking and sorting efficiency, achieving a 42% decrease in average wall utilization and a 60% decrease in average order cycle time. We propose a model allowing us to analyze the tradeoffs between two heuristic policies representing the current policy and our proposed policy, and characterize a condition under which our proposed policy makes a small sacrifice in picking efficiency in return for a larger increase in sorting efficiency. This explains the empirical success of our policy. / by Chongli Daniel Chen. / Ph. D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2000. / Includes bibliographical references (leaves 103-112). / This thesis describes two applications of Operations Research to the field of industrial procurement, addressing problems encountered in supplier selection and supplier control, respectively. The first part addresses the problem of designing multi-item procurement auctions in capacity-constrained environments. Using insights from classical auction theory, we construct an optimization based auction mechanism ("Smart Market") relying on the dynamic resolution of a linear program minimizing the buyer's cost under the suppliers' capacity constraints. Based on the optimal allocation corresponding to each set of bids, suppliers can respond by modifying their offers, giving rise to a dynamic competitive bidding process. A first contribution of our work is the solution we develop to assist suppliers, a bidding suggestion device based on a myopic best response (MBR) calculation solving an inverse optimization problem. The second main contribution is the analytical study of the bid profile sequences arising in this smart market within a game-theoretic framework assuming linear costs for the suppliers. Under a particularly weak behavioral assumption and some symmetry requirements, we establish an explicit upper bound for the winning bids when the auction terminates as a function of the market environment parameters. This bound constitutes a performance guarantee from the buyer's perspective, and provides insights on how capacity constraints affect relative market power. We then formulate a complete behavioral model and solution methodology based on the MBR rationale and the concept of local Nash Equilibrium, and argue its realism. We derive analytically some structural and convergence properties of the MBR dynamics in the simplest non-trivial market environment, suggesting further possible design improvements, and obtain insights on market behavior, efficiency and incentive compatibility issues through numerical simulations. In particular, experiments tend to show that suppliers might be relied upon to provide their own capacity information when procurement contracts are properly designed. The second part is motivated by a strategic challenge faced in particular by electronic goods manufacturing companies. Because most of their assembly operations are highly automated, procurement delays typically account for most of the total production lead-time, and have a major impact on inventory costs. However, in an increasingly global outsourcing environment, these delays can be both long and uncertain. This leads us to examine the problem of optimally procuring components in a single-product stochastic assembly system. We consider a model where product demand follows a stationary Poisson process, assembly is instantaneous, and unsatisfied demand is backordered. The suppliers are uncapacitated and the components have independent but non-identically distributed stochastic procurement delays. The following class of policies is considered: The finished goods inventory is initially filled to its base stock level, and each customer order triggers a replenishment order for a component after a component-dependent postponement lead time. The objective is to minimize the sum of holding and backorder costs in steady-state over this class of replenishment policies. To keep the analysis tractable, we assume that no mixing occurs between component orders (synchronization assumption). Combining classical queueing network theory with original results concerning a distributional property we call closure under maximization and translation (CMT), we obtain a near-optimal solution in closed-form. We then demonstrate through simulation, using industrial data from a Hewlett-Packard facility, that the policy we derived significantly outperforms other policies commonly used in practice. In addition, we show that it is quite robust with respect to various model assumptions, except the synchronization one. We thus conclude that this work is potentially amenable to implementation in the settings where this assumption is not exceedingly demanding. Moreover, we believe that the CMT distributions we introduce could also prove useful in a variety of applications beyond the context of supply chains, such as project management, reliability analysis, and the study of natural extreme phenomena. / by Jérémie Gallien. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics; and, (Ph.D.)--Massachusetts Institute of Technology, Operations Research Center, 1999. / Includes bibliographical references (p. 144-151). / The unifying contribution of this thesis is to show that optimization is a very powerful tool that provides unexpected insights and impact on a variety of domains, such as probability, finance and revenue management. The thesis has two parts: In the first part, we use optimization models and techniques to derive optimal bounds for moment type problems in probability and finance. In the probability framework , we derive optimal inequalities for P(X E S), for a multivariate random variable X that has a given collection of moments, and an arbitrary set S. We provide a complete characterization of the problem of finding optimal bounds, from a complexity standpoint. We propose an efficient algorithm to compute tight bounds when S is a union of a polynomial number of convex sets, and up to second order moments of X are known. We show that it is NP-hard to obtain such bounds if the domain of X is Rn+, or if moments of third or higher order are given. Using convex optimization methods, we prove explicit tight bounds that generalize the classical Markov and Chebyshev inequalities, when the set S is convex. We examine implications to the law of large numbers, and the central limit theorem. In the finance framework, we investigate the applicability of such moment methods to obtain optimal bounds on financial quantities, when information about related instruments is available. We investigate the relation of option and stock prices just based on the no-arbitrage assumption, without assuming any model for the underlying price dynamics. We introduce convex optimization methods, duality and complexity theory to shed new light to this relation. We propose efficient algorithms for finding best possible bounds on option prices on multiple assets, based on the mean and variance of the underlying asset prices and their correlations and identify cases under which the derivation of such bounds is NP-hard. Conversely, given observable option prices, we provide best possible bounds on the moments of the underlying assets as well as prices of other options on the same asset. Our methods naturally extend for the case of transactions costs. The second part of this thesis applies dynamic and linear optimization methods to network revenue management applications. We investigate dynamic policies for allocating inventory to correlated, stochastic demand for multiple classes, in a network environment so as to maximize total expected revenues. We design a new efficient algorithm, based on approximate dynamic programming that provides structural insights into the optimal policy by using adaptive, non-additive bid-prices from a linear programming relaxation. Under mild restrictions on the demand process, our algorithm is asymptotically optimal as the number of periods in the time horizon increases, capacities being held fixed. In contrast, we prove that this is not true for additive bid-price mechanisms. We provide computational results that give insight into the performance of these algorithms, for several networks and demand scenarios. We extend these algorithms to handle cancellations and no-shows by incorporating overbooking decisions in the underlying mathematical programming formulation. / by Ioana Popescu. / 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, 2019 / Cataloged from student-submitted PDF version of thesis. / Includes bibliographical references (pages 183-190). / Optimization under uncertainty forms the foundation for many of the fundamental problems the operations research community seeks to solve. In this thesis, we develop and analyze algorithms that incorporate ideas from machine learning to optimize uncertain objectives directly from data. In the first chapter, we consider problems in which the decision affects the observed outcome, such as in personalized medicine and pricing. We present a framework for using observational data to learn to optimize an uncertain objective over a continuous and multi-dimensional decision space. Our approach accounts for the uncertainty in predictions, and we provide theoretical results that show this adds value. In addition, we test our approach on a Warfarin dosing example, and it outperforms the leading alternative methods. / In the second chapter, we develop an approach for solving dynamic optimization problems with covariates that uses machine learning to approximate the unknown stochastic process of the uncertainty. We provide theoretical guarantees on the effectiveness of our method and validate the guarantees with computational experiments. In the third chapter, we introduce a distributionally robust approach for incorporating covariates in large-scale, data-driven dynamic optimization. We prove that it is asymptotically optimal and provide a tractable general-purpose approximation scheme that scales to problems with many temporal stages. Across examples in shipment planning, inventory management, and finance, our method achieves improvements of up to 15% over alternatives. In the final chapter, we apply the techniques developed in previous chapters to the problem of optimizing the operating room schedule at a major US hospital. / Our partner institution faces significant census variability throughout the week, which limits the amount of patients it can accept due to resource constraints at peak times. We introduce a data-driven approach for this problem that combines machine learning with mixed integer optimization and demonstrate that it can reliably reduce the maximal weekly census. / by Christopher George McCord. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

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 213-221). / The availability and prevalence of data have provided a substantial opportunity for decision makers to improve decisions and outcomes by effectively using this data. In this thesis, we propose approaches that start from data leading to high-quality decisions and predictions in various application areas. In the first chapter, we consider problems with observational data, and propose variants of machine learning (ML) algorithms that are trained by taking into account decision quality. The traditional approach to such a task has often focused on two-steps, separating the estimation task from the subsequent optimization task which uses these estimated models. Consequently, this approach can miss out on potential improvements in decision quality by considering these tasks jointly. Crucially, this leads to stronger prescriptive performance, particularly for smaller training set sizes, and improves the decision quality by 3 - 5% over other state-of-the-art methods. / We introduce the idea of uncertainty penalization to control the optimism of these methods which improves their performance, and propose finite-sample regret bounds. Through experiments on real and synthetic data sets, we demonstrate the value of this approach. In the second chapter, we consider observational data with decision-dependent uncertainty; in particular, we focus on problems with a finite number of possible decisions (treatments). We present our method of prescriptive trees, that prescribes the best treatment option by learning from observational data while simultaneously predicting counterfactuals. We demonstrate the effectiveness of such an approach using real data for the problem of personalized diabetes management. In the third chapter, we consider stochastic optimization problems when the sample average approximation approach is computationally expensive. / We introduce a novel measure, called the Prescriptive divergence which takes into account the decision quality of the scenarios, and consider scenario reduction in this context. We demonstrate the power of this optimization-based approach on various examples. In the fourth chapter, we present our work on a problem in predictive analytics where we focus on ML problems from a modern optimization perspective. For sparse shape-constrained regression problems, we propose modern optimization based algorithms that are scalable, and recover the true support with high accuracy and low false positive rates. / by Nishanth Mundru. / Ph. D. / Ph.D. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center

This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Thesis: S.M., Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2019 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 82-90). / Social networks have given us the ability to spread messages and influence large populations very easily. Malicious actors can take advantage of social networks to manipulate opinions using artificial accounts, or bots. It is suspected that the 2016 U.S. presidential election was the victim of such social network interference, potentially by foreign actors. Foreign influence bots are also suspected of having attacked European elections. The bots main action was the sharing of politically polarized content in an effort to shift opinions. In this work we present a method to identify coordinated influence campaigns, and quantify the impact of bots on the opinions of users in a social network. First, we provide evidence that modern bots in the social network Twitter coordinate their attacks. They do not create original content, but rather amplify certain human users by disproportionately retweeting them. We design a new algorithm for bot detection, and utilize the Ising model from statistical physics to model the network structure and bot labels. Then, we leverage a model for opinion dynamics in a social network, which we validate by showing that the user opinions predicted by the model align with the opinions of these users' based on their social media posts. Finally, we use the opinion model to calculate how the opinions shift when we remove the bots from the network. Our high level finding is that a small number of bots can have a disproportionate impact on the network opinions. / by Nicolas Guenon des Mesnards / S.M. / S.M. Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center