Skip to main content


eCommons@Cornell

eCommons@Cornell >
Cornell University Graduate School >
Theses and Dissertations (OPEN) >

Please use this identifier to cite or link to this item: http://hdl.handle.net/1813/29123
Title: Exploiting Structure In Combinatorial Problems With Applications In Computational Sustainability
Authors: Dilkina, Bistra
Keywords: computational sustainability
sat
milp
combinatorial optimizations
backdoors
conservation planning
active learning
Issue Date: 31-Jan-2012
Abstract: Combinatorial decision and optimization problems are at the core of many tasks with practical importance in areas as diverse as planning and scheduling, supply chain management, hardware and software verification, electronic commerce, and computational biology. Another important source of combinatorial problems is the newly emerging field of computational sustainability, which addresses decision-making aimed at balancing social, economic and environmental needs to guarantee the long-term prosperity of life on our planet. This dissertation studies different forms of problem structure that can be exploited in developing scalable algorithmic techniques capable of addressing large real-world combinatorial problems. There are three major contributions in this work: 1) We study a form of hidden problem structure called a backdoor, a set of key decision variables that captures the combinatorics of the problem, and reveal that many real-world problems encoded as Boolean satisfiability or mixed-integer linear programs contain small backdoors. We study backdoors both theoretically and empirically and characterize important tradeoffs between the computational complexity of finding backdoors and their effectiveness in capturing problem structure succinctly. 2) We contribute several domain-specific mathematical formulations and algorithmic techniques that exploit specific aspects of problem structure arising in budget-constrained conservation planning for wildlife habitat connectivity. Our solution approaches scale to real-world conservation settings and provide important decision-support tools for cost-benefit analysis. 3) We propose a new survey-planning methodology to assist in the construction of accurate predictive models, which are especially relevant in sustainability areas such as species- distribution prediction and climate-change impact studies. In particular, we design a technique that takes advantage of submodularity, a structural property of the function to be optimized, and results in a polynomial-time procedure with approximation guarantees.
Committee Chair: Gomes, Carla P
Committee Member: Shmoys, David B
Kozen, Dexter Campbell
Discipline: Computer Science
Degree Name: Ph.D. of Computer Science
Degree Level: Doctor of Philosophy
Degree Grantor: Cornell University
URI: http://hdl.handle.net/1813/29123
Appears in Collections:Theses and Dissertations (OPEN)

Files in This Item:

File Description SizeFormat
bnd6thesisPDF.pdf4.5 MBAdobe PDFView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.

 

© 2014 Cornell University Library Contact Us