Skip to main content
U.S. flag

An official website of the United States government

Efficiently approximating the Pareto frontier: Hydropower dam placement in the Amazon basin

January 1, 2018

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  > 0 on treestructured networks. Given a set of objectives, our approximation scheme runs in time polynomial in the size of the instance and 1/. 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.

Publication Year 2018
Title Efficiently approximating the Pareto frontier: Hydropower dam placement in the Amazon basin
Authors Xiaojian Wu, Jonathan Gomes-Selman, Qinru Shi, Yexiang Xue, Roosevelt Garcia-Villacorta, Eliza Anderson, Suresh Sethi, Scott Steinschneider, Alexander Flecker, Carla P. Gomes
Publication Type Conference Paper
Publication Subtype Conference Paper
Index ID 70196983
Record Source USGS Publications Warehouse
USGS Organization Coop Res Unit Leetown