TY - GEN

T1 - A mathematical programming approach to marker-assisted gene pyramiding

AU - Canzar, Stefan

AU - El-Kebir, Mohammed

PY - 2011

Y1 - 2011

N2 - In the crossing schedule optimization problem we are given an initial set of parental genotypes and a desired genotype, the ideotype. The task is to schedule crossings of individuals such that the number of generations, the number of crossings, and the required populations size are minimized. We present for the first time a mathematical model for the general problem variant and show that the problem is -hard and even hard to approximate. On the positive side, we present a mixed integer programming formulation that exploits the intrinsic combinatorial structure of the problem. We are able to solve a real-world instance to provable optimality in less than 2 seconds, which was not possible with earlier methods.

AB - In the crossing schedule optimization problem we are given an initial set of parental genotypes and a desired genotype, the ideotype. The task is to schedule crossings of individuals such that the number of generations, the number of crossings, and the required populations size are minimized. We present for the first time a mathematical model for the general problem variant and show that the problem is -hard and even hard to approximate. On the positive side, we present a mixed integer programming formulation that exploits the intrinsic combinatorial structure of the problem. We are able to solve a real-world instance to provable optimality in less than 2 seconds, which was not possible with earlier methods.

UR - http://www.scopus.com/inward/record.url?scp=80052998452&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052998452&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-23038-7_3

DO - 10.1007/978-3-642-23038-7_3

M3 - Conference contribution

AN - SCOPUS:80052998452

SN - 9783642230370

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 26

EP - 38

BT - Algorithms in Bioinformatics - 11th International Workshop, WABI 2011, Proceedings

T2 - 11th Workshop on Algorithms in Bioinformatics, WABI 2011

Y2 - 5 September 2011 through 7 September 2011

ER -