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-usExcluding 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