Advanced Kernel Search approach for the MST Problem with conflicts involving affinity detection and initial solution construction

• URL: http://arxiv.org/abs/2401.02222v2
• Date: Tue, 10 Jun 2025 16:39:37 GMT
• Title: Advanced Kernel Search approach for the MST Problem with conflicts involving affinity detection and initial solution construction
• Authors: Francesco Carrabs, Martina Cerulli, Domenico Serra,
• Abstract summary: We use an enhanced Kernel Search method to solve the Minimum Spanning Tree Problem with Conflicts.<n>We integrate the computation of independent sets from the conflict graph within the algorithm to detect affinities and effectively manage conflicts.<n>Although our methodology is designed for MSTC, its principles could be extended to other optimization problems with conflicts.
• 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 an enhanced Kernel Search method, which iteratively solves refined problem restrictions. Our approach addresses two central open questions in the kernel search literature: (1) how to determine the affinity between variables to ensure that the restricted problem contains variables that are as compatible as possible, meaning they are more likely to appear together in a feasible solution, and (2) how to construct an initial feasible solution quickly. To this end, we integrate the computation of independent sets from the conflict graph within the algorithm to detect affinities and effectively manage conflicts. Furthermore, we heuristically construct an initial starting point, significantly accelerating the computational process. Although our methodology is designed for MSTC, its principles could be extended to other combinatorial optimization problems with conflicts. Experimental results on benchmark instances demonstrate the efficiency and competitiveness of our approach compared to existing methods in the literature, achieving 17 new best-known values.

Related papers

• Improved Algorithms for Overlapping and Robust Clustering of Edge-Colored Hypergraphs: An LP-Based Combinatorial Approach [0.0]
  edge-colored clustering (ECC) has emerged as a useful approach for handling categorical data.<n>To tackle these limitations, three versions of ECC have been studied.<n>We present an algorithmic framework that combines the strengths of LP with the computational efficiency of algorithms.
  arXiv  Detail & Related papers  (2025-05-23T15:46:16Z)
• Optimal Multi-Objective Best Arm Identification with Fixed Confidence [62.36929749450298]
  We consider a multi-armed bandit setting in which each arm yields an $M$-dimensional vector reward upon selection. The end goal is to identify the best arm of em every objective in the shortest (expected) time subject to an upper bound on the probability of error. We propose an algorithm that uses the novel idea of em surrogate proportions to sample the arms at each time step, eliminating the need to solve the max-min optimisation problem at each step.
  arXiv  Detail & Related papers  (2025-01-23T12:28:09Z)
• 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)
• 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)
• BalMCTS: Balancing Objective Function and Search Nodes in MCTS for Constraint Optimization Problems [7.196057722218442]
  Constraint Problems Optimization (COP) pose intricate challenges in problems usually addressed through Branch and Bound (B&B) methods. We propose a novel neural network algorithm based on a depth-first search algorithm for solving COP. Our method identifies feasible solutions with a gap of less than 17.63% within the initial 5 feasible solutions.
  arXiv  Detail & Related papers  (2023-12-26T03:09:08Z)
• 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)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• 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)
• Learning Primal Heuristics for Mixed Integer Programs [5.766851255770718]
  We investigate whether effective primals can be automatically learned via machine learning. We propose a new method to represent an optimization problem as a graph, and train a Graph Conal Network on solved problem instances with known optimal solutions. The prediction of variable solutions is then leveraged by a novel configuration of the B&B method, Probabilistic Branching with guided Depth-first Search.
  arXiv  Detail & Related papers  (2021-07-02T06:46:23Z)
• 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)
• Revisiting the Complexity Analysis of Conflict-Based Search: New Computational Techniques and Improved Bounds [5.158632635415881]
  State-of-the-art approach to computing optimal solutions is Conflict-Based Search (CBS) We revisit the complexity analysis of CBS to provide tighter bounds on the algorithm's run-time in the worst-case.
  arXiv  Detail & Related papers  (2021-04-18T07:46:28Z)
• 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)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  Bipartite b-matching is fundamental in algorithm design, and has been widely applied into economic markets, labor markets, etc. Existing exact and approximate algorithms usually fail in such settings due to either requiring intolerable running time or too much computation resource. We propose textttNeuSearcher which leverages the knowledge learned from previously instances to solve new problem instances.
  arXiv  Detail & Related papers  (2020-05-09T02:48:23Z)
• 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)
• Learning High Order Feature Interactions with Fine Control Kernels [12.5433010409486]
  We provide a methodology for learning sparse statistical models that use as features all possible multiplicative interactions. We also introduce an algorithmic paradigm, the Fine Control Kernel framework, so named because it is based on Fenchel Duality.
  arXiv  Detail & Related papers  (2020-02-09T06:29:15Z)

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.