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

By: , and 



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.

Study Area

Additional publication details

Publication type Conference Paper
Publication Subtype Conference Paper
Title Efficiently approximating the Pareto frontier: Hydropower dam placement in the Amazon basin
Year Published 2018
Language English
Publisher AAAI
Contributing office(s) Coop Res Unit Leetown
Description 10 p.
Larger Work Type Book
Larger Work Subtype Conference publication
Larger Work Title Proc. Thirty-Second AAAI Conference on Artificial Intelligence
Other Geospatial Amazon Basin