Multi-objective optimization plays a key role in the study of real-world problems, as they often involve multiple criteria. In multi-objective optimization, it is important to identify the so-called Pareto frontier, which characterizes the trade-offs between the objectives of different solutions. We provide a C++ implementation of exact and approximate dynamic programming (DP) algorithms for computing the Pareto frontier on tree-structured networks. The code uses a specialized divide-and-conquer approach for the pruning of dominated solutions. This optimization outperforms the previous approaches, leading to speed-ups of two to three orders of magnitude in practice.

We apply a rounding technique to the exact dynamic programming algorithm that provides a fully polynomial-time approximation scheme (FPTAS). The FPTAS finds a solution set of polynomial-size, which approximates the Pareto frontier within an arbitrary small e factor and runs in time that is polynomial in the size of the instance and 1/ e.

We illustrate the code by evaluating trade-offs in ecosystem services due to the proliferation of hydropower dams throughout the Amazon basin. In particular, we apply our algorithms to identify portfolios of hydropower dam sites that simultaneously minimize impacts on river flow, river connectivity, sediment transport, fish diversity, and greenhouse gas emissions while achieving energy production goals, at different scales, including the entire Amazon basin. The code can be easily adapted to compute the Pareto frontier of various multi-objective problems for other river basins or other tree-structured networks. This work is described in the manuscript by Flecker et al., entitled “Reducing adverse impacts of Amazon hydropower expansion” in press, Science, 2021