  Motivated by the recent success of tensor networks to calculate the residual
entropy of spin ice and kagome Ising models, we develop a general framework to
study frustrated Ising models in terms of infinite tensor networks %, i.e.
tensor networks that can be contracted using standard algorithms for infinite
systems. This is achieved by reformulating the problem as local rules for
configurations on overlapping clusters chosen in such a way that they relieve
the frustration, i.e. that the energy can be minimized independently on each
cluster. We show that optimizing the choice of clusters, including the weight
on shared bonds, is crucial for the contractibility of the tensor networks, and
we derive some basic rules and a linear program to implement them. We
illustrate the power of the method by computing the residual entropy of a
frustrated Ising spin system on the kagome lattice with next-next-nearest
neighbour interactions, vastly outperforming Monte Carlo methods in speed and
accuracy. The extension to finite-temperature is briefly discussed.
