10 | Tricks from LP w applications Flashcards
Before lecture 10 we encountered linear and quadratic programs modeling metabolism such as FBA, FVA, ROOM, MOMA, etc.
Why consider more complex objectives or constraints?
- Better capture biological reality
- Model behaviors like enzyme efficiency or regulatory logic
What is the tradeoff of using complex objective functions?
- Increased computational complexity
- Need for transformations to LP or MILP
What is an example of transforming a non-linear problem to LP?
- Flux Coupling Analysis (linear fractional program)
- Transformed using Charnes-Cooper transformation
What is the goal of pFBA?
Aims to determine the subset of genes and proteins that may contribute to the most efficent metabolic topology under the given growth conditions
* Identify minimal set of active enzymes, most efficient subset of pathways
* Model efficient enzyme usage under growth constraints
* Mimics minimal enzymatic cost for maximal growth
What modifications are made to reactions in pFBA?
- Reversible reactions are split into two irreversible reactions
- (but we learnt a trick how to deal with an LP without splitting)
What are the two steps of pFBA?
- Step 1: Solve FBA to determine vbioopt
- Step 2: Minimize total flux of gene-associated rxns under steady-state, fixed growth
How can genes be classified based on pFBA?
- Essential
- pFBA optima
- Enzymatically Less Efficient (ELE)
- Metabolically Less Efficient (MLE)
- pFBA no-flux
pFBA classifications - what does ELE mean?
- Enzymatically Less Efficient
- there are alternative pathways that meet same need with less steps
pFBA classifications - what does MLE mean?
- Metabolically less efficient
- leading to reduced growth, if used
pFBA classifications - what does pFBA no-flux mean?
No flux in the experimental conditions
What is the pFBA optimization problem (with split reversible reactions)?
- min ∑ vi (for gene-associated reactions)
- s.t. Nv = 0
- vbio = vbio,lb
- 0 ≤ v ≤ vmax
How can a flux minimization problem be handled without reaction splitting?
- Replace vi with vi+ - vi-
- Enforce vi+, vi- ≥ 0
Consider the pFBA LP without splitting reversible reactions.
minv ∑ |vi|
s.t.
Nv = 0
vbio = vbio,lb
vmin ≤ v ≤ vmax
Why can’t LP be directly applied to minimize ∑|vi|?
- Because vi can be negative
- such an absolute value function is not additive nor homogeneous → nonlinear!
In pFBA, how can we transform vi to make it LP-compatible?
Introduce the following substitution with two new non-negative variables:
vi = vi+ − vi−
→ |vi| = vi+ + vi−
Such that: vi+, vi− ≥ 0
∑|vi| = ∑(vi+ + vi−) → objective is now linear
When using the trick for making problems minimizing all reaction fluxes without having to split reversible reactions by introducing vi = vi+ − vi−…
Why can we assume at most one of vi+ or vi− is positive at optimality?
Because the substitution vi = vi+ − vi− allows us to reduce both by min(v+, v−) and keep vi unchanged.
→ both being positive reduces the objective → contradicts optimality
→ optimal solution forces one of the two to be zero
—
Very elegant idea:
If both are positive, you can subtract the smaller of the two from both (i.e., move v closer to zero) → reduces the objective value
So at optimality, one of the two is always zero
In other words:
You never need to explicitly add a constraint forcing them to not be positive simultaneously
It emerges naturally from the LP optimality condition
–
from slide:
Suppose that both 𝑣𝑖+</sup) and 𝑣𝑖− are non-zero (positive) and let the smaller be of value 𝛿. Subtracting 𝛿 from both does not affect 𝑣𝑖 = 𝑣𝑖+</sup) - 𝑣𝑖−
However, it reduces the value of the objective 𝑣𝑖+</sup) + 𝑣𝑖− by 2𝛿.
contradicts the optimality!
What is the form of a minmax problem?
- minx maxk∈K ∑ ckj xj
- k∈K indexes multiple cost functions - for each k theres a different linear cost.
- The objective is to find the x that makes worst of the values as small as possible.
- ie trying to minimize the maximum over several linear expressions!
Consider the minmax problem:
minx maxk∈K ∑ ckj xj
st:
Ax ≤ b
x ≥ 0
How can the minmax problem be turned into LP?
- Introduce an additional decision variable, eg z
- Add constraints: ∑ ckj xj ≤ z for all k ∈ K
- This ensures that optimal value for z will not be larger than the maximum over all k
- New objective: minimize z over x,z
What is an everyday example of a min–max problem?
Why would you use min–max in this bakery example?
A bakery delivers to 3 cafés
Each café wants a different amount of baked goods (e.g., 3x₁ + 2x₂)
You can’t perfectly satisfy all
Goal: Choose x₁ and x₂ to minimize the maximum dissatisfaction
Turns into:
min z
s.t. each café’s dissatisfaction ≤ z
Why would you use min–max in this bakery example?
* To distribute resources fairly
* Prevent any one café from being too disappointed
* Smooth out extremes
* Objective: smallest worst-case cost
In detail:
🍞 Scenario: You run a bakery
You bake:
* Baguettes (x₁)
* Croissants (x₂)
You want to deliver these to 3 cafes, and each one wants a different amount:
* Café A - 3x₁ + 2x₂
* Café B - 2x₁ + 5x₂
* Café C - 4x₁ + 1x₂
But due to delivery delays, you might not satisfy every café perfectly.
You don’t want any one café to be too disappointed.
🎯 Goal:
Minimize the maximum dissatisfaction of any café.
This is a min–max problem:
minx₁,x₂ max {
3x₁ + 2x₂, // Café A
2x₁ + 5x₂, // Café B
4x₁ + 1x₂ // Café C
}
You’re trying to find x₁ and x₂ (how many baguettes and croissants to bake) that make the worst café the least unhappy.
💡 Why use min–max?
This is a fairness strategy:
* You’re not trying to make one café super happy at the cost of others
* You’re trying to balance deliveries, so no café is hit the hardest
* It’s like smoothing out the extremes.
✅ LP transformation
Introduce a variable z = “maximum dissatisfaction”
Add constraints:
* 3x₁ + 2x₂ ≤ z
* 2x₁ + 5x₂ ≤ z
* 4x₁ + 1x₂ ≤ z
Now you can minimize z subject to those constraints (and whatever other constraints you have, like time or flour limits), and you’ve turned it into an LP.
What is an example of min–max in metabolic modeling?
- You want a mutant to stay close to wild-type behavior
- Instead of minimizing total deviation (MOMA), minimize largest individual rxn change
- avoids big deviations in any one reaction
- Useful when one large change would be biologically unrealistic
What is an example of a discontinuous variable and what is the trick to incorporate these into LPs?
- x = 0 or l ≤ x ≤ u
- Linear programming allows only modeling with variables that take continuous values
- → Introduce binary variable eg y ∈ {0,1}
- Constraint: ly ≤ x ≤ uy
We then get: - y = 0 ⇒ x = 0
- y = 1 ⇒ l ≤ x ≤ u
eg optReg etc! –> MILP
When do fixed costs arise in metabolic modelling?
- e.g. for newly synthesized enzymes - Modeling set-up costs
- Modeling of two mutually exclusive situations
What is the LP and cost function for a fixed cost setup? Why is this not solvable as is with LP?
Max over x of C(x)
St:
aix + ∑j aijwj ≤ bi
xi, wj ≥ 0
Where:
C(x) = 0 if x = 0
C(x) = k + c*x if x > 0
not linear and not continuous → not an LP
Consider the fixed cost setup:
Max over x of C(x)
St:
aix + ∑j aijwj ≤ bi
xi, wj ≥ 0
Where:
C(x) = 0 if x = 0
C(x) = k + c*x if x > 0
How can this be modeled in LP?
(NEED TO UNDERSTAND THIS BETTER)
* Introduce binary indicator variable y
x = 0 → y = 0
x > 0 → y =1
* Link with x using the constraint: εy ≤ x ≤ My
* Cost function becomes: C(x,y) = ky + cx
Final LP:
Maxx,y,wC(x)
St:
aix + ∑j aijwj ≤ bi
εy ≤ x ≤ My
xi, wj ≥ 0
** y ∈{0,1}**
What is an either-or constraint? Give an example. Is this an LP
Exactly one of two (or more?) constraints must be satisfied
maxx cjxj
s.t.
∑ a1jxj ≤ 𝑏1
∑ a2jxj ≤ 𝑏2
Where exactly one of the conditions (1) or (2) must hold
Not an LP - In linear programmig, all constraints must be satisfied.
