# How to represent an integer variable via binary variables?

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?

• My immediate reaction was to change "How" to "Why" in my head? If you were coding, I would say that this si a [code smell](en.wikipedia.org/wiki/Code_smell" - something that makes you stop and think twice about what you are doing. No offence intended, but are you sure that you want to do that, and, if so, can satisfy my curiosity by explaining why? Thanks
– Mawg
Commented Jul 6, 2021 at 5:58
• @MawgsaysreinstateMonica one situation I came across recently where you might want to do this is in exact stochastic, multi-stage integer programming. The approach explained here, for example, only works with binary integer variables. To apply that method to general integer variables, one would have to write the integer variable as a sum of binaries (with appropriate coefficients). Commented Jul 11, 2021 at 10:24

I'm not entirely sure if this is the most elegant way to model things, but here's how integer numbers are represented in a computer:

Let's take an integer variable $$x \in \mathbb{Z}$$ with $$L \leq x \leq U$$ and $$L \geq 0$$, meaning $$x$$ is non-negative. By using $$M$$ binary variables (bits) $$b_0, \ldots, b_{M-1}$$, we can represent $$x$$ in base 2 as:

$$x = (b_{M-1}b_{M-2}\ldots b_{0})_2 = \sum_{j=0}^{M-1} b_j \cdot 2^j.$$

To minimize the number of binary variables needed, we find the smallest $$M$$ such that:

$$U \leq \max_{b_0,\ldots,b_{M-1}} \sum_{j=0}^{M-1} b_j \cdot 2^j = \sum_{j=0}^{M-1} 1 \cdot 2^j = 2^{M} - 1,$$

which gives us $$M = \left\lceil \log_2{(U + 1)} \right\rceil$$. If $$L < 0$$, the two's complement representation can be used. It is expressed as:

$$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$$ represents the minimum number of binary variables needed to represent $$x$$.

• +1. Here is an early reference for this approach. See the footnote on page 1172. Commented Jul 4, 2021 at 15:38
• This approach is sometimes referred to as a "power expansion". Commented Jul 4, 2021 at 20:53
• There is also unary encoding. (Doing this sounds stupid, but I once read that it provices tighter models.)
– T_O
Commented Jul 5, 2021 at 11:13

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.