Grouping Strategies on Two-Phase Methods for Bi-objective Combinatorial Optimization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917981502570496 |
|---|---|
| author | Mota, Felipe O. Paquete, Luís Vanderpooten, Daniel |
| author_facet | Mota, Felipe O. Paquete, Luís Vanderpooten, Daniel |
| contents | Two-phase methods are commonly used to solve bi-objective combinatorial optimization problems. In the first phase, all extreme supported nondominated points are generated through a dichotomic search. This phase also allows the identification of search zones that may contain other nondominated points. The second phase focuses on exploring these search zones to locate the remaining points, which typically accounts for most of the computational cost. Ranking algorithms are frequently employed to explore each zone individually, but this approach leads to redundancies, causing multiple visits to the same solutions. To mitigate these redundancies, we propose several strategies that group adjacent zones, allowing a single run of the ranking algorithm for the entire group. Additionally, we explore an implicit grouping approach based on a new concept of coverage. Our experiments on the Bi-Objective Spanning Tree Problem demonstrate the beneficial impact of these grouping strategies when combined with coverage. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_06869 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Grouping Strategies on Two-Phase Methods for Bi-objective Combinatorial Optimization Mota, Felipe O. Paquete, Luís Vanderpooten, Daniel Data Structures and Algorithms Discrete Mathematics Two-phase methods are commonly used to solve bi-objective combinatorial optimization problems. In the first phase, all extreme supported nondominated points are generated through a dichotomic search. This phase also allows the identification of search zones that may contain other nondominated points. The second phase focuses on exploring these search zones to locate the remaining points, which typically accounts for most of the computational cost. Ranking algorithms are frequently employed to explore each zone individually, but this approach leads to redundancies, causing multiple visits to the same solutions. To mitigate these redundancies, we propose several strategies that group adjacent zones, allowing a single run of the ranking algorithm for the entire group. Additionally, we explore an implicit grouping approach based on a new concept of coverage. Our experiments on the Bi-Objective Spanning Tree Problem demonstrate the beneficial impact of these grouping strategies when combined with coverage. |
| title | Grouping Strategies on Two-Phase Methods for Bi-objective Combinatorial Optimization |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2504.06869 |