2
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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$).

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.