LP (AI generated from transcript) Flashcards
What can Max Flow be modeled as?
Linear Programming (LP)
Max Flow models the flow of resources through a network while adhering to constraints.
What is the objective function for Max Flow in LP?
Maximize sum of flow for all edges in E
What are the constraints for Max Flow in LP?
- Must have non-negative flow
- For every vertex, flow in must equal flow out
In a 2D LP example, what is the objective function?
A + 6B
What are the constraints in the 2D LP example?
- A <= 300
- B <= 200
- A + 3B <= 700
- A, B >= 0
What does the orange area represent in the 2D LP geometric view?
The feasible region
What is the optimal point in the 2D LP example?
x1=100 and x2=200 with profit = 1300
Is Linear Programming in P or NP?
Linear Programming is in P
What is Integer Linear Programming (ILP)?
NP-Complete
What characterizes the optimal point in LP?
Lies at a vertex of the feasible region
How many vertices are in the given 2D LP example?
5 vertices: {(0,0), (0, 200), (100,200), (300,0), (300, ~120)}
True or False: A feasible region is convex.
True
What happens to the feasible region defined by the intersection of half spaces?
It must be a convex set
In the standard form of LP, what does the objective function maximize?
A linear function of n variables
What are the coefficients in the standard form of LP?
c1, c2, …, cn
What constraints are included in the standard form of LP?
- m constraints
- Non-negativity constraints
What is the significance of non-negative constraints in LP?
Used to find a trivially feasible point or to determine if the LP is infeasible
What is the first step in converting a linear program to standard form?
To minimize a linear function, multiply the objective function by -1
How do you handle equality constraints when converting to standard form?
Replace with 2 inequality constraints
What is the geometric view of LP with n variables?
Corresponds to points satisfying all n+m constraints
What does the Simplex algorithm do?
Solves linear programs in polynomial time
What is the starting point for the Simplex algorithm?
Feasible point, typically the zero vector
What happens if no higher-value neighbors are found in Simplex?
The current vertex is optimal
What is an example of infeasibility in LP?
Non-intersecting half spaces yield an empty feasible region
What is the result of an unbounded LP?
Infinite optimal value of the objective function
What is the method to detect infeasibility?
Add a single new variable z that is unrestricted
What is the dual LP?
A minimization problem derived from the original maximization LP
What do the coefficients from the original LP constraints define in the dual LP?
The objective function of the dual LP
What is the relationship between the number of variables in the primal LP and the dual LP?
Orig: # Vars → Dual: # Constraints
What is the relationship between the number of constraints in the primal LP and the dual LP?
Orig: # Constraints → Dual: # Vars
What is the general objective of the primal LP?
Maximize a profit function represented by obj. func. max(cTx) under constraints Ax≤b, x≥0
What does the Dual LP aim to do?
Minimize profit, finding smallest upper bound by obj. func. minbTy
What constraints are derived from the primal LP’s objective function?
ATy≥c, y≥0
What is the relationship between the number of variables and constraints in the primal and dual LPs?
Orig: # Vars → Dual: # Constraints; Orig: # Constraints → Dual: # Vars
What is required for the Dual LP formulation?
The primal LP must be in canonical form with ‘at most’ inequalities and maximization objective
True or False: The Dual LP of a Dual LP is the original Primal LP.
True
How many variables are in the Dual LP if the primal has 2 constraints?
2
How many constraints are in the Dual LP if the primal has 3 variables (excluding non-negative constraints)?
3
Fill in the blank: The values of d are _______.
[1, -3]
What does the Weak Duality theorem state?
For any feasible solution x to the primal and y to the dual, cTx≤bTy
What is the implication of matching objective function values in primal and dual LPs?
Both are optimal (x = optimal max, y = optimal min)
What does the Strong Duality theorem guarantee?
The existence of optimal primal-dual pairs if both LPs are feasible and bounded
What happens if the primal LP is unbounded?
The dual LP is infeasible
What is the first step to check if a primal LP in canonical form is unbounded?
Check feasibility by adding new z variable Ax+z≤b, x≥0
What must be checked for the dual LP to determine primal unboundedness?
If the dual is infeasible
What is the key idea behind Strong Duality?
A feasible and bounded primal LP has an equivalent dual LP that is also feasible and bounded
What is the max flow min cut theorem in relation to LPs?
Max flow = primal LP; min cut = dual LP
Fill in the blank: The constraints in the primal LP must be transformed into _______.
Canonical form
