Supporting material
The Vertex Separator Problem (VSP) is an NP-hard problem which arises from several important domains and applications. In this paper, we present an improved Breakout Local Search for VSP (named BLS-RLE). The distinguishing feature of BLS-RLE is a new parameter control mechanism that draws upon ideas from reinforcement learning theory for an interdependent decision on the number and on the type of perturbation moves. The mechanism complies with the principle ``intensification first, minimal diversification only if needed'', and uses a dedicated sampling strategy for a rapid convergence towards a limited set of parameter values that appear to be the most convenient for the given state of search. Extensive experimental evaluations and statistical comparisons on a wide range of benchmark instances show significant improvement in performance of the proposed algorithm over the existing BLS algorithm for VSP. Indeed, out of the 422 tested instances, BLS-RLE was able to attain the best-known solution in 93.8% of the cases, which is around 20% higher compared to the existing BLS. In addition, we provide detailed analyses to evaluate the importance of the key elements of the proposed method and to justify the degree of diversification introduced during perturbation.
| Benchmark set B1: The ISPD98 Circuit Benchmark Suite (~27M) | Download B1 |
| Benchmark set B2: Scale-free network graphs generated with the Barabasi-Albert model (~90M) | Download B2 |
| Benchmark set B3: Exponential network graphs generated by the Erdos-Renyi model (~67M) | Download B3 |
| Benchmark set B4: Graphs from the Stanford SNAP database and the University of Florida Sparse Matrix Collection (~16M) | Download B4 |
| Benchmark set B5: Toroidal, planar, and random graphs (~2.1M) | Download B5 |
This website was created to accompany our submission, which is currently under review. In its present form it only provides results from our analysis, that could not be fitted into the page limits of the paper.
The following tables show comprehensive experimental results between all implemented algorithms for all benchmark instances used in the article.
To indicate the best performing cases, we highlight the cases with minimal objective value with boldface font.
Copyright 2015, Michael G. Epitropakis, Una Benlic, and Edmund K. Burke. All rights reserved.
Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met:
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
The views and conclusions contained in the software and documentation are those of the authors and should not be interpreted as representing official policies, either expressed or implied, of the FreeBSD Project.
(This is the so-called Simplified BSD License AKA FreeBSD License)
| The source code ncludes the following algorithms: BLS-RLE, BLS-Original, BLS-Random, ILS-TABU, ILS-RND | Download Source Code |
For any further inquiries about the manuscript please contact Michael G. Epitropakis or Una Belnic.
This project was supported by the EPSRC grant, EP/J017515/1 (DAASE: Dynamic Adaptive Automated Software Engineering).