User:Jarle Pahr/OptKnock

From OpenWetWare
Jump to: navigation, search

Notes on the OptKnock algorithm:

OptKnock is a bi-level optimization algorithm that seeks to optimize metabolite production through gene knockouts, subject to maximization of the cellular objective.

Problem formulation:

  • Direct solution intractable
  • Solution approach based on LP duality theory. Basis: "For every linear programming problem (primal) there exists a unique optimization problem (dual) whose optimal objective value is equal to that of the primal problem." (Burgard 2003).


Xu et al ( point out a flaw in the justification of the transformation of the bi-level problemt o a MILP as performed by Burgard et al. They cite Scott DeNegre in INTERDICTION AND DISCRETE BILEVEL LINEAR PROGRAMMING (PhD thesis), who writes:

"In their model, Burgard et al. (2003) utilize binary upper-level variables to represent yes/no decisions regarding the gene knockouts and reformulate the the problem using lower-level duality. Rather than using KKT conditions, the y instead enforce lower-level primal and dual feasibility and require the primal and dual objectives to be equal. However, they neglect to include the lower-level primal variables in the dual object ive and, thus, erroneously state that a MILP formulation has been derived. "

Related methods