5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ 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 $\endgroup$ Jul 6 at 5:58
  • 1
    $\begingroup$ @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). $\endgroup$
    – N. Wouda
    Jul 11 at 10:24
11
$\begingroup$

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

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

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.

$\endgroup$
2
$\begingroup$

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.

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