# Branching tree with tight continuous relaxation

Suppose you are solving an integer, linear math problem. The continuous relaxation is denoted by $z$, and the optimal solution is denoted by $z^*$.

In a branch-and-bound algorithm, is it possible to have more than one node in the branching tree if the continuous relaxation is tight, i.e., if $z^*=z$ ?

• Do you mean whether the root node can assume the optimal value while the solution is not integral? – LinAlg Oct 20 '16 at 16:55
• Yes that would be another way of saying it. – Kuifje Oct 20 '16 at 17:24

The answer is yes. If you solve $\max_{x \in \{0,1\}^2}\{ x_1+x_2 : x_1+x_2\leq 1 \}$ with an interior point solver, the root node will have $x=(0.5, 0.5)$ and you need to branch.
• Great! But you mean max I think in the objective function otherwise, the solution is $(0,0)$. Or equivalently, $\ge$ instead of $\le$ in the constraint. Am i right? – Kuifje Oct 20 '16 at 17:28
• I think this would happen even with the simplex algorithm with $\max_{x \in \{0,1\}^2}\{ x_1+x_2 : x_1+x_2\leq 1, x_2\ge x_1 \}$, as $(0.5,0.5)$ is now a vertex of the polygon. – Kuifje Oct 20 '16 at 17:53