Research map / Learning theory and algorithms / Combinatorial and search optimization
Constraint-aware Pareto Optimization for Tree-Structured Networks: Addressing Decarbonization Targets with Hydropower Expansion
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a constraint-aware dynamic-programming Pareto algorithm for tree-structured networks with lower and upper objective bounds, applied to hydropower dam portfolio planning in the Magdalena River basin under Colombia's net-zero 2050 targets.
Problem
Multi-objective combinatorial optimization of hydropower dam portfolios on tree-structured river networks where objectives carry realistic lower and upper bounds (energy/capacity targets), which existing unconstrained Pareto methods ignore.
Approach
Extends the tree-structured DP Pareto algorithm with box constraints by pruning partial solutions at each node that cannot satisfy lower bounds (provably a subset of unconstrained frontier) or upper bounds (using forced minimum contributions from outside the subtree), so that the constrained frontier covers more feasible solutions than post-hoc filtering.
Key results
- On synthetic trees the constraint-aware method finds up to 50% more of the true constrained Pareto solutions than post hoc removal, and never fewer.
- On the full Magdalena basin with NZ-1% bounds and epsilon 0.01, the constraint-aware method runs in 4,779 s versus 41,907 s for post hoc removal and reaches normalized hypervolume 0.589 versus 0.585.
- Constraint-aware search is reported as 1.5 to 9 times faster on large instances as objectives increase and bounds tighten.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, BAU-NZ · Magdalena basin, BAU-NZ | runtime (sec): 41,907 -> 26,375 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, BAU-NZ · Magdalena basin, BAU-NZ | # Pareto Solutions: 22,420,662 -> 22,469,399 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, BAU-NZ · Magdalena basin, BAU-NZ | # Pareto Solutions ≥99% UB: 15,181 -> 17,773 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, BAU-NZ · Magdalena basin, BAU-NZ | Normalized Hypervolume: 0.318 -> 0.324 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, NZ-1% · Magdalena basin, NZ-1% | runtime (sec): 41,907 -> 4,779 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, NZ-1% · Magdalena basin, NZ-1% | # Pareto Solutions: 132,159 -> 135,283 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, NZ-1% · Magdalena basin, NZ-1% | # Pareto Solutions ≥99% UB: 21,473 -> 23,175 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Magdalena basin, NZ-1% · Magdalena basin, NZ-1% | Normalized Hypervolume: 0.585 -> 0.589 | Helped |
| Use constraint-aware Pareto optimization instead of post-hoc removal of infeasible solutions | Constraint-aware Pareto optimization · Synthetic trees, 3–5 objectives | true constrained Pareto solutions found: up to 50% more | Helped |
| Use lower-bound constraints to prune partial solutions that cannot meet the bounds | Constraint-aware Pareto optimization · Synthetic trees | solutions considered | Helped |
Surprising findings
- Feasible Pareto solutions can be dominated by infeasible solutions, so constraint-agnostic solvers may discard them.
Limitations
- Upper-bound pruning sacrifices guarantees of exact optimality and of covering the upper-bound region; found solutions may not be Pareto optimal for the constrained problem.
- Constraints only on objective space; decision-space constraints (e.g., mutually exclusive dams) not handled.
- True Pareto frontier infeasible to compute for full Magdalena, so comparisons rely on the Cauca sub-basin.
Experimental setup
Datasets: Magdalena River basin hydropower dam data (143 proposed dams) Cauca sub-basin (19 built, 28 unbuilt dams) synthetic tree instances (10 trees, 26 nodes)
Benchmarks: synthetic tree instances Cauca sub-basin exhaustive search Magdalena River basin
Metrics: percentage of true constrained Pareto solutions found normalized distance to missed Pareto solutions runtime normalized hypervolume number of solutions considered
Baselines: post hoc removal of infeasible solutions from unconstrained Pareto frontier exhaustive search
Builds on: Wu et al. 2018 tree-structured Pareto DP Grimson et al. 2024 multi-edged tree FPTAS Gomes-Selman et al. 2018
Closest papers by meaning
- Scaling Up Pareto Optimization for Tree Structures with Affine Transformations: Evaluating Hybrid Floating Solar-Hydropower Systems in the Amazon (AAAI 2024 · similarity 0.93)
- Threshold UCT: Cost-Constrained Monte Carlo Tree Search with Pareto Curves (AAAI 2025 · similarity 0.80)
- How to Find the Exact Pareto Front for Multi-Objective MDPs? (ICLR 2025 · similarity 0.80)
- Preference Optimization on Pareto Sets: On a Theory of Multi-Objective Optimization (NeurIPS 2025 · similarity 0.80)
- ParetoFlow: Guided Flows in Multi-Objective Optimization (ICLR 2025 · similarity 0.80)
- Graph-Based Stochastic-Power-UCT: Monte-Carlo Graph Search with Power Mean Estimation (NeurIPS 2026 · similarity 0.80)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.