Optimization Online


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

Makoto Yamashita(Makoto.Yamashita***at***is.titech.ac.jp)
Tim J. Mullin(tim.mullin***at***biosylve.com )
Sena Safarina(sena4***at***is.titech.ac.jp)

Abstract: An important problem in tree breeding is optimal selection from candidate pedigree members to produce the highest performance in seed orchards, while conserving essential genetic diversity. The most beneficial members should contribute as much as possible, but such selection of orchard parents would reduce performance of the orchard progeny due to serious inbreeding. To avoid inbreeding, we should include a constraint on the numerator relationship matrix to keep a group coancestry under an appropriate threshold. Though an SDP (semidefinite programming) approach proposed by Pong-Wong and Woolliams gave an accurate optimal value, it required rather long computation time. In this paper, we propose an SOCP (second-order cone programming) approach to reduce this computation time. We demonstrate that the same solution is attained by the SOCP formulation, but requires much less time. Since a simple SOCP formulation is not much more efficient compared to the SDP approach, we exploit a sparsity structure of the numerator relationship matrix, and formulate the SOCP constraint using Henderson's algorithm. Numerical results show that the proposed SOCP approach reduced computation time in a case study from 39,200 seconds under the SDP approach to less than 2 seconds.

Keywords: Semidefinite programming, Second-order cone programming, Tree breeding, Optimal selection, Group coancestry, Relatedness, Genetic gain

Category 1: Linear, Cone and Semidefinite Programming (Second-Order Cone Programming )

Category 2: Applications -- Science and Engineering

Citation: Research Report B-480, Dept. of Mathematical and Computing Science, Tokyo Institute of Technology

Download: [PDF]

Entry Submitted: 06/15/2015
Entry Accepted: 06/15/2015
Entry Last Modified: 06/15/2015

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society