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

  • $\begingroup$ Do you mean whether the root node can assume the optimal value while the solution is not integral? $\endgroup$ – LinAlg Oct 20 '16 at 16:55
  • $\begingroup$ Yes that would be another way of saying it. $\endgroup$ – 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.

  • $\begingroup$ 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? $\endgroup$ – Kuifje Oct 20 '16 at 17:28
  • $\begingroup$ Right, thanks! You can easily construct more examples by taking a constant objective function. $\endgroup$ – LinAlg Oct 20 '16 at 17:30
  • $\begingroup$ Good point. But is this possible with a solver that does not use interior points? The example in the answer clearly does not work with the simplex. $\endgroup$ – Kuifje Oct 20 '16 at 17:48
  • 1
    $\begingroup$ 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. $\endgroup$ – Kuifje Oct 20 '16 at 17:53
  • $\begingroup$ With the simplex method you may be "lucky" to end up with an integer solution. $\endgroup$ – LinAlg Oct 20 '16 at 17:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.