# Benders decomposition Master Problem

I am currently working on implementation of Bender's Decomposition for MIP. I am looking at the simplest model \begin{equation} \begin{split} \min_{x,y} &\; c^Tx + f(y)\\ s.t. & \; Ax + Dy \ge b\\ & \; x\ge0, y\in\mathbb{Y} \end{split} \label{OP} \end{equation} Then the primal problem is formulated simply fixing complicating variable $y$. The dual of it will be \begin{equation} \begin{split} \max_{u} & \; \left(b - D\hat{y}\right)^T u \\ s.t. &\; A^Tu\leq c \\ & \; u\geq 0 \end{split} \label{DSP} \end{equation} Where $u$ is dual variable. Then the algorithm tells that Master problem is: \begin{equation} \begin{split} \min & \; f(y) + z \\ s.t. & \; z\geq \left(b - Dy\right)^T \hat{u}_j \quad \quad j=1,2,...,Q \\ & \; y\in\mathbb{Y}, z\in\mathbb{R} \end{split} \label{MP} \end{equation} Now assume that $y$ is binary vector variable. Algorithm tells me that dual primal problem is LP and I totally agree with that. Also it tells me that Master Problem is purely IP(Integer programming). And I don't understand why, because Master problem also includes variable $z$. My question: Why Master problem is purely IP and how do I get $z$? or if $z$ is a variable, how do I solve Master Problem?

Thanks everyone!

After few weeks of research I think I know the answer. $z$ is indeed unrestricted variable. But it is totally defined binary variable $y$. Hence the only variable need to be found is $y$. That is, the problem is purely IP.