Many real-world problems, particularly in global sustainability, involve large-scale, highly complex systems. In decision making, this often entails optimizing for multiple competing objectives concurrently, as in large-scale projects such as energy or conservation planning. For many modeling tasks, this requires reasoning over multiple correlated entities simultaneously, such as with multi-object detection and classification or semantic scene classification. Unfortunately, this level of complexity often pushes standard deep learning and classical methods beyond their limits. However, exploiting problem structure can make them more tractable, scalable, and interpretable. We apply this approach to two motivating problems in computational sustainability. First, a multi-objective optimization case study on large-scale hydropower dam planning in South America, including the Amazon basin, which requires balancing multiple environmental and societal objectives. We leverage the river network's inherent tree structure and key operational constraints in order to identify significantly more accurate Pareto frontiers, the set of solutions where no solution exists that is better in all objectives. Additionally, our careful analyses reveal objective tradeoffs and the potential benefit of co-locating floating solar on hydropower reservoirs. Importantly, our algorithms are general and can be applied to other tree-structured networks. Second, we address joint species distribution modeling, which is crucial for biodiversity conservation, by leveraging eBird, a massive participatory science program for bird observations. This translates into a multi-entity learning task focused on interpretable models that capture both environment-species and species-species interactions. Our contributions include additive feature groupings for analyzing environmental drivers and LabelKAN, a novel structured and interpretable latent-space model that explicitly captures entity-entity relationships. LabelKAN improves predictive performance and enables new analyses of species co-occurrence patterns. These methodologies, while driven by specific applications working closely with domain experts, represent novel computational algorithms and models applicable to broader domains in multi-objective decision-making and multi-entity learning, while still remaining true to the original domains.