Branch and Bound

Branching is the process of recursively partitioning the feasible solution space into smaller, mutually exclusive subproblems. This creates a decision tree where each node represents a constrained subset of the original problem.

• Variable Diving: A common strategy selects a fractional integer variable and creates two child nodes by rounding it down and up.
• Depth-First vs. Best-First: The search strategy dictates which node to explore next. Best-first prioritizes nodes with the most promising bound.
• Constraint Propagation: After branching, logical deductions immediately reduce the domains of other variables, shrinking the subproblem before solving.

Bounding computes a numerical limit on the best possible solution obtainable within a given subproblem. Pruning discards a subproblem entirely if its bound proves it cannot improve upon the current best-known feasible solution, the incumbent.

• Relaxation: The bound is typically found by solving a relaxed, easier version of the problem, such as the Linear Programming (LP) Relaxation of a Mixed-Integer Linear Programming (MILP) model.
• Pruning by Optimality: If a subproblem's relaxation yields an integer-feasible solution, it is a candidate optimum for that branch.
• Pruning by Infeasibility: If the relaxed subproblem has no solution, the branch itself is infeasible and is pruned.

The incumbent is the best integer-feasible solution found at any point during the search. It provides a dynamic global upper bound (for minimization) that drives pruning efficiency.

• Warm Starts: Providing a high-quality initial incumbent via a heuristic like Adaptive Large Neighborhood Search (ALNS) can dramatically accelerate the algorithm by pruning more nodes early.
• Absolute vs. Relative Gap: The algorithm terminates when the difference between the incumbent and the best remaining node bound falls below a specified MIP gap tolerance, proving optimality within that threshold.

The order in which subproblems are explored critically impacts memory usage and time-to-solution. Modern solvers like Gurobi and OR-Tools use sophisticated hybrid strategies.

• Best-Bound First: Selects the node with the most optimistic bound, minimizing total nodes explored but consuming more memory to store the active node list.
• Depth-First Search: Plunges deep into the tree quickly to find a new incumbent, which is memory-efficient and crucial for large-scale problems.
• Hybrid Interleaving: Commercial solvers dynamically switch between strategies, often starting with depth-first to find a good incumbent, then switching to best-bound to close the optimality gap.

Modern Branch and Bound is almost always combined with Cutting Plane methods to form the Branch and Cut algorithm, the backbone of industrial MILP solvers.

• Gomory Cuts: Generated from the simplex tableau to eliminate fractional LP solutions without removing any integer-feasible points.
• Clique Cuts: Derived from the constraint matrix structure to tighten the LP relaxation's formulation of binary variables.
• Separation Problem: The solver iteratively solves a subproblem to find a violated valid inequality, adds it as a cut, and re-optimizes the LP relaxation, tightening the bound before any branching decision.

Branch and Bound (and Branch and Cut) is the core exact engine for solving Capacitated VRP (CVRP) and Pickup and Delivery Problems (PDP) to proven optimality for small-to-medium instances.

• Set Partitioning Formulation: A common VRP model where each variable represents a feasible route. Column Generation is used to dynamically generate these route variables, while Branch and Bound enforces integer selection of routes.
• Branching on Arcs: Instead of branching on route variables, the algorithm can branch on the flow on a specific edge in the transportation network, forcing it to be used or not.
• Constraint Programming Hybrids: For highly constrained problems like the Dial-a-Ride Problem (DARP) with complex time windows, Branch and Bound is integrated with Constraint Programming propagation for logical scheduling constraints.