Branch & Bound in Combinatorial Optimization: A State-Space Framework and Computational Study

Branch-and-bound (B&B) is an implicit enumeration algorithm in which the solution space is recursively partitioned and explored through bounding and pruning. Although frequently discussed in the context of Mixed-Integer Linear Programming (MILP), B&B is not limited to that scope. As a general procedure, it can solve combinatorial optimization problems when deriving problem-specific bounds, branching rules, and pruning strategies. Some of the most successful applications involve scheduling and graph problems. This paper presents bnbpy, a state-space customizable framework that aims to foster the implementation of problem-specific B&B algorithms. As case studies, B&B implementations for the Maximum Clique Problem (MCP), the Single-Machine Sequencing with Deadlines (SMSD), and the Permutation Flowshop Scheduling Problem (PFSP) are provided, showing that the problem-specific B&B implementations can outperform commercial MILP solvers by orders of magnitude.