A hybrid breakout local search and reinforcement learning approach to the vertex separator problem

DOI10.1016/J.EJOR.2017.01.023MaRDI QIDQ1753627zbMATH OpenOpenAlexFDO

Authors Una Benlic, Michael G. Epitropakis, Edmund K. Burke

Publication date 29 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.ejor.2017.01.023

zbMATH Keywords

heuristicsiterated local searchreinforcement learningvertex separatorparameter control

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Combining intensification and diversification strategies in VNS. An application to the vertex separation problem
• Variable neighborhood search for the vertex separation problem
• A quality and distance guided hybrid algorithm for the vertex separator problem
• Exact algorithms for the vertex separator problem in graphs
• A variable neighborhood search approach for the vertex bisection problem

Cites work

• scientific article; zbMATH DE number 3150484 (Why is no real title available?)
• scientific article; zbMATH DE number 3858396 (Why is no real title available?)
• scientific article; zbMATH DE number 960162 (Why is no real title available?)
• A Separator Theorem for Planar Graphs
• A Spectral Bundle Method for Semidefinite Programming
• A framework for solving VLSI graph layout problems
• A graph partitioning algorithm by node separators
• An Automatic Nested Dissection Algorithm for Irregular Finite Element Problems
• An exact algorithm for solving the vertex separator problem
• Breakout local search for maximum clique problems
• Breakout local search for the quadratic assignment problem
• Continuous quadratic programming formulations of optimization problems on graphs
• Exact algorithms for the vertex separator problem in graphs
• Finding good approximate vertex and edge partitions is NP-hard
• Finding small balanced separators
• Finite-time analysis of the multiarmed bandit problem
• Improved approximation algorithms for minimum-weight vertex separators
• Parameter setting in evolutionary algorithms.
• Partitioning hypergraphs in scientific computing applications through vertex separators on graphs
• Reactive search and intelligent optimization
• Some aspects of the sequential design of experiments
• Statistical mechanics of complex networks
• Sublinear Time Width-Bounded Separators and Their Application to the Protein Side-Chain Packing Problem
• The vertex separator problem: a polyhedral investigation
• The vertex separator problem: algorithms and computations

Cited in

(6)

• Alternative evaluation functions for the cyclic bandwidth sum problem
• Machine learning at the service of meta-heuristics for solving combinatorial optimization problems: a state-of-the-art
• A flow based formulation and a reinforcement learning based strategic oscillation for cross-dock door assignment
• A quality and distance guided hybrid algorithm for the vertex separator problem
• Learning to select operators in meta-heuristics: an integration of Q-learning into the iterated greedy algorithm for the permutation flowshop scheduling problem
• Learning driven three-phase search for the maximum independent union of cliques problem

This page was built for publication: A hybrid breakout local search and reinforcement learning approach to the vertex separator problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1753627)