« home

Branch and Bound

optimizationalgorithmcetztikz

Illustration of a linear-programming (LP)-based branch and bound algorithm. Not knowing how to solve a mixed-integer programming (MIP) problem directly, it first removes all integrality constraints. This results in a solvable LP called the linear-programming relaxation of the original MIP. The algorithm then picks some variable x restricted to be integer, but whose value in the LP relaxation is fractional. Suppose its value in the LP relaxation is x = 0.7. It then excludes this value by imposing the restrictions x ≤ 0 and x ≥ 1, thereby creating two new MIPs. By applying this recursively step and exploring each resulting bifurcation, the globally optimal solution satisfying all constraints can be found.


Branch and Bound

  Download

PNGPDFSVG

  Code

  LaTeX

branch-and-bound.tex (59 lines)

\documentclass{standalone}

\usepackage{forest}

\tikzset{
  font=\normalsize,
  tree node/.style = {align=center, inner sep=0pt, draw, circle, minimum size=18},
  tree node label/.style={font=\scriptsize},
}

\forestset{
  declare toks={left branch prefix}{},
  declare toks={right branch prefix}{},
  declare toks={left branch suffix}{},
  declare toks={right branch suffix}{},
  maths branch labels/.style={
    branch label/.style={
      if n=1{
        edge label={node [left, midway] {$\forestoption{left branch prefix}##1\forestoption{left branch suffix}$}},
      }{
        edge label={node [right, midway] {$\forestoption{right branch prefix}##1\forestoption{right branch suffix}$}},
      }
    },
  },
  set branch labels/.style n args=4{%
    left branch prefix={#1},
    left branch suffix={#2},
    right branch prefix={#3},
    right branch suffix={#4},
  },
  branch and bound/.style={
    /tikz/every label/.append style=tree node label,
    maths branch labels,
    for tree={
      tree node,
      math content,
      s sep'+=20mm,
      l sep'+=5mm,
      thick,
      edge+={thick},
    },
    before typesetting nodes={
      for tree={
        split option={content}{:}{content,branch label},
      },
    },
  },
}

\begin{document}
\begin{forest}
  branch and bound,
  where level=1{
  set branch labels={x_1\leq}{}{x_1\geq}{},
  }{if level=2{set branch labels={x_2\leq}{}{x_2\geq}{}}{set branch labels={x_3\leq}{}{x_3\geq}{}}}
  [P_0[P_1:0][P_2:1[P_3:0[P_5:0][P_6:1]][P_4:1]]]
\end{forest}
\end{document}

  Typst

branch-and-bound.typ (61 lines)

#import "@preview/cetz:0.3.2": canvas, draw

#set page(width: auto, height: auto, margin: 8pt)

#canvas({
  import draw: line, content, circle

  let node-sep = 1.5 // Horizontal separation between nodes
  let level-sep = 1.5 // Vertical separation between levels
  let node-radius = 0.35
  let arrow-style = (mark: (end: "stealth", fill: black, scale: 0.2), stroke: black + 1pt)

  // Helper to draw a node with label
  let draw-node(pos, label, name: none) = {
    circle(pos, radius: node-radius, name: name)
    content(pos, $#label$)
  }

  // Helper to draw edge label
  let draw-edge-label(from, to, label, left: true) = {
    let anchor = if left { "east" } else { "west" }
    content(
      (rel: (if left { -0.3 } else { 0.3 }, 0), to: from + "-" + to + ".mid"),
      $#label$,
      anchor: anchor,
    )
  }

  // Draw nodes level by level
  // Root (level 0)
  draw-node((0, 0), $P_0$, name: "p0")

  // Level 1
  draw-node((-node-sep, -level-sep), $P_1$, name: "p1")
  draw-node((node-sep, -level-sep), $P_2$, name: "p2")

  // Level 2
  draw-node((0, -2 * level-sep), $P_3$, name: "p3")
  draw-node((2 * node-sep, -2 * level-sep), $P_4$, name: "p4")

  // Level 3
  draw-node((-node-sep, -3 * level-sep), $P_5$, name: "p5")
  draw-node((node-sep, -3 * level-sep), $P_6$, name: "p6")

  // Draw edges
  line("p0", "p1", ..arrow-style, name: "p0-p1")
  line("p0", "p2", ..arrow-style, name: "p0-p2")
  line("p2", "p3", ..arrow-style, name: "p2-p3")
  line("p2", "p4", ..arrow-style, name: "p2-p4")
  line("p3", "p5", ..arrow-style, name: "p3-p5")
  line("p3", "p6", ..arrow-style, name: "p3-p6")

  // Draw edge labels
  draw-edge-label("p0", "p1", $x_1 <= 0$)
  draw-edge-label("p0", "p2", $x_1 >= 1$, left: false)
  draw-edge-label("p2", "p3", $x_2 <= 0$)
  draw-edge-label("p2", "p4", $x_2 >= 1$, left: false)
  draw-edge-label("p3", "p5", $x_3 <= 0$)
  draw-edge-label("p3", "p6", $x_3 >= 1$, left: false)
})