# 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

## 1 Answer

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