We are solving an optimization problem, $$\min_{x, y,z} f(x,z) + g(y,z)$$ Both $x$ and $y$ must be the same, $x = y$. They must also be integer. (The reason why we don't just substitute $x = y$ in the problem is because we need to decompose it to make it faster to solve).
We then attempt the following approximation: Instead of solving the above problem, let's approximate it by introducing some $\lambda$, and solving $$ \min_\lambda \max_{x,y,z} f(x,z) + g(y,z) + \lambda(x-y)$$ So we first maximize by introducing a penalization for not having $x = y$, and then we minimize this over $\lambda$, which should bring us back close to our original problem.
However, having solved this, we may not get $x^\star = y^\star$ after all. I am now reading a book which says that we can "branch" and create two new problems, where one problem has the condition $x \le [m]$ and the other has $x \ge [m] + 1$, where $m = (x+y)/2$. Here, $[m]$ is rounding down.
And then we repeat the procedure for these two new problems. They say that if the number of integers that $x, y$ can take on is finite, then this will converge towards an optimal soution to our original problem, with $x = y$.
However, I do not see this clearly? Why will this converge? How to understand it with intuition?
Your reformulation is based on the assumption is that there exists a $\lambda$ for which $$\arg\max_x f(x,z) + \lambda x = \arg\max_y g(y,z) - \lambda y.$$ This is not necessarily true. For example, take $f(x,z) = x$ and $g(y,z)=y$, then the inner problem does not have a solution.