Back to Search
Start Over
Boosting Efficiency for Computing the Pareto Frontier on Tree Structured Networks
- Source :
- Integration of Constraint Programming, Artificial Intelligence, and Operations Research ISBN: 9783319930305, CPAIOR
- Publication Year :
- 2018
- Publisher :
- Springer International Publishing, 2018.
-
Abstract
- 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 show how a divide-and-conquer approach, combined with batched processing and pruning, significantly boosts the performance of an exact and approximation dynamic programming (DP) algorithm for computing the Pareto frontier on tree-structured networks, proposed in [18]. We also show how exploiting restarts and a new instance selection strategy boosts the performance and accuracy of a mixed integer programming (MIP) approach for approximating the Pareto frontier. We provide empirical results demonstrating that our DP and MIP approaches have complementary strengths and outperform previous algorithms in efficiency and accuracy. Our work is motivated by a problem in computational sustainability concerning the evaluation of trade-offs in ecosystem services due to the proliferation of hydropower dams throughout the Amazon basin. Our approaches are general and can be applied to computing the Pareto frontier of a variety of multi-objective problems on tree-structured networks.
- Subjects :
- 020301 aerospace & aeronautics
Mathematical optimization
Boosting (machine learning)
Computer science
Pareto principle
Approximation algorithm
020207 software engineering
02 engineering and technology
Computational sustainability
Multi-objective optimization
Dynamic programming
Frontier
0203 mechanical engineering
0202 electrical engineering, electronic engineering, information engineering
Integer programming
Subjects
Details
- ISBN :
- 978-3-319-93030-5
- ISBNs :
- 9783319930305
- Database :
- OpenAIRE
- Journal :
- Integration of Constraint Programming, Artificial Intelligence, and Operations Research ISBN: 9783319930305, CPAIOR
- Accession number :
- edsair.doi...........af3b7774447e8c0500fc9b636f7a5d0b