Two novel branch and bound algorithms for the vertex bisection problem. (15th March 2022)

• Record Type: Journal Article
• Authors: Soto, Carlos; Ángel-Martínez, Eduardo Del; Fraire-Huacuja, Héctor; Dorronsoro, Bernabe; Rangel, Nelson; Cruz-Reyes, Laura
• Is Part Of: Expert systems with applications. Volume 190(2022)
• Publication Date: 2022-03-15
• Subjects: Vertex bisection problem -- B&B -- Upper bound -- Lower bound -- Constructive heuristic; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2021.116169
• Languages: English
• ISSNs: 0957-4174

Abstract

Abstract: 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. Highlights: 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.