Decisions surrounding the presence of infectious diseases are typically made in the face of considerable uncertainty. However, the development of models to guide these decisions has been substantially constrained by computational difficulty. This paper focuses on the case of finding the optimal level of surveillance against a highly infectious animal disease where time, space and randomness are fully considered. We apply the Sample Average Approximation approach to solve our problem, and to control model dimension, we propose the use of an infection tree model, in combination with sensible 'tree-pruning' and parallel processing techniques. Our proposed model and techniques are generally applicable to a number of disease types, but we demonstrate the approach by solving for optimal surveillance levels against foot-and-mouth disease using bulk milk testing as an active surveillance protocol, during an epidemic, among 42,279 farms, fully characterised by their location, livestock type and size, in the state of Victoria, Australia.