2
$\begingroup$

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!

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.