Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929622827925504 |
|---|---|
| author | Gao, Xuan-Zhao Wang, Yi-Jia Zhang, Pan Liu, Jin-Guo |
| author_facet | Gao, Xuan-Zhao Wang, Yi-Jia Zhang, Pan Liu, Jin-Guo |
| contents | The branching algorithm is a fundamental technique for designing fast exponential-time algorithms to solve combinatorial optimization problems exactly. It divides the entire solution space into independent search branches using predetermined branching rules, and ignores the search on suboptimal branches to reduce the time complexity. The complexity of a branching algorithm is primarily determined by the branching rules it employs, which are often designed by human experts. In this paper, we show how to automate this process with a focus on the maximum independent set problem. The main contribution is an algorithm that efficiently generate optimal branching rules for a given sub-graph with tens of vertices. Its efficiency enables us to generate the branching rules on-the-fly, which is provably optimal and significantly reduces the number of branches compared to existing methods that rely on expert-designed branching rules. Numerical experiment on 3-regular graphs shows an average complexity of O(1.0441^n) can be achieved, better than any previous methods. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2412_07685 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem Gao, Xuan-Zhao Wang, Yi-Jia Zhang, Pan Liu, Jin-Guo Optimization and Control Data Structures and Algorithms Combinatorics The branching algorithm is a fundamental technique for designing fast exponential-time algorithms to solve combinatorial optimization problems exactly. It divides the entire solution space into independent search branches using predetermined branching rules, and ignores the search on suboptimal branches to reduce the time complexity. The complexity of a branching algorithm is primarily determined by the branching rules it employs, which are often designed by human experts. In this paper, we show how to automate this process with a focus on the maximum independent set problem. The main contribution is an algorithm that efficiently generate optimal branching rules for a given sub-graph with tens of vertices. Its efficiency enables us to generate the branching rules on-the-fly, which is provably optimal and significantly reduces the number of branches compared to existing methods that rely on expert-designed branching rules. Numerical experiment on 3-regular graphs shows an average complexity of O(1.0441^n) can be achieved, better than any previous methods. |
| title | Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem |
| topic | Optimization and Control Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2412.07685 |