This dataset was compiled as part of the following PhD thesis: CHRISTIE, L.A. 2016. The role of Walsh structure and ordinal linkage in the optimisation of pseudo-Boolean functions under monotonicity invariance. Robert Gordon University, PhD thesis. Held on OpenAIR [online]. Available from: http://hdl.handle.net/10059/1567. The aim of this thesis was to investigate the role that problem structure plays in heuristic optimisation, developing a classification of pseudo-Boolean functions based on rank-invariance. The thesis provides insight into the relationship between function structure and problem difficulty for optimisation, which may be used to direct the development of novel algorithms.