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. 108-112). / Classical methods of maximum likelihood and least squares rely a great deal on the correctness of the model assumptions. Since these assumptions are only approximations of reality, many robust statistical methods have been developed to produce estimators that are robust against the deviation from the model assumptions. Unfortunately, these techniques have very high computational complexity that prevents their application to large scale problems. We present computationally efficient methods for robust mean-covariance estimation and robust linear regression using special mathematical programming models and semi-definite programming (SDP). In the robust covariance estimation problem, we design an optimization model with a loss function on the weighted Mahalanobis distances and show that the problem is equivalent to a system of equations and can be solved using the Newton-Raphson method. The problem can also be transformed into an SDP problem from which we can flexibly incorporate prior beliefs into the estimators without much increase in the computational complexity. The robust regression problem is often formulated as the least trimmed squares (LTS) regression problem where we want to nd the best subset of observations with the smallest sum of squared residuals. We show the LTS problem is equivalent to a concave minimization problem, which is very hard to solve. We resolve this difficulty by introducing the maximum trimmed squares" problem that finds the worst subset of observations. This problem can be transformed into an SDP problem that can be solved efficiently while still guaranteeing that we can identify outliers. / (cont.) In addition, we model the robust ranking problem as a mixed integer minimax problem where the ranking is in a discrete uncertainty set. We use mixed integer programming methods, specifically column generation and network flows, to solve the robust ranking problem. To illustrate the power of these robust methods, we apply them to the mean-variance portfolio optimization problem in order to incorporate estimation errors into the model. / by Tri-Dung Nguyen. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Sloan School of Management, Operations Research Center, 2008. / Includes bibliographical references (p. 123-130). / Large population health insurance claims databases together with operations research and data mining methods have the potential of significantly impacting health care management. In this thesis we research how claims data can be utilized in three important areas of health care and medicine and apply our methods to a real claims database containing information of over two million health plan members. First, we develop forecasting models for health care costs that outperform previous results. Secondly, through examples we demonstrate how large-scale databases and advanced clustering algorithms can lead to discovery of medical knowledge. Lastly, we build a mathematical framework for a real-time drug surveillance system, and demonstrate with real data that side effects can be discovered faster than with the current post-marketing surveillance system. / by Margrét Vilborg Bjarnadóttir. / Ph.D.

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. 123-124). / Combat outposts (COPs) are small, well-protected bases from which soldiers reside and conduct operations from. Used extensively during the "Surge" in Iraq, COPs are usually established in populated areas and are prevalent in the counterinsurgency operations in Afghanistan in 2010. This research models population security to determine combat outpost locations in a battalion area of operation. Population security is measured by level of violence, level of insurgent activity, and effectiveness of host nation security forces. The area of operation is represented as a graphical network of nodes and arcs. Operational inputs include pertinent information about each node. The model allows the commander to set various weights that reflect his understanding of the situation, mission, and local people. Based on trade-offs in patrolling and self-protection, the deterministic model recommends the size and locations for emplacing combat outposts and conducting patrols. We use piecewise linear approximation to solve the problem as a mixed-integer linear program. Results are based on two representative scenarios and show the impact of an area of operation's characteristics and commander's weights on COP size and locations. / by Scott B. Seidel. / S.M.

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.

<p> This dissertation studies two important models in the field of the distributed generation technologies to provide resiliency to the electric power distribution system. In the first part of the dissertation, we study the impact of assessing a Combined Cooling Heating Power system (CCHP) on the optimization and management of an on-site energy system under stochastic settings. These mathematical models propose a scalable stochastic decision model for large-scale microgrid operation formulated as a two-stage stochastic linear programming model. The model is solved enhanced algorithm strategies for Benders decomposition are introduced to find an optimal solution for larger instances efficiently. Some observations are made with different capacities of the power grid, dynamic pricing mechanisms with various levels of uncertainty, and sizes of power generation units. In the second part of the dissertation, we study a mathematical model that designs a Microgrid (MG) that integrates conventional fuel based generating (FBG) units, renewable sources of energy, distributed energy storage (DES) units, and electricity demand response. Curtailment of renewable resources generation during the MG operation affects the long-term revenues expected and increases the greenhouses emission. Considering the variability of renewable resources, researchers should pay more attention to scalable stochastic models for MG for multiple nodes. This study bridges the research gap by developing a scalable chance-constrained two-stage stochastic program to ensure that a significant portion of the renewable resource power output at each operating hour will be utilized. Finally, some managerial insights are drawn into the operation performance of the Combined Cooling Heating Power and a Microgrid.</p>

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.