A mathematical programming approach to marker-assisted gene pyramiding

Stefan Canzar, Mohammed El-Kebir

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - 11th International Workshop, WABI 2011, Proceedings
Number of pages13
StatePublished - 2011
Externally publishedYes
Event11th Workshop on Algorithms in Bioinformatics, WABI 2011 - Saarbrucken, Germany
Duration: Sep 5 2011Sep 7 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6833 LNBI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other11th Workshop on Algorithms in Bioinformatics, WABI 2011

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'A mathematical programming approach to marker-assisted gene pyramiding'. Together they form a unique fingerprint.

Cite this