Gomes-Selman, Jonathan M.Shi, QinruPerez, Guillaume2021-12-132021-12-132021-12-13https://hdl.handle.net/1813/110374Copyright 2021 Institute for Computational Sustainability Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"), to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions: The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.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, 2021en-USExact and approximate Pareto frontiermulti-optimizationtree structuressoftwarehttps://doi.org/10.7298/qh5x-6f22