# Branch and bound branching

we are doing a MILPP problem where we use branch and bound $minimize: \: \: c^{^{T}}x \\ subject \: to: \sum_{j=1}^{n} A_{ij}x_{j} \leq b_{i} \: \forall i = \overline{1,n} \\ \hspace{2.2cm} x_{i} \in \mathbb{Z}\: for\: some\: i = 1, . . . n \\ \hspace{2.2cm} x_{i} \in \mathbb{R} \: for \:remaining\: i = 1, . . . n$

now suppose we solve LPP and find a solution: we find that for some k $x_{k}= a$, $x_{k} \notin \mathbb{Z}$ thus we do a branching based on $x_{k}$

after branching we get 2 new problems with 1 more constraint $x_{k} \geq a$ ,$\: x_{k} \leq a$ respectively.

the question is: can we conclude that one of the resulted LPP's will be either unbounded or infeasible. If not, what conditions must be fulfilled (if any) to satisfy the conclusion

No, this needs not happen. Consider the problem

$$\max 1.5x+0.5y$$ $$x+0.5y \leq 3.75$$ $$y \leq 3.5$$ $$x \leq 2.5$$ $$x,y \geq 0$$

The feasible set with the objective function is: Solving the relaxation gives us the solution (2.5,2.5). Both coordinates are non-integers so we have to branch. We branch at $y$ and add the constraints $y\geq 3$ and $y \leq 2$. This reduces to the feasible sets below: Hence, both subproblems are neither unbounded nor infeasible. We would find the solutions (2.25,3) and (2.5,2) and would have to keep on branching. Note, however, if we had branched at $x$ instead of $y$ in the first step, then the subproblem with the constraint $x\geq3$ would indeed have been infeasible. Yet, as the example above shows, this needs not always happen.

• So can we say that for any constraint , there exists some variable that after splitting will give 2 feasible and unbounded LPP ? – Vanta May 15 '18 at 17:15