Heuristic Multiobjective Discrete Optimization using Restricted Decision Diagrams
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917353007087616 |
|---|---|
| author | Patel, Rahul Khalil, Elias B. Bergman, David |
| author_facet | Patel, Rahul Khalil, Elias B. Bergman, David |
| contents | Decision diagrams (DDs) have emerged as a state-of-the-art method for exact multiobjective integer linear programming. When the DD is too large to fit into memory or the decision-maker prefers a fast approximation to the Pareto frontier, the complete DD must be restricted to a subset of its states (or nodes). We introduce new node-selection heuristics for constructing restricted DDs that produce a high-quality approximation of the Pareto frontier. Depending on the structure of the problem, our heuristics are based on either simple rules, machine learning with feature engineering, or end-to-end deep learning. Experiments on multiobjective knapsack, set packing, and traveling salesperson problems show that our approach is highly effective, recovering over 85% of the Pareto frontier while achieving 2.5x speedups over exact DD enumeration on average, with very few non-Pareto solutions. The code is available at https://github.com/rahulptel/HMORDD. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_02482 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Heuristic Multiobjective Discrete Optimization using Restricted Decision Diagrams Patel, Rahul Khalil, Elias B. Bergman, David Artificial Intelligence Decision diagrams (DDs) have emerged as a state-of-the-art method for exact multiobjective integer linear programming. When the DD is too large to fit into memory or the decision-maker prefers a fast approximation to the Pareto frontier, the complete DD must be restricted to a subset of its states (or nodes). We introduce new node-selection heuristics for constructing restricted DDs that produce a high-quality approximation of the Pareto frontier. Depending on the structure of the problem, our heuristics are based on either simple rules, machine learning with feature engineering, or end-to-end deep learning. Experiments on multiobjective knapsack, set packing, and traveling salesperson problems show that our approach is highly effective, recovering over 85% of the Pareto frontier while achieving 2.5x speedups over exact DD enumeration on average, with very few non-Pareto solutions. The code is available at https://github.com/rahulptel/HMORDD. |
| title | Heuristic Multiobjective Discrete Optimization using Restricted Decision Diagrams |
| topic | Artificial Intelligence |
| url | https://arxiv.org/abs/2403.02482 |