ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set

• URL: http://arxiv.org/abs/2208.07777v3
• Date: Wed, 16 Apr 2025 18:08:04 GMT
• Title: ARES: An Efficient Algorithm with Recurrent Evaluation and Sampling-Driven Inference for Maximum Independent Set
• Authors: Enqiang Zhu, Yu Zhang, Witold Pedrycz, Chanjuan Liu,
• Abstract summary: This paper introduces an efficient algorithm for the Maximum Independent Set (MIS) problem, incorporating two innovative techniques.<n>The proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.
• Score: 48.57120672468062
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Maximum Independent Set (MIS) problem is a well-known NP-complete problem with a wide range of applications across various fields. Heuristic approaches are commonly utilized to efficiently tackle large instances of this problem, yielding high-quality solutions within a reasonable time. However, heuristics face challenges such as falling into local optima and redundant searches within the solution space. This paper introduces an efficient heuristic algorithm for the MIS problem, incorporating two innovative techniques. The first technique features a recurrent evaluation mechanism that monitors the progress of solutions and identifies local optima, triggering restarts to avoid convergence on suboptimal outcomes. The second technique utilizes a sampling-driven inference rule to selectively fix vertices based on sampled solutions, thereby narrowing the search space and enhancing efficiency. Comprehensive experimental evaluations across multiple well-established real-world benchmarks demonstrate that the proposed algorithm outperforms state-of-the-art algorithms in terms of solution quality, computational efficiency, and stability.

Related papers

• Learning-guided iterated local search for the minmax multiple traveling salesman problem [13.924692115320553]
  We propose a leaning-driven iterated local search approach to the minmax multiple traveling salesman problem. We show that our algorithm achieves excellent results in terms of solution quality and running time. In particular, it achieves 32 new best-known results and matches the best-known results for 35 other instances.
  arXiv  Detail & Related papers  (2024-03-19T02:57:10Z)
• Dynamic Incremental Optimization for Best Subset Selection [15.8362578568708]
  Best subset selection is considered the gold standard for many learning problems. An efficient subset-dual algorithm is developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2024-02-04T02:26:40Z)
• Quality-Diversity Algorithms Can Provably Be Helpful for Optimization [24.694984679399315]
  Quality-Diversity (QD) algorithms aim to find a set of high-performing, yet diverse solutions. This paper tries to shed some light on the optimization ability of QD algorithms via rigorous running time analysis.
  arXiv  Detail & Related papers  (2024-01-19T07:40:24Z)
• 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)
• New Characterizations and Efficient Local Search for General Integer Linear Programming [17.80124240223163]
  This work proposes new characterizations of linear programming (ILP) with the concept of boundary solutions. We develop a new local search algorithm Local-ILP, which is efficient for solving general ILP validated on a large heterogeneous problem dataset. Experiments conducted on the MIPLIB dataset show the effectiveness of our algorithm in solving large-scale hard ILP problems.
  arXiv  Detail & Related papers  (2023-04-29T07:22:07Z)
• Best Subset Selection with Efficient Primal-Dual Algorithm [24.568094642425837]
  Best subset selection is considered the gold standard' for many learning problems. In this paper, we investigate the dual forms of a family of $ell$-regularized problems. An efficient primal-dual method has been developed based on the primal and dual problem structures.
  arXiv  Detail & Related papers  (2022-07-05T14:07:52Z)
• A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
  Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
  arXiv  Detail & Related papers  (2022-03-28T21:34:16Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• PAMELI: A Meta-Algorithm for Computationally Expensive Multi-Objective Optimization Problems [0.0]
  The proposed algorithm is based on solving a set of surrogate problems defined by models of the real one. Our algorithm also performs a meta-search for optimal surrogate models and navigation strategies for the optimization landscape.
  arXiv  Detail & Related papers  (2021-03-19T11:18:03Z)
• Learning to Schedule Heuristics in Branch-and-Bound [25.79025327341732]
  Real-world applications typically require finding good solutions early in the search to enable fast decision-making. We propose the first data-driven framework for schedulings in an exact MIP solver. Compared to the default settings of a state-of-the-art academic MIP solver, we are able to reduce the average primal integral by up to 49% on a class of challenging instances.
  arXiv  Detail & Related papers  (2021-03-18T14:49:52Z)
• A Two-stage Framework and Reinforcement Learning-based Optimization Algorithms for Complex Scheduling Problems [54.61091936472494]
  We develop a two-stage framework, in which reinforcement learning (RL) and traditional operations research (OR) algorithms are combined together. The scheduling problem is solved in two stages, including a finite Markov decision process (MDP) and a mixed-integer programming process, respectively. Results show that the proposed algorithms could stably and efficiently obtain satisfactory scheduling schemes for agile Earth observation satellite scheduling problems.
  arXiv  Detail & Related papers  (2021-03-10T03:16:12Z)
• Resource Allocation via Model-Free Deep Learning in Free Space Optical Communications [119.81868223344173]
  The paper investigates the general problem of resource allocation for mitigating channel fading effects in Free Space Optical (FSO) communications. Under this framework, we propose two algorithms that solve FSO resource allocation problems.
  arXiv  Detail & Related papers  (2020-07-27T17:38:51Z)
• Combining Deep Learning and Optimization for Security-Constrained Optimal Power Flow [94.24763814458686]
  Security-constrained optimal power flow (SCOPF) is fundamental in power systems. Modeling of APR within the SCOPF problem results in complex large-scale mixed-integer programs. This paper proposes a novel approach that combines deep learning and robust optimization techniques.
  arXiv  Detail & Related papers  (2020-07-14T12:38:21Z)
• The limits of min-max optimization algorithms: convergence to spurious non-critical sets [82.74514886461257]
  min-max optimization algorithms encounter problems far greater because of the existence of periodic cycles and similar phenomena. We show that there exist algorithms that do not attract any points of the problem. We illustrate such challenges in simple to almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost almost
  arXiv  Detail & Related papers  (2020-06-16T10:49:27Z)
• Beyond Worst-Case Analysis in Stochastic Approximation: Moment Estimation Improves Instance Complexity [58.70807593332932]
  We study oracle complexity of gradient based methods for approximation problems. We focus on instance-dependent complexity instead of worst case complexity. Our proposed algorithm and its analysis provide a theoretical justification for the success of moment estimation.
  arXiv  Detail & Related papers  (2020-06-08T09:25:47Z)
• 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)
• Extreme Algorithm Selection With Dyadic Feature Representation [78.13985819417974]
  We propose the setting of extreme algorithm selection (XAS) where we consider fixed sets of thousands of candidate algorithms. We assess the applicability of state-of-the-art AS techniques to the XAS setting and propose approaches leveraging a dyadic feature representation.
  arXiv  Detail & Related papers  (2020-01-29T09:40:58Z)

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.