842 Advanced

Branch and Bound

Functional Programming

Tutorial Video

Text description (accessibility)

This video demonstrates the "Branch and Bound" functional Rust example. Difficulty level: Advanced. Key concepts covered: Functional Programming. Backtracking explores the complete search space but doesn't use bounds to prune. Key difference from OCaml: | Aspect | Rust | OCaml |

Tutorial

The Problem

Backtracking explores the complete search space but doesn't use bounds to prune. Branch and bound adds an upper/lower bound computation at each node: if the best possible solution achievable from a partial assignment cannot beat the current best complete solution, prune that entire subtree. This makes branch and bound the algorithm of choice for exact optimization: integer linear programming, traveling salesman problem (with bounds from relaxations), knapsack (with greedy fractional bound), and scheduling optimization. While still exponential in the worst case, good bounds make it practical for real instances that pure backtracking cannot handle.

🎯 Learning Outcomes

• Understand the bounding function: optimistic estimate of best achievable value from a partial solution

• Implement the branch-and-bound template: branch into children, compute bound, prune if bound ≤ best

• Apply to 0/1 knapsack with fractional relaxation bound (greedily pack remaining items fractionally)

• Recognize the tradeoff: tighter bounds → more pruning → faster → more expensive to compute

• Compare with dynamic programming: DP is exact and polynomial for knapsack; B&B is exact but can prune large trees

Code Example

#![allow(clippy::all)]
//! Placeholder

(* Branch and Bound — TSP in OCaml *)
(* Uses a simple lower bound: sum of two cheapest outgoing edges per node *)

let inf = max_int / 2

(* Simple lower bound for TSP: for each unvisited node, add half the sum
   of its two cheapest edges to any other unvisited node or path endpoints *)
let lower_bound (dist : int array array) (path : int list) (n : int) : int =
  let visited = Array.make n false in
  List.iter (fun v -> visited.(v) <- true) path;
  (* Current path length *)
  let path_cost = ref 0 in
  let rec sum_path = function
    | [] | [_] -> ()
    | a :: (b :: _ as rest) -> path_cost := !path_cost + dist.(a).(b); sum_path rest
  in
  sum_path (List.rev path);
  (* For unvisited nodes + endpoints: add min edge cost *)
  let bound = ref !path_cost in
  for v = 0 to n - 1 do
    if not visited.(v) || v = List.hd path || v = List.hd (List.rev path) then begin
      let edges = Array.init n (fun u ->
        if u = v then inf
        else if visited.(u) && u <> List.hd path && u <> List.hd (List.rev path) then inf
        else dist.(v).(u)
      ) in
      Array.sort compare edges;
      let e1 = edges.(0) and e2 = if Array.length edges > 1 then edges.(1) else 0 in
      if e1 < inf then bound := !bound + (e1 + e2) / 2
    end
  done;
  !bound

(* Branch and Bound TSP solver *)
let tsp_bnb (dist : int array array) : int * int list =
  let n = Array.length dist in
  let best_cost = ref inf in
  let best_path = ref [] in
  let rec bnb path visited cost =
    let path_len = List.length path in
    if path_len = n then begin
      (* Complete tour: add return to start *)
      let total = cost + dist.(List.hd path).(List.hd (List.rev path)) in
      if total < !best_cost then begin
        best_cost := total;
        best_path := List.rev path
      end
    end else begin
      for v = 0 to n - 1 do
        if not visited.(v) then begin
          let new_cost = cost + dist.(List.hd path).(v) in
          (* Simple pruning: current cost already exceeds best *)
          if new_cost < !best_cost then begin
            visited.(v) <- true;
            bnb (v :: path) visited new_cost;
            visited.(v) <- false  (* backtrack *)
          end
        end
      done
    end
  in
  let visited = Array.make n false in
  visited.(0) <- true;
  bnb [0] visited 0;
  (!best_cost, !best_path)

let () =
  (* Small 4-city example *)
  let dist = [|
    [| 0; 10; 15; 20 |];
    [| 10; 0; 35; 25 |];
    [| 15; 35; 0; 30 |];
    [| 20; 25; 30; 0 |];
  |] in
  let (cost, path) = tsp_bnb dist in
  Printf.printf "TSP optimal cost: %d\n" cost;
  Printf.printf "Tour: %s\n"
    (String.concat " -> " (List.map string_of_int path) ^ " -> 0")

Key Differences

Aspect	Rust	OCaml
Search strategy	DFS (stack-based) or BFS	Same options
Best tracking	`mut f64` variable	`float ref`
Bounding function	Nested `fn bound`	Nested `let bound` or separate
Priority queue	`BinaryHeap` for best-first	`Heap` module or priority list
Sorting	`sort_by` with `partial_cmp`	`List.sort` with comparison
Integer variant	`u64` items and capacity	`int` items

OCaml Approach

OCaml's branch-and-bound uses a priority queue (BFS with best-first search) or a recursive DFS. The bound function mirrors the Rust fractional knapsack. OCaml's List.sort sorts items by ratio. The Queue.t or Heap module implements BFS order. Mutable best ref tracks the current best. OCaml's tail-recursive DFS avoids stack overflow for deep trees. The List.fold_left accumulates the bound computation.

Full Source

#![allow(clippy::all)]
//! Placeholder

(* Branch and Bound — TSP in OCaml *)
(* Uses a simple lower bound: sum of two cheapest outgoing edges per node *)

let inf = max_int / 2

(* Simple lower bound for TSP: for each unvisited node, add half the sum
   of its two cheapest edges to any other unvisited node or path endpoints *)
let lower_bound (dist : int array array) (path : int list) (n : int) : int =
  let visited = Array.make n false in
  List.iter (fun v -> visited.(v) <- true) path;
  (* Current path length *)
  let path_cost = ref 0 in
  let rec sum_path = function
    | [] | [_] -> ()
    | a :: (b :: _ as rest) -> path_cost := !path_cost + dist.(a).(b); sum_path rest
  in
  sum_path (List.rev path);
  (* For unvisited nodes + endpoints: add min edge cost *)
  let bound = ref !path_cost in
  for v = 0 to n - 1 do
    if not visited.(v) || v = List.hd path || v = List.hd (List.rev path) then begin
      let edges = Array.init n (fun u ->
        if u = v then inf
        else if visited.(u) && u <> List.hd path && u <> List.hd (List.rev path) then inf
        else dist.(v).(u)
      ) in
      Array.sort compare edges;
      let e1 = edges.(0) and e2 = if Array.length edges > 1 then edges.(1) else 0 in
      if e1 < inf then bound := !bound + (e1 + e2) / 2
    end
  done;
  !bound

(* Branch and Bound TSP solver *)
let tsp_bnb (dist : int array array) : int * int list =
  let n = Array.length dist in
  let best_cost = ref inf in
  let best_path = ref [] in
  let rec bnb path visited cost =
    let path_len = List.length path in
    if path_len = n then begin
      (* Complete tour: add return to start *)
      let total = cost + dist.(List.hd path).(List.hd (List.rev path)) in
      if total < !best_cost then begin
        best_cost := total;
        best_path := List.rev path
      end
    end else begin
      for v = 0 to n - 1 do
        if not visited.(v) then begin
          let new_cost = cost + dist.(List.hd path).(v) in
          (* Simple pruning: current cost already exceeds best *)
          if new_cost < !best_cost then begin
            visited.(v) <- true;
            bnb (v :: path) visited new_cost;
            visited.(v) <- false  (* backtrack *)
          end
        end
      done
    end
  in
  let visited = Array.make n false in
  visited.(0) <- true;
  bnb [0] visited 0;
  (!best_cost, !best_path)

let () =
  (* Small 4-city example *)
  let dist = [|
    [| 0; 10; 15; 20 |];
    [| 10; 0; 35; 25 |];
    [| 15; 35; 0; 30 |];
    [| 20; 25; 30; 0 |];
  |] in
  let (cost, path) = tsp_bnb dist in
  Printf.printf "TSP optimal cost: %d\n" cost;
  Printf.printf "Tour: %s\n"
    (String.concat " -> " (List.map string_of_int path) ^ " -> 0")

Deep Comparison

OCaml vs Rust: Branch And Bound

Overview

See the example.rs and example.ml files for detailed implementations.

Key Differences

Aspect	OCaml	Rust
Type system	Hindley-Milner	Ownership + traits
Memory	GC	Zero-cost abstractions
Mutability	Explicit ref	mut keyword
Error handling	Option/Result	Result<T, E>

See README.md for detailed comparison.

Exercises

Implement best-first search branch-and-bound using BinaryHeap<Reverse<(NotNan<f64>, State)>> for better pruning order.

Apply branch-and-bound to the traveling salesman problem with a minimum spanning tree lower bound.

Compare branch-and-bound vs. DP knapsack on instances with 20, 50, 100 items and measure when B&B beats DP.

Implement the LP relaxation bound using the minilp crate for tighter bounds on integer programs.

Profile the percentage of nodes pruned as a function of bound tightness for random knapsack instances.

Open Source Repos

functional-rust

View the source for this example on GitHub — OCaml and Rust side by side in the repo.

Rust