Two novel branch and bound algorithms for the vertex bisection problem.

In this paper, we address the exact solution of the vertex bisection problem (VBP). We propose two novel B&B algorithms to solve VBP, which include new upper and lower bound constructive heuristics, and an efficient strategy to explore the combinatorial search space. The computational results show that the proposed algorithms clearly outperforms the state-of-the-art B&B algorithm in quality and efficiency. The two proposed B&B versions differ in the exploration strategy and the storage of the search tree. Also, we provide four new solutions, previously unknown. We consider that the main contributions of this work can be adapted to solve combinatorial problems in other related domains. • Two representations of the search tree for the branch and bound algorithm. • Two new greedy constructive heuristics for the vertex bisection problem. • A new lower bound computation for the vertex bisection problem. • New optimal solutions for four Harwell–Boing instances. [ABSTRACT FROM AUTHOR]