Bilevel optimization techniques in computational strain design

Over the past decade a number of bilevel optimization techniques were introduced for computational strain design leading to the overproduction of biochemicals. In this paper, we provide an algorithmcentric description of the OptKnock and OptForce strain-design protocols, highlight their differences and demonstrate their application for a prototypical overproduction problem. The derivation of the equivalent MILP representation in both cases is described in detail along with provisions that lead to significantly improved performance. Comparison between the intervention strategies of OptKnock and OptForce for the overproduction of succinate in Escherichia coli reveal that while OptKnock couples succinate with biomass production, OptForce suggests interventions that improves the minimum production of succinate. Further, OptForce is more tractable as it identifies interventions from only the subset of reactions that must change in the overproducing strain. Overall, this paper highlights the computational challenges faced in strain design and the methodological choices explored by OptKnock and OptForce. (C) 2014 Elsevier Ltd. All rights reserved.