Branch and bound tree in tikz

I'm trying to create a tree showing the branch and bound process for an integer programming problem in tikz. I managed to create a tree with the first level in exactly the way I want but latex fails to compile the tree with the second level, and I'm unsure My code is very poorly optimised since this was the only way I could work out how to do it, and the messy code means its difficult to pinpoint where I'm going wrong.

If anyone could show me a way to clean up the code so most of the node details are in the pre-definition or show me where I'm going wrong in the second tree that would be great.

Code for the first level:

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{calc, shapes}

\begin{document}
\begin{figure}
\centering
\begin{tikzpicture}[
scale = 1.5, transform shape, thick,
tree node/.style = {align=center, inner sep=0pt, text centered, font =
\scriptsize},
S/.style = {draw, circle, minimum size = 8mm, top color=white, bottom
color=blue!20},
grow = down,  % alignment of characters
level 1/.style = {sibling distance=3cm},
level 2/.style = {sibling distance=4cm},
level 3/.style = {sibling distance=2cm},
level distance = 1.25cm]

\node [S, label={[font = \scriptsize]10:950}, label={[font =
\scriptsize]170:1055.56}] {$S$}
child{node [S, label={[font = \scriptsize]10:950}, label={[font =
\scriptsize]170:1000}] {$S_1$}edge from parent node[above left, font =
\scriptsize] {$x \leq 5$}}
child{node [S, label={[font = \scriptsize]10:950}, label={[font =
\scriptsize]170:1033}]
{$S_2$} edge from parent node[above right, font = \scriptsize] {$x \geq 6$}};
\end{tikzpicture}
\end{figure}
\end{document}

Code for the first and second levels, which fail to compile:

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{calc, shapes}

\begin{document}

\begin{figure}
\begin{tikzpicture}[
scale = 1.5, transform shape, thick,
tree node/.style = {align=center, inner sep=0pt, text centered, font =
\scriptsize},
S/.style = {draw, circle, minimum size = 8mm, top color=white, bottom
color=blue!20},
grow = down,  % alignment of characters
level 1/.style = {sibling distance=3cm},
level 2/.style = {sibling distance=4cm},
level 3/.style = {sibling distance=2cm},
level distance = 1.25cm]
\node [S, label={[font = \scriptsize]10:950}, label={[font =
\scriptsize]170:1055.56}] {$S$}
child{node [S, label={[font = \scriptsize]10:950}, label={[font =
\scriptsize]170:1000}] {$S_1$} edge from parent node[above left, font =
\scriptsize] {$x \leq 5$}}
child{node [S, label={[font = \scriptsize]10:950}, label={[font =
\scriptsize]170:1033}]
{$S_2$} edge from parent node[above right, font = \scriptsize] {$x \geq 6$}
child{node [S, label={[font = \scriptsize]10:950}, label={[font
= \scriptsize]170:1033}]
{$S_2,1$} edge from parent node[above right, font = \scriptsize]
{$x \leq 1$}
child{node [S, label={[font = \scriptsize]10:950}, label={[font
= \scriptsize]170:1033}]
{$S_2,2$} edge from parent node[above right, font = \scriptsize]
{$x \geq 2$}};
\end{tikzpicture}
\end{figure}
\end{document}

Edit: A branch and bound tree like the one I'm trying to create

• Have you considered using a tree drawing package? Even the trees library, but preferably forest or tikz-qtree. Especially if you need to draw many trees .... – cfr Feb 20 '18 at 23:50
• You're missing some } in the second tree, so TikZ is not finding the end of the nodes. – cfr Feb 21 '18 at 0:02

I would use one of the specialised tree-drawing packages. More specifically, I would use forest or, failing that, tikz-qtree. If you do this, you can specify trees very concisely and simply and easily ensure that they are consistently formatted.

In the case of Forest, the package will also do a lot of the layout work for you, although labels are not handled in this way, so this particular advantage may not be of much benefit for trees of this particular kind.

Here's an example which defines a branch and bound style for Forest. When applied to a tree, the following happens:

• tree node, S and thick are applied to all nodes in the tree and there content is set in maths mode;

• the edges are also thick;

• a bit of space is added to the tree to space out the branches and the levels;

• after the tree is parsed, the content of each node is split at each colon: <left label>:<node content>:<right label>:<edge label>;

• The part before the first colon becomes the left label (at 170). The next part is set as the main node content (with tree node, in maths mode etc.). The third part is set as the right label (at 10). The final part becomes the label on the branch: left of the midpoint for a left-hand branch and right for a right-hand one.
• the contents of the edge labels can be set in either text mode (text branch labels) or maths mode (maths branch labels);

• prefixes and suffixes can be added using one of

• set branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}

• set maths branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}

• set text branch labels={<left branch prefix>}{<left branch suffix>}{<right branch prefix>}{<right branch suffix>}

• a horizontal line is drawn under each leaf of the tree.

Then we can specify what I think is your second tree, now edited in light of comments to vary edge labels according to level, with

\begin{forest}
branch and bound,
where level=1{
set branch labels={x\leq}{}{x\geq}{},
}{
if level=2{
set branch labels={}{\geq y}{}{\leq y},
}{},
}
[1055.56:S:950
[1000:S_1:950:5
]
[1033:S_2:950:6
[1033:{S_2,1}:950:1]
[950:{S_2,2}:1033:2]
]
]
\end{forest}

which is obviously quite a bit more concise and produces

I don't know what the criteria are for this kind of tree, so this might need a little tweaking to work well. For example, perhaps the edge labels aren't always of the form x\leq and x\req, or perhaps there are sometimes only one or more than two children. However, this should at least illustrate the potential power of this approach.

Complete code:

\documentclass[border=10pt]{standalone}
\usepackage{forest}
\tikzset{
tree node/.style = {align=center, inner sep=0pt, font = \scriptsize},
S/.style = {draw, circle, minimum size = 8mm, top color=white, bottom color=blue!20},
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}{},
tree node left label/.style={
label=170:#1,
},
tree node right label/.style={
label=10:#1,
},
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}$}},
}
},
},
text branch labels/.style={
branch label/.style={
if n=1{
edge label={node [left, midway] {\foresteoption{left branch prefix}##1\forestoption{left branch suffix}}},
}{
edge label={node [right, midway] {\forestoption{right branch prefix}##1\forestoption{right branch suffix}}},
}
},
},
text branch labels,
set branch labels/.style n args=4{%
left branch prefix={#1},
left branch suffix={#2},
right branch prefix={#3},
right branch suffix={#4},
},
set maths branch labels/.style n args=4{
maths branch labels,
set branch labels={#1}{#2}{#3}{#4},
},
set text branch labels/.style n args=4{
text branch labels,
set branch labels={#1}{#2}{#3}{#4},
},
branch and bound/.style={
/tikz/every label/.append style=tree node label,
maths branch labels,
for tree={
tree node,
S,
math content,
s sep'+=20mm,
l sep'+=5mm,
thick,
edge+={thick},
},
before typesetting nodes={
for tree={
split option={content}{:}{tree node left label,content,tree node right label,branch label},
},
},
where n children=0{
tikz+={
\draw [thick]  ([yshift=-10pt, xshift=-2.5pt].south west) -- ([yshift=-10pt, xshift=2.5pt].south east);
}
}{},
},
}
\begin{document}
\begin{forest}
branch and bound,
where level=1{
set branch labels={x\leq}{}{x\geq}{},
}{
if level=2{
set branch labels={}{\geq y}{}{\leq y},
}{},
}
[1055.56:S:950
[1000:S_1:950:5
]
[1033:S_2:950:6
[1033:{S_2,1}:950:1]
[950:{S_2,2}:1033:2]
]
]
\end{forest}
\end{document}
• This is exactly what I was looking for, thank you! One more quick question, for the second layer of the tree I'd like to change the label on the branches, for example to "y<=...". It seemed the intuitive way this would work would be to add a second "if n=2{..." clause in the branch label style part of the code but this doesn't seem to work. Any suggestions? – M. Hughes Feb 21 '18 at 15:06
• @M.Hughes What do you mean by 'the second layer'? If you change edge label={node [left, midway] {$x\leq#1$}}, to edge label={node [left, midway] {$#1$}}, and likewise for the right case, then you can specify whatever you like for the label, just writing y\geq3 or x^{5+23i} or whatever you need. In this case, the label will just be wrapped in maths mode. (If you sometimes want text mode, you could always remove the $...$, too. Would any of that help? – cfr Feb 22 '18 at 1:26
• @M.Hughes Please see edited answer above. – cfr Feb 22 '18 at 3:20
• errors for second code in your mwe has source in mising } after edge from parent node
• solution with tikz
• your code is cleaned and make shorter by defining new styles for nodes and edges labels
• combining both trees in your question in one (similar as do cfr in his answer) mwe become:

\documentclass{article}
\usepackage[utf8]{inputenc}
\usepackage{tikz}
\usetikzlibrary{calc, shapes}

\begin{document}
\begin{figure}
\tikzset{thick,
tree node/.style = {align=center, inner sep=0pt, font = \scriptsize},
every label/.append style = {font=\scriptsize},
S/.style = {draw, circle, minimum size = 11mm, inner sep=0pt,
top color=white, bottom color=blue!20},
ENL/.style = {% edge node left
font=\footnotesize, left=1pt},
ENR/.style = {% edge node right
font=\footnotesize, right=1pt},
grow = down,
sibling distance = 2.8cm,
level distance = 3cm
}
\newcommand\LB{% Lower bound
\tikz\draw[very thick] (-0.5,0) -- + (1,0);}

\centering
\begin{tikzpicture}
\node [S, label=10:950, label=170:1055.56] {$S$}
child{node [S, label=10:950, label=170:1000, label=below:\LB] {$S_1$}
edge from parent node[ENL] {$x \leq 5$}}
child{node [S, label=10:950, label=170:1033] {$S_2$}
child{node [S, label=10:950, label=170:1033, label=below:\LB] {$S_2,1$}
edge from parent node[ENL] {$x \geq 6$}}
child{node [S, label=10:950, label=170:1033, label=below:\LB] {$S_2,2$}
edge from parent node[ENR] {$x \leq 1$}}
edge from parent node[ENR] {$x \geq 6$}
};
\end{tikzpicture}
\end{figure}
\end{document}