8 | metabolic engineering strategies I

Question 1

What is the motivation behind coupling product formation to growth?

Answer 1

• force cell to produce desired compound as by-product of growth
• → ensures production is evolutionarily stable.

Question 2

What is strong coupling in metabolic engineering?

Answer 2

KO strategy: product formation strongly coupled to growth (biomass production)
ensure any growth-supporting flux dist also produces product > threshold.

Question 3

What is weak coupling?

Answer 3

Product is only formed at the optimal growth flux, not necessarily under all conditions.

Question 4

What is the exhaustive KO strategy covered in lecture 8 on metabolic engineering?

Answer 4

• Try all possible subsets of knock-outs from the list of genes.
• Evaluate product yield or other objectives, solution = maximum of all maxima

Question 5

Write the LP for an exhaustive knock out enumeration.

Answer 5

For every subset 𝑇 ⊆ 𝐿:
max 𝑣_{𝑐ℎ𝑒𝑚𝑖𝑐𝑎𝑙}
s.t.
𝑁𝑣 =0
∀𝑗 ∈ 𝑇, 𝑣_𝑗= 0,
∀𝑖, 𝑖 ∉ 𝑇,𝑣_𝑖^𝑚𝑖𝑛 ≤ 𝑣_𝑖 ≤ 𝑣_𝑖^𝑚𝑎𝑥
𝑣_𝑏𝑖𝑜 ≥ 𝛼𝑧^∗
If we want sufficient high product yield to be at some level of biomass yield:
where 𝑧^∗ is the optimal growth.

Question 6

What additional constraint ensures viability in exhaustive knock-out tests?

Answer 6

v_bio ≥ α · z, where z is wild-type biomass flux

Question 7

What are the limitations of exhaustive knock-out search?

Answer 7

• Combinatorial explosion: infeasible for large gene lists
• Cannot scale to full genome-wide searches

Question 8

What is a bi-level optimization problem?

Answer 8

• One optimization problem (outer) depends on the solution of another (inner)
• I.e two nested optimizations
• The outer objective uses the result of the inner optimization

Question 9

Why do bi-level problems appear in metabolic engineering?

Answer 9

• The outer problem wants to maximize product formation (engineer)
• The inner problem responds by optimizing its own growth (cell)
• The engineering strategy must account for the internal optimization

Question 10

In OptKnock, what are the outer and inner problems?

Answer 10

• Outer: maximize v_target (e.g. product formation) by choosing KOs
• Inner: maximize v_bio (growth) given knock-outs

Question 11

How are knock-outs encoded in OptKnock?

Answer 11

• Binary variable y_i ∈ {0, 1}
• y_i = 1 → reaction is active
• y_i = 0 → reaction is knocked out → v_i = 0
• Use bounds: y_i * v_i^min ≤ v_i ≤ y_i * v_i^max

Question 12

What does the inner problem in a bi-level formulation depend on?

Answer 12

• The outer decision variables (e.g. knock-outs y)
• These change the feasible region for the inner problem
• The inner LP is parameterized by y

Question 13

What makes OptKnock a mixed-integer bi-level program?

Answer 13

• Outer layer includes binary variables y_i
• Inner problem is a linear program over flux variables v
• The feasible set for v depends on y

Question 14

What is OptKnock?

Answer 14

• A bi-level MILP to find knock-outs that couple growth and production
• Automates the search for knock-out designs

Question 15

How is the number of knock-outs restricted in OptKnock?

Answer 15

Add a constraint for K, the max allowed deletions: ∑(1−y_i) ≤ K

Question 16

What is the full program for OptKnock (Burgard et al. (2003) Biotech. & Bioeng.)

Answer 16

max over y: v_chemical
st:
max v_bio
st:
N v = 0
for all i ≤ 1 ≤ m, y_i · v_i^min ≤ v_i ≤ y_i · v_i^max
y_i ∈ {0, 1}
∑_i=1^m(1−y_i) ≤ K

Question 17

What does the inner problem in OptKnock represent?

Answer 17

The cell’s behavior: maximize biomass production given knock-outs

Question 18

What does the outer problem in OptKnock represent?

Answer 18

The engineer’s goal: maximize product formation by choosing which knock-outs to apply

Question 19

What assumptions does OptKnock make about the cell?

Answer 19

• The cell optimizes growth
• Product formation is only induced indirectly via knock-outs

Question 20

Why are bi-level problems difficult to solve?

Answer 20

• The inner problem changes with each outer decision
• You can’t just solve them separately
• to nesting, discrete nature of int vars → problem non-convex, combinatorial

Question 21

What does “combinatorial” mean in the context of bi-level optimization?

Answer 21

• refers to having to choose among many discrete combinations, eg KO sets
• Each combination may lead to a different inner solution
• possible combinations can grow very large - ‘combinatorial explosion’
• Can make problem hard to solve efficiently

Question 22

Why can’t bi-level problems be solved directly?

Answer 22

Inner LP depends on outer variables → standard MILP solvers unable to handle it directly.

Question 23

How can bi-level problems be solved in OptKnock?

Answer 23

Two approaches:
* By replacing the inner LP with its dual problem
* Apply Karush-Kuhn-Tucker (KKT) conditions (optimality) to connect primal, dual

Question 24

What are the KKT conditions used to solve bi-level problems?

(not so relevant ! )

Answer 24

• Stationarity
• Primal feasibility
• Dual feasibility
• Complementary slackness

Question 25

What is complementary slackness?

Answer 25

For each constraint:
* If it’s active, dual variable may be positive
* If it’s inactive, dual variable is zero

Question 26

What are mixed-integer linear programs (MILPs)?

Answer 26

LPs with some variables required to be integers (e.g. binary knock-out indicators)

Question 27

What is LP duality?

Answer 27

• Every LP has a dual problem
• The dual variables represent the shadow prices of the constraints

Question 28

What is a shadow price in LP duality?

Answer 28

Each constraint in the primal has a shadow price.
* = The value of a dual variable corresponding to a primal constraint
* = how much objective function would improve if that constraint relaxed by 1 unit
* AKA marginal value of a resource

Question 29

If you have n variables and m constraints in an LP, how many constraints will you have in its dual?

Answer 29

• m variables
• n constraints

Question 30

What is the optimality property in LP duality?

Answer 30

Let 𝑥 be a feasible solution to a primal LP, and 𝜇 be a feasible solution to the dual LP.
If 𝑐^𝑇𝑥 = 𝑏^𝑇𝜇 then 𝑥 and 𝜇 are optimal solutions to the primal and dual LPs, respectively.

Question 31

What is the strong duality property in LP duality?

Answer 31

• If primal has finite optimal solution, then so does its dual, and these values are equal.
• ie max_𝑥 𝑐^𝑇𝑥 = min_𝜇 𝑏^𝑇𝜇
  That means:
• Solve the primal → get a value; Solve the dual → get a value. ✅ Both values are equal
  This only holds if:
• The primal or dual has a feasible solution (satisfies all constraints)
• The problem is bounded (no infinite solutions)

Question 32

How do you convert a primal LP into its dual (without Lagrangian)?

Answer 32

• Each constraint in the primal becomes a variable in the dual
• Each variable in the primal becomes a constraint in the dual
• The primal objective coefficients become RHS values in the dual constraints
• The primal constraint matrix A is transposed in the dual

Question 33

In LP duality, what happens to ≥ constraints in the primal?

Answer 33

• They become ≤ constraints in the dual
• Their corresponding dual variables must be ≥ 0

Question 34

What is the dual of this primal LP?
min c^T x
s.t. A_ineq x ≥ b_ineq
x ≥ 0
A_eq x = b_eq

Answer 34

max b_ineq^T y₁ + b_eq^T y₂
s.t. A_ineq^T y₁ + A_eq^T
y₂ ≤ c
y₁ ≥ 0

Question 35

Why is LP duality useful in OptKnock?

Answer 35

• Allows removing inner LP, replacing with constraints involving dual variables
• Converts the bi-level problem to a single-level MILP

Question 36

What are two approaches to flattening bi-level optimization problems?

Answer 36

• LP duality: replace the inner LP with its dual and enforce strong duality
• KKT conditions: use stationarity, feasibility, and complementary slackness via the Lagrangian

Question 37

Do LP duality and KKT methods give the same solution for bi-level LPs?

Answer 37

• Yes, they both produce the same optimal result
• They enforce optimality of the inner problem in different ways

Question 38

Do LP duality and KKT produce the same flattened single-level program?

Answer 38

No, the formulations differ
* LP duality leads to a more compact and structured MILP
* KKT-based reformulations are often larger and more complex

Question 39

What does it mean to “not use the Lagrangian approach” for duality?

Answer 39

• You should derive the dual using the standard LP rulebook, not calculus or KKT
• Don’t introduce Lagrange multipliers
• Just work structurally from constraint-to-variable transformation

Question 40

For a primal minimization problem:

min c^Tx
s.t.
A x ≥ b
x ≥ 0

What would be the key steps to formulate the dual?

Answer 40

Follow the standard duality principles in optimization.

1. Identify Primal Components:
2. Assign Dual Variables:
3. Formulate Dual Objective:
4. Formulate Dual Constraints:

Question 41

For a primal minimization problem:

min c^Tx
s.t.
A x ≥ b
x ≥ 0

What is the dual?

Answer 41

max_𝜇 4𝜇
s.t
𝜇 = 0

Perplexity explanation:

Original (primal) problem:
Minimize y
st
y ≥ 0,
x + y ≥ 4.

1. Identify Primal Components:
Variables:
y≥0,
x (unrestricted).
Objective: Minimize y
Constraints: One explicit constraint
x+y≥4.

Assign Dual Variables:
Each primal constraint becomes a dual variable. Here, the constraint
x+y≥4 corresponds to a dual variable
λ≥0.

Formulate Dual Objective:
The dual objective is derived from the right-hand side of the primal constraint multiplied by λ:
4λ.

Formulate Dual Constraints:
For each primal variable, create a dual constraint based on its sign:
For x (unrestricted): The coefficient of x in the primal constraint (1) forms an equality constraint in the dual: λ=0.
For y (non-negative): The coefficient of y in the primal constraint (1) forms an inequality constraint: λ≤1.
Combine Constraints:
The dual constraints are λ=0, λ≤1, and λ≥0.

Dual Problem:
Maximize 4λ
subject to
λ=0,
λ≥0,
λ≤1.

Interpretation:
The only feasible solution for the dual is λ=0, yielding an optimal value of 0 This matches the primal optimal value y=0 (achieved when x≥4), demonstrating strong duality.

Summary:
The dual LP is trivial in this case because the unrestricted variable x forces
λ=0. This ensures the primal and dual optimal values align, satisfying the duality theorems in linear programming.

Question 42

What is the simplified OptKnock reformulation/approximation from the exercise, often used computationally, which:

• Turns the bilevel OptKnock problem into a single-level MILP
• Focuses on minimizing the number of knockouts
• Adds a small constant ε to soften knockouts

?

Answer 42

min ∑ y_i

s.t.

N v = 0
v_bio ≥ α · z*
v_target ≥ β · w_target
v ≥ 0
∀ i:
 (1 − y_i) · ε ≤ v_i
 v_i ≤ (1 − y_i) · v_i^max + y_i · ε
y ∈ {0,1}