An efficient second-order cone programming approach for optimal selection in tree breeding

Makoto Yamashita*, Tim J. Mullin, Sena Safarina

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

10 Citations (Scopus)


It is common in forest tree breeding that selection of populations must consider conservation of genetic diversity, while at the same time attempting to maximize response to selection. To optimize selection in these situations, the constraint on genetic diversity can be mathematically described with the numerator relationship matrix as a quadratic constraint. Pong-Wong and Woolliams formulated the optimal selection problem using semidefinite programming (SDP). Their SDP approach gave an accurate optimal value, but required rather long computation time. In this paper, we propose an second-order cone programming (SOCP) approach to reduce the heavy computation cost. First, we demonstrate that a simple SOCP formulation achieves the same numerical solution as the SDP approach. A simple SOCP formulation is, however, not much more efficient compared to the SDP approach, so we focused on the sparsity structure of the numerator relationship matrix, and we develop a more efficient SOCP formulation using Henderson’s algorithm. Numerical results show that the proposed formulation, which we call a compact SOCP, greatly reduced computation time. In a case study, an optimal selection problem that demanded 39,200 s under the SDP approach was solved in less than 2 s by the compact SOCP formulation. The proposed approach is now available as a part of the software package OPSEL.

Original languageEnglish
Pages (from-to)1683-1697
Number of pages15
JournalOptimization Letters
Issue number7
Publication statusPublished - 1 Oct 2018
Externally publishedYes


  • Genetic gain
  • Group coancestry
  • Optimal selection
  • Relatedness
  • Second-order cone programming
  • Semidefinite programming
  • Tree breeding


Dive into the research topics of 'An efficient second-order cone programming approach for optimal selection in tree breeding'. Together they form a unique fingerprint.

Cite this