Research map / Learning theory and algorithms / Combinatorial and search optimization
Constraint Optimisation Approaches for Designing Group-Living Captive Breeding Programmes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Applies constraint programming (CP-SAT) to optimise group allocations in captive breeding programmes to minimise pairwise relatedness, validated on Galápagos giant tortoise and canid case studies plus synthetic scaling tests.
Problem
Designing breeding groups (multiple males and females per corral) that minimise relatedness and inbreeding in captive populations; existing tools (Swinger, nprcgenekeepr) are slow, threshold-dependent, or not guaranteed optimal at large scale.
Approach
Formulates group-based captive breeding design as a constraint optimisation problem with flexible constraints (corral sizes, sex ratios, priority/mandatory/prohibited pairs, maximum pairwise relatedness, minimum participants) and a squared-relatedness objective, solved with Google OR-Tools CP-SAT, with symmetry breaking and a multi-objective weighted-sum extension for ghost alleles.
Key results
- On commodity MacBook Pro, the 51-tortoise configuration (c=51) reaches an optimal solution in 7,200s cutoff without finishing for the 64-core run only in 7,200s, while smaller configurations (c=20) solve optimally in about 1.3-1.8s.
- Judicious maximum pairwise relatedness thresholds (e.g. percentile p47-p49) reduce runtime to around 3.3-3.5s for 51 tortoises versus the full unconstrained run.
- The approach scales to a synthetic population of 1,000 individuals with a first viable solution in about 42-57s, and updated tortoise breeding groups were adopted by the Galápagos National Park.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the 64-vCPU c6i.16xlarge instead of the MacBook Pro | Constraint programming solver · Galápagos tortoises, c = 30 | time to optimal solution: 7,200s -> 3,216.88s | Helped |
| Use the 64-vCPU c6i.16xlarge instead of the MacBook Pro | Constraint programming solver · Galápagos tortoises, c = 40 | time to optimal solution: 7,200s -> 5,982.42s | Helped |
| Increase the number of participating individuals (ablation) | Galápagos tortoise breeding-group allocation · Galápagos tortoises, 45–51 individuals | mean pairwise relatedness | Mixed |
| Set the maximum pairwise relatedness threshold to p47 (ablation) | Constraint programming solver · Galápagos tortoises, 51 individuals, nine corrals | time to optimal solution: p47 = 3.33s | Helped |
| Set the maximum pairwise relatedness threshold to p48 (ablation) | Constraint programming solver · Galápagos tortoises, 51 individuals, nine corrals | time to optimal solution: p48 = 3.49s | Helped |
| Set the maximum pairwise relatedness threshold to p49 (ablation) | Constraint programming solver · Galápagos tortoises, 51 individuals, nine corrals | time to optimal solution: p49 = 3.52s | Helped |
| Use multi-objective optimization to balance minimum relatedness with maximum ghost alleles (ablation) | Canid breeding-group allocation · Canids with red wolf ghost alleles | total ghost alleles: α = 0, . . . , 1; steps of 0.05; total runtime ≤8s | Mixed |
Surprising findings
- Restricting maximum pairwise relatedness to a high percentile threshold dramatically speeds up solving, and threshold infeasibility can be detected quickly.
- Adding more cores did not guarantee optimality within the time limit for the 51-individual case (7,200s on 64 vCPUs) even though near-optimal solutions were found faster.
Limitations
- Relies on pairwise relatedness estimates as the only input; behavioural compatibility and other husbandry factors are not modelled.
- Choice of maximum relatedness threshold requires careful tuning and may render designs infeasible.
- Multi-objective approach uses weighted sum scalarisation, which cannot find non-convex Pareto frontier points.
Experimental setup
Datasets: Galápagos giant tortoise pairwise relatedness (51 individuals, ngsRelateV2) Canid (coyote) pairwise relatedness (14 individuals, PLINK) Synthetic dataset of 1,000 simulated individuals
Benchmarks: Galápagos giant tortoise breeding program canid red wolf ghost allele case synthetic scaling dataset
Metrics: pairwise relatedness (mean, max) time to optimal solution time to first solution time to within 1% of optimum Adjusted Rand Index
Baselines: Swinger nprcgenekeepr
Builds on: CP-SAT Swinger nprcgenekeepr
Closest papers by meaning
- Improving Community-Participated Patrol for Anti-Poaching (AAAI 2025 · similarity 0.77)
- Decision-Making for Land Conservation: A Derivative-Free Optimization Framework with Nonlinear Inputs (AAAI 2024 · similarity 0.76)
- Runtime Analysis of the (μ + 1) GA: Provable Speed-Ups from Strong Drift towards Diverse Populations (AAAI 2024 · similarity 0.76)
- Online Control in Population Dynamics (NeurIPS 2024 · similarity 0.76)
- Improved Theoretically-Grounded Evolutionary Algorithms for Subset Selection with a Linear Cost Constraint (ICML 2025 · similarity 0.76)
- SAM 3D Animal: Promptable Animal 3D Reconstruction from Images in the Wild (NeurIPS 2026 · similarity 0.75)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.