Fun programming challenge: figure out which sets of passports grant visa-free access to the whole world

Having two citizenships is pretty restricted in Germany too. There are plans to make it a bit easier though.

A friend once told me, that there are ways around that, at least for them. Don't know how accurate that is.

• Send your passport and a renounciation of citizenship to the spanish embassy
• Spanish embassy confirms the arrival of the renounciation
• Use confirmation to get German citizenship
• The Spanish embassy returns your passport to you like "We're sorry, but you are not allowed to renounce citizenship"
• have two passports

@hydravion

As promised, I wrote an integer linear program to solve this problem. It's not exactly what you envisioned, I suspect, but it's what seemed to me the ideal way to solve the problem, and linear programming is an underused tool in the IT world.

Step 1: I downloaded a csv of the passport data, re-ordered a few columns so the matrix was symetric along the diagonal, and transposed the values so as to prepare the data for Octave's expected format.

Step 2: I collapsed all the values on visas status to either 1 or 0; 1 if no visa is required (or granted automatically on entry), and 0 if a visa is required.

Step 3: I used some Excel and Notepad++ trickery to prepare the text of the linear program.

Before I show my linear program, which is large, let's look at a sample one I wrote. Below is a linear program to solve a related set covering problem (scroll down to numerical example) that is easier to conceptualize.

# c is the objective function
c = [ 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ];

# A is the constraint matrix, i.e., the set of linear constraints that form our solution space.
A = [ 1 0 0 1 0 0 1 1 ;
      0 0 1 1 0 0 1 1 ;
      1 0 0 0 1 0 0 0 ;
      1 1 0 0 0 0 0 1 ;
      0 0 1 0 0 0 0 0 ;
      1 0 0 0 1 0 1 1 ;
      1 1 0 0 0 0 0 0 ;
      0 1 0 0 0 1 0 1 ;
      0 0 1 0 0 0 0 0 ;
      0 0 0 0 1 0 0 0 ;
      0 0 1 0 0 0 1 0 ;
      0 1 0 0 1 0 0 1 ;
      0 0 1 0 0 0 0 0 ;
      0 0 0 1 1 1 0 0 ;
      0 0 0 1 0 1 0 0 ;
      ];

# b is the RHS of the constraint equations.
b = [ 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ; 1 ];

# The rest of this isn't conceptually important, just book keeping for Octave.
lb = [ 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ; 0 ];
ub = [ inf ; inf ; inf ; inf ; inf ; inf ; inf ; inf ];
ctype = "LLLLLLLLLLLLLLL";
vtype = "IIIIIIII";
sense = 1;
[xstar,zstar,st,ex]=glpk(c,A,b,lb,ub,ctype,vtype,sense)

Basically, we sum the number of cameras needed to cover all the parts of the stadium. You should be able to see the correlation between the variables I've defined above, and the mathematical representation that I linked.

Now, in contrast, my LP will have a 199x199 constraint matrix, and a bunch of 199x1 and 1x199 other variables. In all of its glory, here it is:

code was too long for the post, so moved to pastebin

Step 4: We save the above to a file, and run it in Octave.

After running the program, which takes fractions of a second, we get a solution array with an entry of 1 in the spot corresponding to each country whose passport is part of the solution set. Those are:

• Afghanistan
• Australia
• Barbados
• Benin
• Canada
• Jordan
• Kenya
• Maldives
• Mali
• North Korea
• Papua New Guinea
• Singapore
• Turkmenistan

To understand the results, we look at our data, which for certain restrictive countries which only allow themselves or one or two others, the minimal solution set to visit every country in the world would require a passport from that country or one of the few it accepts.

Additionally, we know this is an optimal solution, but we don't know if it is unique. I.e., there could be other sets of 13 passports that grant access to every country in the world.

Honestly, after futzing with the data, the actual LP writing was just a few minutes. So this is probably the most efficient way in programmer time to solve these sorts of optimization problems.

I also hand wave away all the questions such as whether the ILP is in a convex space, but I'm not going to get that deep into it.

Have a great night!

So there's a few ways we could incorporate this into my ILP. Since the objective function that we seek to minimize is a 199x1 array of boolean variables, simple changing the coefficients from 1 to the number of years it takes to get a visa from that country would then minimize the problem of the least years it takes to collect them.

Additionally, for the spirit of the problem, certain countries like North Korea should just be left off, along with any country that doesn't have any visa free travel.

We could also reformulate the problem into a maximization problem where we try and maximize the number of countries we can visit visa free subject to a years waiting constraint, such as 20. So you could set a number of years and be given a solution that maximizes what you get for it.

We could also introduce weights to indicate countries of preference.

Have a great day!

Good news, everyone! The same data is also available as JSON: https://api.henleypassportindex.com/api/v3/visa-single/AD