  We provide geometric methods and algorithms to verify, construct and
enumerate pairs of words (of specified length over a fixed $m$-letter alphabet)
that form identities in the semigroup $\ut{n}$ of $n\times n$ upper triangular
tropical matrices. In the case $n=2$ these identities are precisely those
satisfied by the bicyclic monoid, whilst in the case $n=3$ they form a subset
of the identities which hold in the plactic monoid of rank $3$. To each word we
associate a signature sequence of lattice polytopes, and show that two words
form an identity for $\ut{n}$ if and only if their signatures are equal. Our
algorithms are thus based on polyhedral computations and achieve optimal
complexity in some cases. For $n=m=2$ we prove a Structural Theorem, which
allows us to quickly enumerate the pairs of words of fixed length which form
identities for $\ut{2}$. This allows us to recover a short proof of Adjan's
theorem on minimal length identities for the bicyclic monoid, and to construct
minimal length identities for $\ut{3}$, providing counterexamples to a
conjecture of Izhakian in this case. We conclude with six conjectures at the
intersection of semigroup theory, probability and combinatorics, obtained
through analysing the outputs of our algorithms.
