Learning to Prune Instances of Steiner Tree Problem in Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915254059925504 |
|---|---|
| author | Zhang, Jiwei Ajwani, Deepak |
| author_facet | Zhang, Jiwei Ajwani, Deepak |
| contents | We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional nodes. This is a classical NP-hard combinatorial optimisation problem. In recent years, a machine learning framework called learning-to-prune has been successfully used for solving a diverse range of combinatorial optimisation problems. In this paper, we use this learning framework on the Steiner tree problem and show that even on this problem, the learning-to-prune framework results in computing near-optimal solutions at a fraction of the time required by commercial ILP solvers. Our results underscore the potential of the learning-to-prune framework in solving various combinatorial optimisation problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2208_11985 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Learning to Prune Instances of Steiner Tree Problem in Graphs Zhang, Jiwei Ajwani, Deepak Data Structures and Algorithms Artificial Intelligence Discrete Mathematics Machine Learning We consider the Steiner tree problem on graphs where we are given a set of nodes and the goal is to find a tree sub-graph of minimum weight that contains all nodes in the given set, potentially including additional nodes. This is a classical NP-hard combinatorial optimisation problem. In recent years, a machine learning framework called learning-to-prune has been successfully used for solving a diverse range of combinatorial optimisation problems. In this paper, we use this learning framework on the Steiner tree problem and show that even on this problem, the learning-to-prune framework results in computing near-optimal solutions at a fraction of the time required by commercial ILP solvers. Our results underscore the potential of the learning-to-prune framework in solving various combinatorial optimisation problems. |
| title | Learning to Prune Instances of Steiner Tree Problem in Graphs |
| topic | Data Structures and Algorithms Artificial Intelligence Discrete Mathematics Machine Learning |
| url | https://arxiv.org/abs/2208.11985 |