Branching tree with tight continuous relaxation

110 Views Asked by At

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$ ?

1

There are 1 best solutions below

6
On BEST ANSWER

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.