Transformation of variable in restricted range of values in integer programming?

260 Views Asked by At

I have an integer linear program which has the following constraint

$$Z\in\{1,2,\ldots,K\}. \quad\quad\quad\quad\quad(\mathit{C1})$$

So $Z$ is an integer variable that takes values in the set $\{1,2,\ldots,K\}$.

I read that these types of variables can be replaced by binary variables. This can be done by introducing binary variables $Z_{k}\in\{0, 1\}$ and replace constraint $(\mathit{C1})$ by the following:

$$Z=\sum_{k=1}^{K}kZ_{k},\quad\quad\quad(\mathit{C1}')\\ \sum_{k=1}^{K}Z_{k}=1, \quad\quad\quad\quad(\mathit{C1}'')\\ Z_{k}\in\{0,1\}. \quad\quad\quad\quad(\mathit{C1}''')$$

What I do not understand is what are the variables in the new problem with constraints $(\mathit{C1}')$, $(\mathit{C1}'')$ and $(\mathit{C1}''')$? Is $Z$ still a variable? If so, why do we need such a transformation?

I mean, for me, $Z_k$ are the variables now but to solve the problem we need to set $Z=\sum_{k=1}^{K}kZ_{k}$ but then again what is $Z$ in this constraint?

1

There are 1 best solutions below

0
On BEST ANSWER

The idea is to replace all occurences of $Z$ with $\sum_{k=1}^K kZ_k$, so that the new problem only has binary variables $Z_k$ instead of the integer variable $Z$. Your formula $(C1')$ should not be a constraint in the final formulation. (Although if you add it as a constraint, you can leave $Z$ in other constraints as-is, and drop the integrality constraint on $Z$).