Thesis: Ph. D., 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 157-163). / Motivated by bottlenecks in algorithms across online and convex optimization, we consider three fundamental questions over combinatorial polytopes. First, we study the minimization of separable strictly convex functions over polyhedra. This problem is motivated by first-order optimization methods whose bottleneck relies on the minimization of a (often) separable, convex metric, known as the Bregman divergence. We provide a conceptually simple algorithm, Inc-Fix, in the case of submodular base polyhedra. For cardinality-based submodular polytopes, we show that Inc-Fix can be speeded up to be the state-of-the-art method for minimizing uniform divergences. We show that the running time of Inc-Fix is independent of the convexity parameters of the objective function. The second question is concerned with the complexity of the parametric line search problem in the extended submodular polytope P: starting from a point inside P, how far can one move along a given direction while maintaining feasibility. This problem arises as a bottleneck in many algorithmic applications like the above-mentioned Inc-Fix algorithm and variants of the Frank-Wolfe method. One of the most natural approaches is to use the discrete Newton's method, however, no upper bound on the number of iterations for this method was known. We show a quadratic bound resulting in a factor of n6 reduction in the worst-case running time from the previous state-of-the-art. The analysis leads to interesting extremal questions on set systems and submodular functions. Next, we develop a general framework to simulate the well-known multiplicative weights update algorithm for online linear optimization over combinatorial strategies U in time polynomial in log /U/, using efficient approximate general counting oracles. We further show that efficient counting over the vertex set of any 0/1 polytope P implies efficient convex minimization over P. As a byproduct of this result, we can approximately decompose any point in a 0/1 polytope into a product distribution over its vertices. Finally, we compare the applicability and limitations of the above results in the context of finding Nash-equilibria in combinatorial two-player zero-sum games with bilinear loss functions. We prove structural results that can be used to find certain Nash-equilibria with a single separable convex minimization. / by Swati Gupta. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2007. / Includes bibliographical references (p. 115-121). / In the past decade, we have seen significant increase in the level of outsourcing in many industries. This increase in the level of outsourcing increases the importance of implementing effective contracts in supply chains. In this thesis, we study several issues in supply chain contracts. In the first part of the thesis, we study the impact of effort in a supply chain with multiple retailers. The costly effort engaged by a retailer may increase or decrease the demands of other retailers. However, effort is usually not verifiable and hence not contractible. Based on the impact of a retailer's effort on its own and other retailers' revenue, we classify each retailer into different categories. According to the corresponding categories of all retailers, we identify coordinating contracts and general classes of contracts that cannot coordinate. Second, we study the stability of coordinating contracts in supply chains. We illustrate that, due to competition, not all coordinating contracts are achievable. Thus, we introduce the notion of rational contracts, which reflects the agents "bargaining power". We propose a general framework for coordinating and rational contracts. Using this framework, we analyze two supply chains, a supply chain with multiple suppliers and single retailer, and a supply chain with a single supplier and price-competing retailers. / (cont.) We identify coordinating contracts for each case and characterize the bounds on profit shares for the agents in any rational contracts. Finally, we study the robustness of coordinating contracts to renegotiation. Applying the concept of contract equilibrium, we show that many coordinating contracts are not robust to bilateral renegotiation if the relationship between the supplier and the retailers is a one-shot game. If the supplier and retailers engage in long-term relationship, then many coordinating contracts are robust to bilateral renegotiation. We also extend concept of contract equilibrium to the concept of strong contract equilibrium to study the robustness of contracts to multilateral renegotiation. We show that, in repeated game setting, the concept of strong contract equilibrium is related to the concept of rational contracts. / by Wanhang (Stephen) Shum. / Ph.D.

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