  Computing the frustration index of a signed graph is a key step toward
solving problems in many fields including social networks, political science,
physics, chemistry, and biology. The frustration index determines the distance
of a network from a state of total structural balance. Although the definition
of the frustration index goes back to the 1950's, its exact algorithmic
computation, which is closely related to classic NP-hard graph problems, has
only become a focus in recent years. We develop three new binary linear
programming models to compute the frustration index exactly and efficiently as
the solution to a global optimisation problem. Solving the models with
prioritised branching and valid inequalities in Gurobi, we can compute the
frustration index of real signed networks with over 15000 edges in less than a
minute on inexpensive hardware. We provide extensive performance analysis for
both random and real signed networks and show that our models outperform all
existing approaches by large factors. Based on solve time, algorithm output,
and effective branching factor we highlight the superiority of our models to
both exact and heuristic methods in the literature.
