Identifying optimal sets of individuals under a pairwise genomic relationship threshold for breeding and conservation

Maximizing genetic response to selection while constraining inbreeding is a central challenge in breeding and conservation. Classic optimal contribution selection methods address this by managing average population coancestry. However, this often results in complex, nonlinear optimization problems that cannot be guaranteed to reach a global optimum. Furthermore, many applications require a stricter pairwise constraint to avoid immediate inbreeding in offspring. Here, we present a binary integer linear programming formulation to select an optimal subset of individuals under a strict maximum tolerable pairwise genomic relationship threshold. We construct a binary matrix indicating whether each pair exceeds this threshold. This reformulation transforms the problem from a complex nonlinear program into a binary integer linear program. While this formulation remains NP-hard, the linearity allows modern solvers to efficiently navigate the solution space and, when convergence is achieved within the imposed runtime and tolerance settings, certify global optimality, a key advantage over heuristic approaches. We demonstrate the method using two distinct datasets: a large Norway spruce breeding population and a conservation population of German Black Pied cattle. We explore the trade-offs between the selection response, the relationship threshold, and the maximum number of individuals that can be selected under the threshold. Although large, dense problem instances remain computationally demanding, our results show that typical applications can often be solved to proven global optimality in seconds, whereas denser instances may terminate with a remaining optimality gap. This method is a practical solution for breeders and conservation geneticists to select optimal subsets under a strict relationship threshold, enabling applications from maximizing gain in breeding populations to establishing genetic reserves for endangered species.