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 -