  


Polyhedralbased Methods for MixedInteger SOCP in Tree Breeding
Sena Safarina(sena4is.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 secondorder cone, equal deployment in OCS can be mathematically modeled as mixedinteger secondorder cone programming (MISOCP). If we apply a general solver for MISOCP, nonlinearity embedded in OCS requires a heavy computation cost. To address this problem, we propose an implementation of lifted polyhedral programming (LPP) relaxation and a conedecomposition method (CDM) to generate effective linear approximations for OCS. In particular, CDM successively solves OCS problems much faster than generic approaches for MISOCP. The approach of CDM is not limited to OCS, so that we can also apply the approach to other MISOCP problems. Keywords: Secondorder cone programming; Mixedinteger 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 (SecondOrder Cone Programming ) Citation: B489; Department of Mathematical and Computing Sciences, Tokyo Institute of Technology; May 2018 Download: [Compressed Postscript][PDF] Entry Submitted: 05/09/2018 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  