LP Flashcards
Where are vertices of feasible region located
Corner of feasible region polygon
Proof why feasible region is a convex set
feasible region is defined by the intersection of half spaces
Where do optimal points lie in feasible region
vertex of feasible region
When is a vertex a global optima
When its value is “better” than its neighbors
[Canonical Form]
Given obj func:
x1 + 6x2 + 10x3
What are its coefficients
1, 6, 10
Importance of non-negative constraints
- Use to find a trivially feasible points
- Determine feasible region is empty, therefore LP is infeasible
Given obj func and constraints:
x1 + 6x2 + 10x3
x1 <= 300
x2 <= 200
x1 + 3x2 + 2x3 <= 1000
What is its constraint matrix A
[[ 1, 0, 0 ], [ 0, 1, 0 ], [ 1, 3, 2 ]]
[Converting Linear Algebra to Standard Form]
How to minimize objective function cTx
Multiply by -1, -cTx
[Converting Linear Algebra to Standard Form]
Given constraint, how to convert to standard form:
a1x1…anxn ≥ b
Need to change to “at most” form
Multiply by -1 to flip inequality:
-a1x1…-anxn ≤ b
[Converting Linear Algebra to Standard Form]
Given equality constraint, how to convert to standard form:
a1x1…anxn = b
Create 2 inequality constraints
a1x1…anxn ≤ b, and
a1x1… anxn ≥ b
Then flip the second to meet standard form
[Converting Linear Algebra to Standard Form]
Why are strict inequalities not allowed in LPs
With strict inequalities, the feasible region would exclude its boundary points
[Converting Linear Algebra to Standard Form]
How to handle unconstrained variables (e.g. “x”)
Split it to 2 components, x +& x-, both with non-negative values.
x = x+ - x-
Given objective function
min 3x_1 - 2.5x_2 + x_3
Convert c values into standard form
c = [[ -3 ], [ 2.5 ], [ -1 ]]
Given objective function
minimize 3x_1 - 2.5x_2 + x_3
Convert c values into standard form
Convert constraint to standard form
x2 + x3 >= 300
Negate to reverse inequality
-x2 - x3 <= 300
Convert constraint to standard form
0.5x + 7y - 2z = 4
First, split the equality into two inequalities:
0.5x + 7y - 2z ≤ 4
0.5x + 7y - 2z ≥ 4
For the second inequality, multiply by -1 to get the standard “less than or equal to” form:
0.5x + 7y - 2z ≤ 4
-0.5x - 7y + 2z ≤ -4
[Geometric View]
Given m constraints and n non-negativity constraints we get _____ constraints
n+m constraints
[Geometric View]
Given n+m constraints, where does the feasible region lie
Intersection of n+m half spaces (convex polyhedron)
[Geometric View]
Where do vertex lie in feasible region with respect to constraints
n constraints met with equality (=)
m constraints met with inequality (<=)
[Geometric View]
Upper bound of vertex neighbors
at most nm neighbors
Simplex algorithm
- Start at x=0
- Look for neighboring vertex with strictly higher objective value
- Move to neighbor, repeat 2
- Else, return x as optimal
T/F
Simplex algorithm can move to any point in the feasible region
False
Simplex algorithm walks on vertices (corners)
[LP Optimality]
Define infeasible
Feasible region is empty
[LP Optimality]
Define unbounded
Objective function can reach infinite optimal value
Constraint 1 (x + y <= 1) and constraint 2 (3x + 2y >= 6) yield non-intersecting half spaces.
Why is this LP infeasible
It creates 2 non-intersecting half-spaces.
No x,y value can meet both constraints
Infeasibility is not dependent on objective function. Give a reason why
If you set constraints that create non-intersecting regions, you can never find optimal solution.
Unboundedness is specific to the objective function. Give a reason why
Same constraints can produce bounded or unbounded problems depending on which direction the objective function points.
Constraints determine the shape of the feasible region, objective function determines whether we can improve indefinitely within that region.
Conditions that make LP unbounded (2)
- Constraints that create an unbounded feasible region (extending to infinity in some direction)
- An objective function that improves in that same unbounded direction
[Infeasible]
Steps to detect if LP is infeasible
- Add new variable z to constraint Ax + z <= b & x >= 0
- Set new objective function “max z”
- Solve for z
If optimized z is non-negative, original LP is feasible.
If z is negative, original LP is infeasible
[Infeasible]
Why does adding z always satisfy <= b?
Because z is unrestricted, thus we can add a large non-negative number to always meet constraint.
[Optimality]
Optimum of LP is achieved at a vertex of the feasible except 2 cases
Define the two cases
- Infeasible - Feasible region is empty, ie. no variable values will meet all constraints
- Unbounded - Given constraints and obj function, there is no bounds to optimization
Weak Duality definition
If both primal and dual LPs are feasible, the inequality c^Tx <= b^Ty always holds
Weak Duality theorem if obj func of x and y are equal
c^Tx = b^Ty
Both x and y are optimal
x = optimal max
y = optimal min
Strong Duality theorem guarantee if primal-dual pairs are feasible and bounded
We can find an optimal max x and min y value that is equal.
[Unbounded]
If primal linear program (LP) is unbounded , dual LP is ____
If dual is infeasible primal is ______.
Infeasible
Infeasible or Unbounded
[Weak Duality]
If Dual LP is infeasible, then primal is:
Unbounded OR infeasible
T/F
Given primal-dual pair cTx ≤ bTy, if primal is infeasible then dual can’t be infeasible
False
Not a bidirectional relationship, both primal and dual can be infeasible. So the implication has only one direction.
[Unbounded]
Why is just checking if dual LP is unbounded not enough to determine primal is unbounded
If dual is unbounded, primal could be EITHER unbounded or infeasible.
We don’t know which unless we check primal.
2 steps to determine if LP in canonical form is unbounded
- For primal LP, check feasibility by adding z variable and maximizing z. If solution has non-negative z value, primal is feasible.
- For dual LP, check feasibility. If dual = infeasible, primal is unbounded (not infeasible since we confirmed it is feasible in step 1)
Strong duality definition
If primal and dual LPs are both feasible and bounded, then their optimal solutions are equal:
c^Tx = b^Ty
(LHS take max, RHS takes min)
Difference between weak and strong duality theorem
Weak duality only shows inequality between feasible primal / dual solutions.
cTx ≤ bTy
Strong duality shows equality between bounded + feasible primal / dual solutions
If the original LP is feasible and bounded, then the dual LP is:
also feasible and bounded.
The dual of the dual LP is….
primal LP
T/F
It is impossible for both the original LP and the dual LP to be infeasible.
False
T/F
Feasibility means there must be only one solution to the LP problem
False.
this can mean only one solution, or infinitely many solutions.
T/F
An infeasible LP can still be bounded
False
the discussion of boundedness only makes sense for feasible LPs.
[Geometric view]
Max number of vertices with n equality constraints and m inequality constraints?
n+m choose n
(combinatorial)
How to handle converting to duals when some variables are missing
fill in variables with zero cofficients
max x1 - 0x2 - 2x3 s.t. x1 - x2 - 0x3 <= 1 0x1 + 2x2 - x3 <= 1 x1, x2, x3 >= 0 min y1 + y2 s.t. y1 >= 1 -y1 + 2y2 >= 0 -y2 >= -2
