Learning to Prune Instances of Steiner Tree Problem in Graphs

• URL: http://arxiv.org/abs/2208.11985v1
• Date: Thu, 25 Aug 2022 10:31:00 GMT
• Title: Learning to Prune Instances of Steiner Tree Problem in Graphs
• Authors: Jiwei Zhang and Deepak Ajwani
• Abstract summary: We consider the Steiner tree problem on graphs where we are given a set of nodes. The goal is to find a tree sub-graph that contains all nodes in the given set, potentially including additional nodes.
• Score: 0.47138177023764655
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Decision-focused Graph Neural Networks for Combinatorial Optimization [62.34623670845006]
  An emerging strategy to tackle optimization problems involves the adoption of graph neural networks (GNNs) as an alternative to traditional algorithms. Despite the growing popularity of GNNs and traditional algorithm solvers in the realm of CO, there is limited research on their integrated use and the correlation between them within an end-to-end framework. We introduce a decision-focused framework that utilizes GNNs to address CO problems with auxiliary support.
  arXiv  Detail & Related papers  (2024-06-05T22:52:27Z)
• TreeDQN: Learning to minimize Branch-and-Bound tree [78.52895577861327]
  Branch-and-Bound is a convenient approach to solving optimization tasks in the form of Mixed Linear Programs. The efficiency of the solver depends on the branchning used to select a variable for splitting. We propose a reinforcement learning method that can efficiently learn the branching.
  arXiv  Detail & Related papers  (2023-06-09T14:01:26Z)
• Nearly Optimal Steiner Trees using Graph Neural Network Assisted Monte Carlo Tree Search [9.061356032792952]
  We describe an approach for computing Steiner Trees by combining a graph neural network and Monte Carlo Tree Search. We first train a graph neural network that takes as input a partial solution and proposes a new node to be added as output. This neural network is then used in a Monte Carlo search to compute a Steiner tree.
  arXiv  Detail & Related papers  (2023-04-30T17:15:38Z)
• NeuroPrim: An Attention-based Model for Solving NP-hard Spanning Tree Problems [0.0]
  We propose NeuroPrim, a novel framework for solving various spanning tree problems by defining a Decision Process (MDP) for general optimization problems on graphs. We apply our framework to three difficult problems on Euclidean space: the Degree-constrained Minimum Spanning Tree (DCMST) problem, the Minimum Cost Spanning Tree (MRCST) problem, and the Steiner Tree Problem in Routing graphs (STP)
  arXiv  Detail & Related papers  (2022-10-22T13:49:29Z)
• Improved Training of Physics-Informed Neural Networks with Model Ensembles [81.38804205212425]
  We propose to expand the solution interval gradually to make the PINN converge to the correct solution. All ensemble members converge to the same solution in the vicinity of observed data. We show experimentally that the proposed method can improve the accuracy of the found solution.
  arXiv  Detail & Related papers  (2022-04-11T14:05:34Z)
• What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization [8.879790406465556]
  We present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. We also conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. We show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values.
  arXiv  Detail & Related papers  (2022-01-25T17:37:34Z)
• Deep Probabilistic Graph Matching [72.6690550634166]
  We propose a deep learning-based graph matching framework that works for the original QAP without compromising on the matching constraints. The proposed method is evaluated on three popularly tested benchmarks (Pascal VOC, Willow Object and SPair-71k) and it outperforms all previous state-of-the-arts on all benchmarks.
  arXiv  Detail & Related papers  (2022-01-05T13:37:27Z)
• Computing Steiner Trees using Graph Neural Networks [1.0159681653887238]
  In this paper, we tackle the Steiner Tree Problem. We employ four learning frameworks to compute low cost Steiner trees. Our finding suggests that the out-of-the-box application of GNN methods does worse than the classic 2-approximation algorithm.
  arXiv  Detail & Related papers  (2021-08-18T19:55:16Z)
• Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming [0.0]
  Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task. In this work, we propose a new time algorithm for discovering a subset of all possible cluster cuts. We show that, despite being suboptimal, they improve performance by orders of magnitude. The resulting solver also compares favourably with GOBNILP, a state-of-the-art solver for the BNSL problem.
  arXiv  Detail & Related papers  (2021-06-23T09:46:11Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  We propose a hybrid approach to combine the best of the two worlds, in which a bi-level framework is developed with an upper-level learning method to optimize the graph. Such a bi-level approach simplifies the learning on the original hard CO and can effectively mitigate the demand for model capacity.
  arXiv  Detail & Related papers  (2021-06-09T09:18:18Z)
• Learning by Fixing: Solving Math Word Problems with Weak Supervision [70.62896781438694]
  Previous neural solvers of math word problems (MWPs) are learned with full supervision and fail to generate diverse solutions. We introduce a textitweakly-supervised paradigm for learning MWPs. Our method only requires the annotations of the final answers and can generate various solutions for a single problem.
  arXiv  Detail & Related papers  (2020-12-19T03:10:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.