I read somewhere that if I have a fractional solution to a problem and branch on that variable that it is definitely integral afterwards. Can't find the source anymore and would like to verify that.
For example I have the relaxation: x=1.24,y=0.56,z=4.12 and I branch on one of those variables in a way that I compute two sub problems by changing the bounds.
One sub problem with:
$x' \leq \left \lfloor{x}\right \rfloor = 1$
and the other with
$x'' \geq \left \lceil{x}\right \rceil = 2$
Is it true that the first sub problem is either infeasible or has a solution where $x=1$ ?
Or is it possible that it might be fractional again?
I assume it has to be integral or infeasible for convex problems but is it true for non-convex problems and is there an easy proof or counter example?
Maybe you have some interesting literature as well (currently implementing branch and bound :D )
Edit:
I found the source where I read it. The German Wikipedia article about Branch and Bound: https://de.wikipedia.org/wiki/Branch-and-Bound
It says:
Beide Teilprobleme werden mit dem dualen Simplexverfahren gelöst. Folgende Fälle können auftreten:
- Der zulässige Bereich wird leer.
- Man findet eine ganzzahlige Optimallösung für das Teilproblem.
- $x_1$ wird ganzzahlig, dafür aber ein anderes $x_{i}$ nicht, wobei es keine Rolle spielt, ob jenes $x_{i}$ vorher ganzzahlig war oder nicht.
Translation:
Both sub problems will be solved with the dual simplex algorithm. The following three situations might occur if $x_1$ is the branching variable:
- The solution of a sub problem might be infeasible
- The sub problem is fully integral
- $x_1$ will be integral but there is no information about the other $x_i$ even if they have been integral before.
Is this true but maybe only for linear problems in which the simplex algorithm is usable? In my case the non linear version is more interesting.
In general is it reasonable to branch on these two cases then or branch on all different options i.e. if $x \in \{1,2,3,4\}$ branch on 1,2,3,4 no matter what the relaxation is to have all cases. Branching on the two options seem more reasonable to me but I want to be sure that it's a correct way ;)