Branch-and-Bound

Concept

Branch-and-bound is a search technique that uses a backtracking search tree to turn a satisfaction problem into an optimization problem by combining recursive subdivision (branching) with pruning via computed bounds. It is a foundational algorithmic pattern used in constraint programming, MaxSAT solving, and neural network verification.

First seen 6/9/2026

Last seen 6/9/2026

Evidence 1 chunks

Wiki v1

WIKI

Overview

Branch-and-bound is a search technique that operates over the backtracking search tree of a constraint-based solver. It is described as "an efficient technique to search for optimality using the search tree," with the search tree itself providing the mechanism to "turn a satisfaction problem into an optimization problem" ^[1].

How it Relates to the Search Tree

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

1 connections

Code Generation for Custom Architectures using Constraint Programming ← uses 90% 1e

Branch-and-bound is used as a technique to search for optimal solutions in the constraint programming framework.

LINKED ENTITIES

1 links

Code Generation for Custom Architectures using Constraint Programming USES Extracted graph relationship

CITATIONS

4 sources

4 citations — click to collapse

[1] The search tree of a constraint solver can be used to turn a satisfaction problem into an optimization problem, and branch-and-bound is an efficient technique to search for optimality using that search tree. Arslan, Mehmet Ali (PhD thesis)

[2] In a constraint solver, guesses are kept as a search tree; variable selection and value selection heuristics decide the shape of the tree, and the solver backtracks from incorrect guesses. Arslan, Mehmet Ali (PhD thesis)

[3] MaxCDCL is the dominant branch-and-bound MaxSAT solver, and proof logging has been added to certify look-ahead methods and MDD-based clausal encodings of pseudo-Boolean constraints, with feasible overhead but proof checking still a challenge. Certified Branch-and-Bound MaxSAT Solving (Extended Version)

[4] BICCOS leverages logical relationships of neurons within verified subproblems in the branch-and-bound search tree, introduces cuts that preclude these relationships in other subproblems, assigns influence scores to neurons per path for cut strengthening, and uses multi-tree search; it is part of the α,β-CROWN verifier (VNN-COMP 2024 winner). Scalable Neural Network Verification with Branch-and-bound Inferred Cutting Planes