Breakout local search for the cyclic cutwidth minimization problem

The cyclic cutwidth minimization problem (CCMP) is a graph layout problem that involves embedding a graph onto a circle to minimize the maximum cutwidth of the graph. In this paper, we present breakout local search (BLS) for solving CCMP, which combines a dedicated local search procedure to discover...

Full description

Saved in:
Bibliographic Details
Published in:Journal of heuristics 2022-12, Vol.28 (5-6), p.583-618
Main Authors: He, Mu, Wu, Qinghua, Lu, Yongliang
Format: Article
Language:English
Subjects:
Algorithms
Artificial Intelligence
Calculus of Variations and Optimal Control
Optimization
Computing time
Graphs
Heuristic
Management Science
Mathematics
Mathematics and Statistics
Operations Research
Operations Research/Decision Theory
Optimization
Searching
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The cyclic cutwidth minimization problem (CCMP) is a graph layout problem that involves embedding a graph onto a circle to minimize the maximum cutwidth of the graph. In this paper, we present breakout local search (BLS) for solving CCMP, which combines a dedicated local search procedure to discover high-quality local optimal solutions and an adaptive diversification strategy to escape from local optima. Extensive computational results on a wide set of 179 publicly available benchmark instances show that the proposed BLS algorithm has excellent performance with respect to the best-performing state-of-the-art approaches in terms of solution quality and computational time. In particular, it reports improved best-known solutions for 31 instances, while finding matching best-known results on 139 instances.
ISSN:1381-1231
1572-9397
DOI:10.1007/s10732-022-09504-5