Can I read SAT-and-Reduce for Vertex Cover: Accelerating Branch-and-Reduce by SAT Solving on EtoBox?

SAT-and-Reduce for Vertex Cover: Accelerating Branch-and-Reduce by SAT Solving by Rick Plachetta; Alexander van der Grinten is a book available to read on EtoBox.

What is SAT-and-Reduce for Vertex Cover: Accelerating Branch-and-Reduce by SAT Solving about?

Kernelization, i.e., the use of reduction rules to simplify a problem instance, is known to be highly successful for the VertexCover problem, both in theory and in practice. State-of-the-art solvers for VertexCover generally perform reductions, followed by a Branchand-Bound algorithm on the kernelized instance. In fact, all top-3 solvers of the recent PACE 2019 challenge on VertexCover exploit this strategy. Branchand-Reduce algorithms, i.e., extensions of Branch-and-Bound that perform reductions in each branch of the search tree, are known to solve some instances very well; however, they are not competitive with the best Branchand-Bound solvers on kernelized instances.In this paper, we identify a critical bottleneck of Branch-and-Reduce algorithms, namely that on hard instances, many applications of reduction rules do not help to discard branches (even if the problem size is reduced considerably). Based on this observation, we design an algorithm that exploits a SAT solver to discard branches before significant amounts of ineffective reductions are applied. Our algorithm, which we term "SATand-Reduce", generally runs a Branch-and-Reduce procedure. Before branching, we call into th

Author

Rick Plachetta; Alexander van der Grinten

Publisher

Society for Industrial and Applied Mathematics

Published

2021

Language

EN