A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems
Motivated by a real-world vehicle routing application, we consider the maximum-weight independent set problem: 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. To solve instances of this size, we develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search (GRASP) framework. This algorithm, which we call METAMIS, uses a wider range of simple local search operations than previously described in the literature. We introduce data structures that make these operations efficient. A new variant of path-relinking is introduced to escape local optima and so is a new alternating augmenting-path local search move that improves algorithm performance. We compare an implementation of our algorithm with a state-of-the-art openly available code on public benchmark sets, including some large instances with hundreds of millions of vertices. Our algorithm is, in general, competitive and outperforms this openly available code on large vehicle routing instances. We hope that our results will lead to even better MWIS algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Markov Chain methods for the bipartite Boolean quadratic programming problem
We study the Bipartite Boolean Quadratic Programming Problem (BBQP) which is an extension of the well known Boolean Quadratic Programming Problem (BQP). Applications of the BBQP include mining discrete patterns from bina…
A proposed method to extract maximum possible power in the shortest time on solar PV arrays under partial shadings using metaheuristic algorithms
The increasing use of fossil fuels to produce energy is leading to environmental problems. Hence, it has led the human society to move towards the use of renewable energies, including solar energy. In recent years, one o…
A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem
Denoising diffusion models (DDMs) offer a promising generative approach for combinatorial optimization, yet they often lack the robust exploration capabilities of traditional metaheuristics like evolutionary algorithms (…
Applications of Nature-Inspired Metaheuristic Algorithms for Tackling Optimization Problems Across Disciplines
Nature-inspired metaheuristic algorithms are important components of artificial intelligence, and are increasingly used across disciplines to tackle various types of challenging optimization problems. This paper demonstr…
Matrix CompletionSolving Weighted Constraint Satisfaction Problems with Memetic/Exact Hybrid Algorithms
A weighted constraint satisfaction problem (WCSP) is a constraint satisfaction problem in which preferences among solutions can be expressed. Bucket elimination is a complete technique commonly used to solve this kind of…