Abstract
The development of ethical AI decision-making systems requires considering multiple criteria, often resulting in a large spectrum of partially ordered solutions. At the core of this challenge lies the Pareto frontier, the set of all feasible solutions where no solution is dominated by another. In previous work, we developed both exact and approximate algorithms for generating the Pareto frontier for tree-structured networks. However, as the number of criteria grows, the Pareto frontier increases exponentially, posing a significant challenge for decision-makers. To address this challenge, we propose various strategies to efficiently compress the Pareto frontier, including an approximation method with optimality and polynomial runtime guarantees. We provide detailed empirical results on the strategies’ effectiveness in the context of strategic planning of the hydropower expansion in the Amazon basin. Our strategies offer a more manageable approach for navigating Pareto frontiers.
This project is partially supported by the Eric and Wendy Schmidt AI in Science Postdoctoral Fellowship, a Schmidt Futures program; the National Science Foundation (NSF); the National Institute of Food and Agriculture (USDA/NIFA); the Air Force Office of Scientific Research (AFOSR); and the Cornell Atkinson Center for a Sustainable Future (ACSF).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Almeida, R.M., et al.: Reducing greenhouse gas emissions of amazon hydropower with strategic dam planning. Nat. Commun. 10(1), 1–9 (2019)
Andersen, H.R., Hadzic, T., Hooker, J.N., Tiedemann, P.: A constraint store based on multivalued decision diagrams. In: Bessière, C. (ed.) CP 2007. LNCS, vol. 4741, pp. 118–132. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74970-7_11
Bai, Y., Shi, Q., Grimson, M., Flecker, A., Gomes, C.P.: Efficiently approximating high-dimensional pareto frontiers for tree-structured networks using expansion and compression. In: Cire, A.A. (eds.) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2023. LNCS, vol. 13884, pp. 1–17. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-33271-5_1
Bergman, D., Cire, A.A.: Multiobjective optimization by decision diagrams. In: Rueher, M. (ed.) CP 2016. LNCS, vol. 9892, pp. 86–95. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44953-1_6
Cao, Y., Smucker, B.J., Robinson, T.J.: On using the hypervolume indicator to compare pareto fronts: applications to multi-criteria optimal experimental design. J. Stat. Plan. Inference 160, 60–74 (2015). https://doi.org/10.1016/j.jspi.2014.12.004, https://www.sciencedirect.com/science/article/pii/S0378375814002006
Chen, W., Ishibuchi, H., Shang, K.: Clustering-based subset selection in evolutionary multiobjective optimization. In: 2021 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 468–475. IEEE (2021)
Deb, K., Jain, H.: An evolutionary many-objective optimization algorithm using reference-point-based nondominated sorting approach, part i: solving problems with box constraints. IEEE Trans. Evol. Comput. 18(4), 577–601 (2013)
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T.: A fast and elitist multiobjective genetic algorithm: nsga-ii. IEEE Trans. Evol. Comput. 6(2), 182–197 (2002)
Doerr, B., Qu, Z.: A first runtime analysis of the nsga-ii on a multimodal problem. IEEE Transactions on Evolutionary Computation (2023)
Doerr, B., Qu, Z.: From understanding the population dynamics of the nsga-ii to the first proven lower bounds. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 37, pp. 12408–12416 (2023)
Doerr, B., Qu, Z.: Runtime analysis for the nsga-ii: Provable speed-ups from crossover. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 37, pp. 12399–12407 (2023)
Flecker, A.S., et al.: Reducing adverse impacts of amazon hydropower expansion. Science 375(6582), 753–760 (2022)
Gomes, C., et al.: Computational sustainability: computing for a better world and a sustainable future. Commun. ACM 62(9), 56–65 (2019)
Gomes-Selman, J.M., Shi, Q., Xue, Y., García-Villacorta, R., Flecker, A.S., Gomes, C.P.: Boosting efficiency for computing the pareto frontier on tree structured networks. In: van Hoeve, W.-J. (ed.) CPAIOR 2018. LNCS, vol. 10848, pp. 263–279. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-93031-2_19
Grimson, M., et al.: Scaling up pareto optimization for tree structures with affine transformations: Evaluating hybrid floating solar-hydropower systems in the amazon. In: Proceedings of the AAAI Conference on Artificial Intelligence (submitted)
Johnson, S.C.: Hierarchical clustering schemes. Psychometrika 32(3), 241–254 (1967). https://doi.org/10.1007/bf02289588, http://dx.doi.org/10.1007/BF02289588
Murtagh, F., Legendre, P.: Ward’s hierarchical agglomerative clustering method: which algorithms implement ward’s criterion? J. Classif. 31(3), 274–295 (2014). https://doi.org/10.1007/s00357-014-9161-z, http://dx.doi.org/10.1007/s00357-014-9161-z
Newman, M.E.J.: Finding community structure in networks using the eigenvectors of matrices. Phys. Rev. E 74(3) (2006). https://doi.org/10.1103/physreve.74.036104, http://dx.doi.org/10.1103/PhysRevE.74.036104
Sahraei, S., Asadzadeh, M.: Cluster-based multi-objective optimization for identifying diverse design options: application to water resources problems. Environ. Model. Softw. 135, 104902 (2021)
Sibson, R.: Slink: an optimally efficient algorithm for the single-link cluster method. Comput. J. 16(1), 30–34 (1973). https://doi.org/10.1093/comjnl/16.1.30, http://dx.doi.org/10.1093/comjnl/16.1.30
Sokal, R.R.: Numerical taxonomy. Sci. Am. 215(6), 106–117 (1966). http://www.jstor.org/stable/24931358
Srinivas, N., Deb, K.: Muiltiobjective optimization using nondominated sorting in genetic algorithms. Evol. Comput. 2(3), 221–248 (1994)
United Nations General Assembly: Transforming our world: the 2030 agenda for sustainable development (2015). https://sdgs.un.org/2030agenda
Vamplew, P., Dazeley, R., Foale, C., Firmin, S., Mummery, J.: Human-aligned artificial intelligence is a multiobjective problem. Ethics Inf. Technol. 20, 27–40 (2018)
Wei, D., Jiang, Q., Wei, Y., Wang, S.: A novel hierarchical clustering algorithm for gene sequences. BMC Bioinform. 13(1) (2012). https://doi.org/10.1186/1471-2105-13-174, http://dx.doi.org/10.1186/1471-2105-13-174
Wu, X., et al.: Efficiently approximating the pareto frontier: hydropower dam placement in the amazon basin. In: Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32 (2018)
Zhang, H., Song, S., Zhou, A., Gao, X.Z.: A clustering based multiobjective evolutionary algorithm. In: 2014 IEEE Congress on Evolutionary Computation (CEC), pp. 723–730. IEEE (2014)
Zhang, Q., Li, H.: MOEA/D: a multiobjective evolutionary algorithm based on decomposition. IEEE Trans. Evol. Comput. 11(6), 712–731 (2007)
Zheng, W., Liu, Y., Doerr, B.: A first mathematical runtime analysis of the Non-Dominated Sorting Genetic Algorithm II (NSGA-II). In: Conference on Artificial Intelligence, AAAI 2022. AAAI Press (2022). preprint at https://arxiv.org/abs/2112.08581
Zhou, S., et al.: A multi-objective evolutionary algorithm with hierarchical clustering-based selection. IEEE Access 11, 2557–2569 (2023)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Qu, Z. et al. (2024). Strategies for Compressing the Pareto Frontier: Application to Strategic Planning of Hydropower in the Amazon Basin. In: Dilkina, B. (eds) Integration of Constraint Programming, Artificial Intelligence, and Operations Research. CPAIOR 2024. Lecture Notes in Computer Science, vol 14743. Springer, Cham. https://doi.org/10.1007/978-3-031-60599-4_9
Download citation
DOI: https://doi.org/10.1007/978-3-031-60599-4_9
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-60601-4
Online ISBN: 978-3-031-60599-4
eBook Packages: Computer ScienceComputer Science (R0)