Back to search

Cornell University

Exploiting Structure In Combinatorial Problems With Applications In Computational Sustainability

Abstract

dc:description.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.

Degree

thesis:*
Name thesis:degree_name
Ph. D., Computer Science
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Computer Science
Grantor
Cornell University
Year dc:date.issued
2012

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dilkina, Bistra
Chair dc:contributor.chair
  • Gomes, Carla P
Committee members dc:contributor.committeemember
  • Shmoys, David B
  • Kozen, Dexter Campbell

Subjects

dc:subject × 7

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Dc Identifier Bibid
7745063

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dilkina, Bistra. Exploiting Structure In Combinatorial Problems With Applications In Computational Sustainability. Doctor of Philosophy thesis, Cornell University, 2012. https://hdl.handle.net/1813/29123