2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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: enter image description here

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:

enter image description here

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.

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

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.