Optimization Online


Polyhedral-based Methods for Mixed-Integer SOCP in Tree Breeding

Sena Safarina(sena4***at***is.titech.ac.jp)
Tim J Mullin(Tim.Mullin***at***skogforsk.se)
Makoto Yamashita(Makoto.Yamashita***at***is.titech.ac.jp)

Abstract: Optimal contribution selection (OCS) is a mathematical optimization problem that aims to maximize the total benefit from selecting a group of individuals under a constraint on genetic diversity. We are specifically focused on OCS as applied to forest tree breeding, when selected individuals will contribute equally to the gene pool. Since the diversity constraint in OCS can be described with a second-order cone, equal deployment in OCS can be mathematically modeled as mixed-integer second-order cone programming (MI-SOCP). If we apply a general solver for MI-SOCP, non-linearity embedded in OCS requires a heavy computation cost. To address this problem, we propose an implementation of lifted polyhedral programming (LPP) relaxation and a cone-decomposition method (CDM) to generate effective linear approximations for OCS. In particular, CDM successively solves OCS problems much faster than generic approaches for MI-SOCP. The approach of CDM is not limited to OCS, so that we can also apply the approach to other MI-SOCP problems.

Keywords: Second-order cone programming; Mixed-integer conic programming; Conic relaxation; Tree Breeding; Equal deployment problem; Geometric cut; Optimal selection

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

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

Citation: B-489; Department of Mathematical and Computing Sciences, Tokyo Institute of Technology; May 2018

Download: [Compressed Postscript][PDF]

Entry Submitted: 05/09/2018
Entry Accepted: 05/10/2018
Entry Last Modified: 05/09/2018

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