Captive breeding programs play a critical role in combating the ongoing biodiversity crisis by preserving the most endangered species and supporting reintroduction efforts. Maintaining the genetic health of captive populations requires careful management to prevent inbreeding and maximize the effective population size. Decisions about which males and females should be bred together are guided by the principle of minimizing relatedness between pairs. Methods to select breeding pairs are well developed, however, some species' ecology requires them to live in groups, and evaluating optimal groupings of multiple males and females that would be suitable to breed together is a more complex problem. Current computational tools to support the design of group-living captive breeding programs suffer from challenges of scalability and flexibility. In this paper we demonstrate the applicability of constraint programming (CP) approaches to optimize breeding groups to minimize relatedness. We present the example of the Galapagos giant tortoises as the test case used to develop our approach. Exploration of the needs of this captive breeding program has informed the development of our flexible approach to capture the constraints on viable captive breeding program design. Our findings have directly informed the implementation of new group configurations at the captive breeding centre. We further demonstrate that our approach is broadly applicable in other contexts through a second case study, providing multi-objective optimisation of a breeding program of canids. Through these case studies and an ablation study using synthetic datasets, we show that our constraint optimisation approach provides an expressive and generalizable means to support captive breeding program design, including scaling to large captive populations, which are currently intractable using current computational methods.