Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
Suppose we have a model with $N$ integer variables, i.e. $x \in \mathbb{Z}^{N}$ with $L \leq x \leq U$.
How can we represent the integer variables via binary variables? Or in other words: how can we transform an integer programming problem into a binary programming problem?
I'm not sure if this is the most elegant modelling way. However, this is exactly how integer numbers are represented in the computer:
Let's consider one integer variable $x \in \mathbb{Z}$ with $L \leq x \leq U$ and $L \geq 0$, i.e. $x$ is not negative.
By introducing $M$ binary variables (bits) $b_0, \ldots, b_{M-1}$, we have the representation of $x$ in the base 2 which reads as:
$$ x = (b_{M-1}b_{M-2}\ldots b_{0})_2 = \sum_{j=0}^{M-1} b_j \cdot 2^j. $$
In order to use as few binary variables (bits) as possible, we need the smallest $M$ such that
$$ U \leq \max \sum_{j=0}^{M-1} b_j \cdot 2^j % = \sum_{j=0}^{M-1} 1 \cdot 2^j % = 2^{M} - 1, $$
which yields $M = \left\lceil \log_2{(U + 1)} \right\rceil $.
In case $x$ is not guaranteed to be positive, one can use the two complement representation:
$$ x = (b_{M-1}b_{M-2}\ldots b_{0})_2 = -b_{M-1} \cdot 2^{M-1} + \sum_{j=0}^{M-2} b_j \cdot 2^j, $$
where $M = \left \lceil \log_2{( \max \{ |L|, |U| \} + 1)} + 1\right \rceil$ is the minimal number of binary variables required to represent $x$.
You can stay in base $10$ with a similar approach as @joni: introduce $m=U-L+1$ binary variables $y_i$, one for each integer value in the range $[L,U]$, and write $x$ as follows: $$ x= L y_1 + (L+1)y_2 +...+(U-1)y_{m-1} + Uy_m $$
Then, make sure only one of these values is selected: $$ \sum_{i=1}^m y_i = 1 $$
Of course this yields more than $\lceil \log_2(U+1) \rceil$ variables.
In computer science, "integer" data types are generally a fixed-length array of bits. In earlier languages, those lengths were generally 16 or 32 bits, but later languages tend towards 64. This type of implementation does have drawbacks. For instance, they aren't really integers, in the mathematical sense, as they are members of a finite set. The idea is that they're "big enough"; how often do you have to deal with integers bigger than a quadrillion? It's possible to implement model of the integers that aren't fixed bits, but those are more complicated (e.g. linked lists), and we can't know ahead of time how much/which portion of memory to assign ahead of time.
What implementation to choose depends on what we value. Once option, after putting the integers in binary, is to split its digits into blocks, and then have another block that keeps track of what blocks represent what integers. There are several ways to do that, one of which is store the block numbers where a new integer starts. Since we know the first integer starts in the first block, this means that for n integers, we now need to store n-1 integers, each of which should be on the order of the log of the original numbers.
Another method is encode the information within the block. You could assign one bit in each block to recording whether it's the last block for its integer. You could compress it even further with more complicated algorithms.
