Linear Programming Flashcards
True or false? If an LP is feasible and bounded, the optimum is achieved at a vertex of the feasible region?
True.
When is there no optimal solution to an LP?
- The LP is infeasible. That is, the constraints are so tight that it is impossible to satisfy all of them. For example: x<=1, x>=2. This depends on the constraints.
- The LP is unbounded. This happens when the constraints are so loose that the feasible region is unbounded and so it is possible to achieve arbitrarily high objective values. This depends on the objective function.
Describe the standard form of an LP
n variables, m constraints
n variables: x = x1, x2, …, xn
objective function: max c1 x1 + c2 x2 + … + cn xn
constraints:
Ax <= b:
a11 x1 + … + a1n xn <= b1
a21 x1 + … + a2n xn <= b2
.
.
.
am1 x1 + …. + amn xn <= bm
x >= 0
Describe the feasible region of an LP with n variables and m constraints
The feasible region is the intersection of n+m half-spaces, which is a convex polyhedron.
Describe the simplex algorithm
Simplex is a walk on corners:
- Start at x=0. If this doesn’t satisfy any m-constrains, this LP is not feasible.
- Look for a neighbor vertex with a higher objective value and move there. Repeat until no such neighbor can be found.
- Return current location. This is an optimum because the feasible region is convex.
How can you check if an LP is feasible?
Add a z to the constraints (Ax <= b) and solve for a maximum to see if a solution exists:
Ax + z <= b
If z>=0, the LP is feasible. If z<0, it’s not.
If an LP is not feasible, the problem is not solvable.
What is the standard form of a dual LP?
Given an LP with c, A, x, b with n variables and m constraints:
m variables and n constraints:
m variables (one for each constraint in LP): y1, y2, ..., ym objective function: minimize b1 y1 + ... + bm ym constraints:
A^T y >= c:
a11 y1 + a21 y2 + … + am1 ym >= c1
.
.
.
a1n y1 + a2n y2 + … + a mn ym >= cn
y>=0
Weak duality theorem
Take feasible x for primal LP and feasible y for dual LP:
c^T x <= b^T y
**The dual LP solution with y is an upper bound for the primal LP objective function
If we find a feasible x for an LP and a feasible y for a dual LP where c^T x = b^T y, what does this imply about x and y? What does it imply about the LP and dual LP?
This implies x and y are optimal. It also implies that the primal and dual LPs are feasible and bounded.
This is a corollary of the weak duality theorem.
True or false? If the primal LP is unbounded, the dual is infeasible?
True. This is a corollary of the weak duality theorem. Consider that if the Primal LP can go to infinity, there is no upper bound and so the Dual LP is infeasible.
True or false? If the dual LP is unbounded, the primal LP is infeasible?
True. This is a corollary of the weak duality theorem. Consider that if the Dual LP can go to negative infinity, there is no lower bound and the Primal LP is infeasible.
What is the strong duality theorem?
Primal LP is feasible and bounded IFF the dual LP is feasible and bounded.
Primal LP has an optimal x* IFF dual LP has an optimal y* and c^T x* = b^T y*
What can you determine from checking whether or not the Dual LP is feasible or not?
If the dual LP is infeasible, than the primal LP is either:
- Infeasible (which can be checked directly using a z)
- Unbounded (has no optimum)
If the dual LP is feasible, then the primal LP is:
- Bounded (has an optimal)
We saw three algorithms that we can use to approximate the solution to Max-SAT. What are they called, and what fraction-approximation do they achieve?
- Simple: 1/2 approximation algorithm.
- LP-based: (1-1/e) approximation algorithm.
- Best of 2: 3/4 approximation algorithm
What does it mean to produce a fraction-approximation algorithm to Max-SAT?
1/2 approx. algorithm means the algorithm returns l-number of satisfied clauses and l >= m*/2
m* is the maximum number of satisfiable clauses in a given formula f. If #-clauses in f is m, m* <= m.
Generally:
fraction-approximation means l >= fraction x m*
