Multi-objective optimization plays a key role in understanding many ecological problems such as ecosystem service tradeoffs, as they are often not fully characterized by a single optimal solution and frequently involve multiple competing objectives. For instance, in optimal hydropower dam placement and barrier removal problems, a given portfolio of dams may cause low impacts on biogeochemical cycles, but large disruptions in fish migration. It is therefore important to identify the so-called Pareto frontier, which captures the trade-offs between the objectives of different solutions. Specifically, our work is motivated by the proliferation of hydropower dams throughout the Amazon basin. We identified >350 proposed dams in the Amazon Basin and 6 criteria encapsulating major ecological impacts of dams. Our goal is to find a set of good portfolios of dams with respect to these criteria out of the total 2350 (≈ 10105) possible portfolios. The scale and complexity of this multi-objective optimization problem prompts us to develop more efficient computational tools for approximating the Pareto frontiers on river networks and tree-structured networks in general.
Results/Conclusions
We developed a computational framework based on Dynamic Programming (DP) which computes the exact Pareto frontier, and a rounding technique that provides a fully polynomial-time approximation scheme (FPTAS). Compared to previous approaches used to compute the Pareto frontiers for dam placement, our algorithm provides optimality guarantees and is computationally more efficient. Importantly, we also show that the approximate version of our algorithm is guaranteed to run in polynomial time. As an example, the computation of the exact Pareto frontier for the 351 proposed dams for 2 criteria takes 20 minutes (wall-clock time, 36 threads; ≈ 10 hours CPU time) and produces 238,459 non-dominated portfolios. Computing the ε-approximate Pareto frontier with 99% accuracy (i.e., ε = 0.01) for the 351 proposed dams takes 137 seconds wall-clock time (36 threads, ≈ 50 minutes CPU time) and produces 91,033 non-dominated portfolios. Our method is general and widely applicable to other multi-objective optimization problems in ecology emerging from the data revolution in recent years.