Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs
- URL: http://arxiv.org/abs/2401.02222v1
- Date: Thu, 4 Jan 2024 12:10:39 GMT
- Title: Kernel Search approach to solve the Minimum Spanning Tree Problem with conflicting edge pairs
- Authors: Francesco Carrabs, Martina Cerulli, Domenico Serra,
- Abstract summary: In this paper, we solve the Minimum Spanning Tree Problem with Conflicts using a tailored Kernel Search method.
The main novelty of the approach consists in using an independent set of the conflict graph within the algorithm.
- Score: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The Minimum Spanning Tree Problem with Conflicts consists in finding the minimum conflict-free spanning tree of a graph, i.e., the spanning tree of minimum cost, including no pairs of edges that are in conflict. In this paper, we solve this problem using a tailored Kernel Search heuristic method, which consists in solving iteratively improved restrictions of the problem. The main novelty of the approach consists in using an independent set of the conflict graph within the algorithm. We test our approach on the benchmark instances and we compare our results with the ones obtained by other heuristics available in the literature.
Related papers
- Query-decision Regression between Shortest Path and Minimum Steiner Tree [20.092639310758145]
This paper focuses on the shortest path problem and the minimum Steiner tree problem.
We provide theoretical insights regarding the design of realizable hypothesis spaces for building scoring models.
Our experimental studies show that such problems can be solved to a decent extent with statistical significance.
arXiv Detail & Related papers (2024-02-03T17:05:01Z) - Best Arm Identification with Fixed Budget: A Large Deviation Perspective [54.305323903582845]
We present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
In particular, we present sred, a truly adaptive algorithm that can reject arms in it any round based on the observed empirical gaps between the rewards of various arms.
arXiv Detail & Related papers (2023-12-19T13:17:43Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods.
Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem.
As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
arXiv Detail & Related papers (2023-10-08T23:39:38Z) - 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) - 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) - Learning to Prune Instances of Steiner Tree Problem in Graphs [0.47138177023764655]
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.
arXiv Detail & Related papers (2022-08-25T10:31:00Z) - 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) - An Asymptotically Optimal Primal-Dual Incremental Algorithm for
Contextual Linear Bandits [129.1029690825929]
We introduce a novel algorithm improving over the state-of-the-art along multiple dimensions.
We establish minimax optimality for any learning horizon in the special case of non-contextual linear bandits.
arXiv Detail & Related papers (2020-10-23T09:12:47Z) - Exploring search space trees using an adapted version of Monte Carlo
tree search for combinatorial optimization problems [0.6882042556551609]
This approach makes use of a algorithm to explore the search space tree of a problem instance.
The algorithm is based on Monte Carlo tree search, a popular algorithm in game playing that is used to explore game trees.
arXiv Detail & Related papers (2020-10-22T08:33:58Z) - Hardness of Random Optimization Problems for Boolean Circuits,
Low-Degree Polynomials, and Langevin Dynamics [78.46689176407936]
We show that families of algorithms fail to produce nearly optimal solutions with high probability.
For the case of Boolean circuits, our results improve the state-of-the-art bounds known in circuit complexity theory.
arXiv Detail & Related papers (2020-04-25T05:45:59Z)
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.