Dans votre phrase, « qu’ils aient choisi » est un subjonctif passé ce que votre titre ne suggère pas.
Je vous propose plusieurs réflexions qui ne constituent pas la seule réponse possible :
==>utiliser le conditionnel passé dans la principale, avec  une subordonnée introduite par « si » au plus-que-parfait.   « il est possible que » peut être remplacé par « sans doute ».
Si telle situation avait été différente (plus-que-parfait), ils  auraient sans doute choisi autre chose. 

==> Avec « il est possible » :
Le fait n’est pas donné comme certain, donc le subjonctif est de rigueur ; comme vous utilisez le présent, normalement, il faut le subjonctif présent .
Mais pour votre phrase, il me semble gênant de mêler un « irréel du passé (si la situation avait été différente) à une possibilité actuelle au présent (il est possible que).

Si vous passez à « il aurait été possible qu’ils aient choisi autre chose », cela respecte la concordance des temps (conditionnel passé et subjonctif passé) mais cela alourdit un peu.