Ciaran McCreesh
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
Ciaran McCreesh has a total of 9 co-authors. Here are the top co-authors by number of shared publications:
- Patrick Prosser
University of Glasgow
6 shared publications Christine Solnon
INSA-Lyon, LIRIS, UMR5205
2 shared publications- Blair Archibald
School of Computing Science, University of Glasgow, Glasgow, UK
1 shared publication Lars Kotthoff
University of British Columbia
1 shared publication- Patrick Maier
School Of Computing Science University of Glasgow G12 8QQ Scotland
1 shared publication Patrick Prosser
University of Glasgow
1 shared publication
Latest Publications
- Open Access
Replicable Parallel Branch and Bound Search
Combinatorial branch and bound searches are a common technique for solving global optimisation and decision problems. Their performance often depends on good search order heuristics, refined over decades of algorithms research. Parallel search necessarily deviates from the sequential search order, sometimes dramatically and unpredictably, e.g. by distributing work at random. This can disrupt effective search order heuristics and lead to unexpected and highly variable parallel performance. The variability makes it hard to reason about the parallel performance of combinatorial searches. This paper presents a generic parallel branch and bound skeleton, implemented in Haskell, with replicable parallel performance. The skeleton aims to preserve the search order heuristic by distributing work in an ordered fashion, closely following the sequential search order. We demonstrate the generality of the approach by applying the skeleton to 40 instances of three combinatorial problems: Maximum Clique, 0/1 Knapsack and Travelling Salesperson. The overheads of our Haskell skeleton are reasonable: giving slowdown factors of between 1.9 and 6.2 compared with a class-leading, dedicated, and highly optimised C++ Maximum Clique solver. We demonstrate scaling up to 200 cores of a Beowulf cluster, achieving speedups of 100x for several Maximum Clique instances. We demonstrate low variance of parallel performance across all instances of the three combinatorial problems and at all scales up to 200 cores, with median Relative Standard Deviation (RSD) below 2%. Parallel solvers that do not follow the sequential search order exhibit far higher variance, with median RSD exceeding 85% for Knapsack.
Open AccessReplicable Parallel Branch and Bound Search
Combinatorial branch and bound searches are a common technique for solving global optimisation and decision problems. Their performance often depends on good search order heuristics, refined over decades of algorithms research. Parallel search necessarily deviates from the sequential search order, sometimes dramatically and unpredictably, e.g. by distributing work at random. This can disrupt effective search order heuristics and lead to unexpected and highly variable parallel performance. The variability makes it hard to reason about the parallel performance of combinatorial searches. This paper presents a generic parallel branch and bound skeleton, implemented in Haskell, with replicable parallel performance. The skeleton aims to preserve the search order heuristic by distributing work in an ordered fashion, closely following the sequential search order. We demonstrate the generality of the approach by applying the skeleton to 40 instances of three combinatorial problems: Maximum Clique, 0/1 Knapsack and Travelling Salesperson. The overheads of our Haskell skeleton are reasonable: giving slowdown factors of between 1.9 and 6.2 compared with a class-leading, dedicated, and highly optimised C++ Maximum Clique solver. We demonstrate scaling up to 200 cores of a Beowulf cluster, achieving speedups of 100x for several Maximum Clique instances. We demonstrate low variance of parallel performance across all instances of the three combinatorial problems and at all scales up to 200 cores, with median Relative Standard Deviation (RSD) below 2%. Parallel solvers that do not follow the sequential search order exhibit far higher variance, with median RSD exceeding 85% for Knapsack.
- 23 August 2016
- Published by Springer Nature
- p. 350-368
Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems
- 23 August 2016
- Published by Springer Nature
- p. 350-368
Clique and Constraint Models for Maximum Common (Connected) Subgraph Problems
- 13 August 2015
- Published by Springer Nature
- p. 295-312
A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs
- 13 August 2015
- Published by Springer Nature
- p. 295-312
A Parallel, Backjumping Subgraph Isomorphism Algorithm Using Supplemental Graphs
- Open Access
- 10 December 2014
- Published by Springer Nature in Optimization Letters
- Vol. 9 (5) , 949-960
A parallel branch and bound algorithm for the maximum labelled clique problem
- 10 December 2014
- Published by Springer Nature in Optimization Letters
- Vol. 9 (5) , 949-960
Open AccessA parallel branch and bound algorithm for the maximum labelled clique problem
- Open Access
A Parallel Branch and Bound Algorithm for the Maximum Labelled Clique Problem
The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.
Open AccessA Parallel Branch and Bound Algorithm for the Maximum Labelled Clique Problem
The maximum labelled clique problem is a variant of the maximum clique problem where edges in the graph are given labels, and we are not allowed to use more than a certain number of distinct labels in a solution. We introduce a new branch-and-bound algorithm for the problem, and explain how it may be parallelised. We evaluate an implementation on a set of benchmark instances, and show that it is consistently faster than previously published results, sometimes by four or five orders of magnitude.
- Open Access
The Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound
Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core thread-parallel adaptations of a state-of-the-art branch and bound algorithm for the maximum clique problem, and provide a novel explanation as to why they are successful. We show that load balance is sometimes a problem, but that the interaction of parallel search order and the most likely location of solutions within the search space is often the dominating consideration. We use this explanation to propose a new low-overhead, scalable work splitting mechanism. Our approach uses explicit early diversity to avoid strong commitment to the weakest heuristic advice, and late resplitting for balance. More generally, we argue that for branch and bound, parallel algorithm design should not be performed independently of the underlying sequential algorithm.
Open AccessThe Shape of the Search Tree for the Maximum Clique Problem, and the Implications for Parallel Branch and Bound
Finding a maximum clique in a given graph is one of the fundamental NP-hard problems. We compare two multi-core thread-parallel adaptations of a state-of-the-art branch and bound algorithm for the maximum clique problem, and provide a novel explanation as to why they are successful. We show that load balance is sometimes a problem, but that the interaction of parallel search order and the most likely location of solutions within the search space is often the dominating consideration. We use this explanation to propose a new low-overhead, scalable work splitting mechanism. Our approach uses explicit early diversity to avoid strong commitment to the weakest heuristic advice, and late resplitting for balance. More generally, we argue that for branch and bound, parallel algorithm design should not be performed independently of the underlying sequential algorithm.
- Open Access
Finding Maximum k-Cliques Faster using Lazy Global Domination
A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem. We use a state of the art maximum clique algorithm to show that this is feasible in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs.
Open AccessFinding Maximum k-Cliques Faster using Lazy Global Domination
A clique in a graph is a set of vertices, each of which is adjacent to every other vertex in this set. A k-clique relaxes this requirement, requiring vertices to be within a distance k of each other, rather than directly adjacent. In theory, a maximum clique algorithm can easily be adapted to solve the maximum k-clique problem. We use a state of the art maximum clique algorithm to show that this is feasible in practice, and introduce a lazy global domination rule which sometimes vastly reduces the search space. We include experimental results for a range of real-world and benchmark graphs, and a detailed look at random graphs.
- Open Access
- 3 October 2013
- Published by MDPI AG in Algorithms
- Vol. 6 (4) , 618-635
Multi-Threading a State-of-the-Art Maximum Clique Algorithm
We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear speedups are common. We include results for several previously unsolved benchmark problems.
- 3 October 2013
- Published by MDPI AG in Algorithms
- Vol. 6 (4) , 618-635
Open AccessMulti-Threading a State-of-the-Art Maximum Clique Algorithm
We present a threaded parallel adaptation of a state-of-the-art maximum clique algorithm for dense, computationally challenging graphs. We show that near-linear speedups are achievable in practice and that superlinear speedups are common. We include results for several previously unsolved benchmark problems.