Efficiently Approximating the Pareto Frontier: Hydropower Dam Placement in the Amazon Basin

Authors

  • Xiaojian Wu Cornell University
  • Jonathan Gomes-Selman Stanford University
  • Qinru Shi Cornell University
  • Yexiang Xue Cornell University
  • Roosevelt Garcia-Villacorta Cornell University
  • Elizabeth Anderson Florida International University
  • Suresh Sethi U.S. Geological Survey, New York Cooperative Fish and Wildlife Unit, Cornell University
  • Scott Steinschneider Cornell University
  • Alexander Flecker Cornell University
  • Carla Gomes Cornell University

Keywords:

Pareto frontier, approximation algorithms, exact algorithms

Abstract

Real-world problems are often not fully characterized by a single optimal solution, as they frequently involve multiple competing objectives; it is therefore important to identify the so-called Pareto frontier, which captures solution trade-offs. We propose a fully polynomial-time approximation scheme based on Dynamic Programming (DP) for computing a polynomially succinct curve that approximates the Pareto frontier to within an arbitrarily small epsilon > 0 on tree-structured networks. Given a set of objectives, our approximation scheme runs in time polynomial in the size of the instance and 1/epsilon. We also propose a Mixed Integer Programming (MIP) scheme to approximate the Pareto frontier. The DP and MIP Pareto frontier approaches have complementary strengths and are surprisingly effective. We provide empirical results showing that our methods outperform other approaches in efficiency and accuracy. Our work is motivated by a problem in computational sustainability concerning the proliferation of hydropower dams throughout the Amazon basin. Our goal is to support decision-makers in evaluating impacted ecosystem services on the full scale of the Amazon basin. Our work is general and can be applied to approximate the Pareto frontier of a variety of multiobjective problems on tree-structured networks.

Downloads

Published

2018-04-25

How to Cite

Wu, X., Gomes-Selman, J., Shi, Q., Xue, Y., Garcia-Villacorta, R., Anderson, E., Sethi, S., Steinschneider, S., Flecker, A., & Gomes, C. (2018). Efficiently Approximating the Pareto Frontier: Hydropower Dam Placement in the Amazon Basin. Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/11347

Issue

Section

Computational Sustainability and Artificial Intelligence