Academic Commons Search Results
http://academiccommons.columbia.edu/catalog.rss?f%5Bdepartment_facet%5D%5B%5D=Operations+Research&q=&rows=500&sort=record_creation_date+desc
Academic Commons Search Resultsen-usSmart Grid Risk Management
http://academiccommons.columbia.edu/catalog/ac:188373
Abad Lopez, Carlos Adrianhttp://dx.doi.org/10.7916/D8028QR9Tue, 21 Jul 2015 00:00:00 +0000Current electricity infrastructure is being stressed from several directions -- high demand, unreliable supply, extreme weather conditions, accidents, among others. Infrastructure planners have, traditionally, focused on only the cost of the system; today, resilience and sustainability are increasingly becoming more important. In this dissertation, we develop computational tools for efficiently managing electricity resources to help create a more reliable and sustainable electrical grid. The tools we present in this work will help electric utilities coordinate demand to allow the smooth and large scale integration of renewable sources of energy into traditional grids, as well as provide infrastructure planners and operators in developing countries a framework for making informed planning and control decisions in the presence of uncertainty. Demand-side management is considered as the most viable solution for maintaining grid stability as generation from intermittent renewable sources increases. Demand-side management, particularly demand response (DR) programs that attempt to alter the energy consumption of customers either by using price-based incentives or up-front power interruption contracts, is more cost-effective and sustainable in addressing short-term supply-demand imbalances when compared with the alternative that involves increasing fossil fuel-based fast spinning reserves. An essential step in compensating participating customers and benchmarking the effectiveness of DR programs is to be able to independently detect the load reduction from observed meter data. Electric utilities implementing automated DR programs through direct load control switches are also interested in detecting the reduction in demand to efficiently pinpoint non-functioning devices to reduce maintenance costs. We develop sparse optimization methods for detecting a small change in the demand for electricity of a customer in response to a price change or signal from the utility, dynamic learning methods for scheduling the maintenance of direct load control switches whose operating state is not directly observable and can only be inferred from the metered electricity consumption, and machine learning methods for accurately forecasting the load of hundreds of thousands of residential, commercial and industrial customers. These algorithms have been implemented in the software system provided by AutoGrid, Inc., and this system has helped several utilities in the Pacific Northwest, Oklahoma, California and Texas, provide more reliable power to their customers at significantly reduced prices. Providing power to widely spread out communities in developing countries using the conventional power grid is not economically feasible. The most attractive alternative source of affordable energy for these communities is solar micro-grids. We discuss risk-aware robust methods to optimally size and operate solar micro-grids in the presence of uncertain demand and uncertain renewable generation. These algorithms help system operators to increase their revenue while making their systems more resilient to inclement weather conditions.Operations research, Energyca2446Operations Research, Industrial Engineering and Operations ResearchDissertationsExcluding Induced Paths: Graph Structure and Coloring
http://academiccommons.columbia.edu/catalog/ac:186521
Maceli, Peter Lawsonhttp://dx.doi.org/10.7916/D8WW7GK4Mon, 20 Apr 2015 12:17:03 +0000An induced subgraph of a given graph is any graph which can be obtained by successively deleting vertices, possible none. In this thesis, we present several new structural and algorithmic results on a number of different classes of graphs which are closed under taking induced subgraphs.
The first result of this thesis is related to a conjecture of Hayward and Nastos on the structure of graphs with no induced four-edge path or four-edge antipath. They conjectured that every such graph which is both prime and perfect is either a split graph or contains a certain useful arrangement of simplicial and antisimplicial vertices. We give a counterexample to their conjecture, and prove a slightly weaker version. This is joint work with Maria Chudnovsky, and first appeared in Journal of Graph Theory.
The second result of this thesis is a decomposition theorem for the class of all graphs with no induced four-edge path or four-edge antipath. We show that every such graph can be obtained from pentagons and split graphs by repeated application of complementation, substitution, and split graph unification. Split graph unification is a new graph operation we introduced, which is a generalization of substitution and involves "gluing" two graphs along a common induced split graph. This is a combination of joint work with Maria Chudnovsky and Irena Penev, together with later work of Louis Esperet, Laetitia Lemoine and Frederic Maffray, and first appeared in.
The third result of this thesis is related to the problem of determining the complexity of coloring graphs which do not contain some fixed induced subgraph. We show that three-coloring graphs with no induced six-edge path or triangle can be done in polynomial-time. This is joint work with Maria Chudnovsky and Mingxian Zhong, and first appeared in. Working together with Flavia Bonomo, Oliver Schaudt, and Maya Stein, we have since simplified and extended this result.Operations research, Mathematics, Computer scienceplm2109Operations Research, Industrial EngineeringDissertationsEssays on Inventory Management and Conjoint Analysis
http://academiccommons.columbia.edu/catalog/ac:181257
Chen, Yupenghttp://dx.doi.org/10.7916/D8GX49BDWed, 10 Dec 2014 00:00:00 +0000With recent theoretic and algorithmic advancements, modern optimization methodologies have seen a substantial expansion of modeling power, being applied to solve challenging problems in impressively diverse areas. This dissertation aims to extend the modeling frontier of optimization methodologies in two exciting fields inventory management and conjoint analysis. Although the three essays concern distinct applications using different optimization methodologies, they share a unifying theme, which is to develop intuitive models using advanced optimization techniques to solve problems of practical relevance. The first essay (Chapter 2) applies robust optimization to solve a single installation inventory model with non stationary uncertain demand. A classical problem in operations research, the inventory management model could become very challenging to analyze when lost sales dynamics, non zero fixed ordering cost, and positive lead time are introduced. In this essay, we propose a robust cycle based control policy based on an innovative decomposition idea to solve a family of variants of this model. The policy is simple, flexible, easily implementable and numerical experiments suggest that the policy has very promising empirical performance.The policy can be used both when the excess demand is backlogged as well as when it is lost; with non zero fixed ordering cost, and also when lead time is non zero. The policy decisions are computed by solving a collection of linear programs even when there is a positive fixed ordering cost. The policy also extends in a very simple manner to the joint pricing and inventory control problem. The second essay (Chapter 3) applies sparse machine learning to model multimodal continuous heterogeneity in conjoint analysis. Consumers' heterogeneous preferences can often be represented using a multimodal continuous heterogeneity (MCH) distribution. One interpretation of MCH is that the consumer population consists of a few distinct segments, each of which contains a heterogeneous sub population. Modeling of MCH raises considerable challenges as both across and within segment heterogeneity need to be accounted for. In this essay, we propose an innovative sparse learning approach for modeling MCH and apply it to conjoint analysis where adequate modeling of consumer heterogeneity is critical. The sparse learning approach models MCH via a two-stage divide and conquer framework, in which we first decompose the consumer population by recovering a set of candidate segmentations using structured sparsity modeling, and then use each candidate segmentation to develop a set of individual level representations of MCH. We select the optimal individual level representation of MCH and the corresponding optimal candidate segmentation using cross-validation. Two notable features of our approach are that it accommodates both across and within segment heterogeneity and endogenously imposes an adequate amount of shrinkage to recover the individual level partworths. We empirically validate the performance of the sparse learning approach using extensive simulation experiments and two empirical conjoint data sets. The third essay (Chapter 4) applies dynamic discrete choice models to investigate the impact of return policies on consumers' product purchase and return behavior. Return policies have been ubiquitous in the marketplace, allowing consumers to use and evaluate a product before fully committing to purchase. Despite the clear practical relevance of return policies, however, few studies have provided empirical assessments of how consumers' purchase and return decisions respond to the return policies facing them. In this essay, we propose to model consumers' purchase and return decisions using a dynamic discrete choice model with forward looking and Bayesian learning. More specifically, we postulate that consumers' purchase and return decisions are optimal solutions for some underlying dynamic expected utility maximization problem in which consumers learn their true evaluations of products via usage in a Bayesian manner and make purchase and return decisions to maximize their expected present value of utility, and return policies impact consumers' purchase and return decisions by entering the dynamic expected utility maximization problem as constraints. Our proposed model provides a behaviorally plausible approach to examine the impact of return policies on consumers' purchase and return behavior.Operations researchyc2561Operations ResearchDissertations