Written by: Paul Rubin

Primary Source: OR in and OB World, 02/14/2019.

I’ve been poking around in R with an unconstrained optimization problem involving binary decision variables. (Trust me, it’s not as trivial as it sounds.) I wanted to explore the entire solution space. Assuming \(n\) binary decisions, this means looking at the set \(\{0,1\}^n\), which contains \(2^n\) 0-1 vectors of dimension \(n\).

For reasons I won’t get into, I wanted to associate each vector with an ID number from 0 to \(2^n-1\), which sounds pretty straightforward … until you try to do it. I thought I’d post my code here, with no warranty (“express or implied”, as the legal eagles would say) that it’s computationally efficient.

Before I explain the code, let me just point out that using an integer from 0 to \(2^n-1\) implies that \(n\) is small enough that \(2^n-1\) fits in a machine integer. So if you decide to try the code, don’t go nuts with it.

Here’s the code:

# Create a vector of powers of 2 (for use in conversions from binary vectors to integers). powers.of.two <- 2^(0:(n - 1)) # Convert an ID (integer) to a binary vector of appropriate length. Note that the vector is reversed so that the lowest order bit (corresponding to the first decision) comes first. fromID <- function(id) { as.integer(head(intToBits(id), n)) } # Convert a binary vector of appropriate length to an ID value (integer). toID <- function(vec) { as.integer(vec %*% powers.of.two) }

To facilitate converting binary vectors to integers, I store all the powers of 2 once. The fromID() function takes an integer ID number and converts it to a binary vector of length \(n\). It uses the intToBits() function from the R base package, which does the heavy lifting but whose output needs a little massaging. The toID() function takes a binary vector and converts it to an integer ID number. So, with \(n=5\), the output of fromID(22) is

[1] 0 1 1 0 1

while the output of toID(c(0, 1, 1, 0, 1)) is

[1] 22

(as you would expect).

There is one other thing I should point out: because I am using the ID numbers to index binary vectors starting from (0, 0, …, 0) and working up to (1, 1, …, 1), I designed the functions to put the least significant bit first. If you want the most significant bit first and the least significant bit last, you need to make two changes to the code: change the definition of powers.of.two to 2^((n – 1):0); and, in the definition of fromID, change head(intToBits(id), n) to rev(head(intToBits(id), n)).

#### Paul Rubin

#### Latest posts by Paul Rubin (see all)

- Greedy Methods Can Be Exact - January 8, 2020
- 1-D Cutting Stock with Overlap - January 7, 2020
- A Value-ordered Java Map - October 18, 2019