Exam 3 part 2 Flashcards
What is linear programming?
General technique for solving optimization problems
What is the linear programming outline for max-flow problem?
input: G(V,E) with capacities ce > 0
m for every e in E
objective function: sum fsv
subject to:
for every e in E: 0 <= fe <= ce (flow has to be non negative and at most the edge capacity)
for every v in V - {s, t}
- sum wv in edge fwv = sum vz in edge fvz
(total flow into v has to equal the total flow out of v)
objective function is a max or a min of a linear function
And there are constraints on the variables
Give an example of a linear program
Company makes products A and B
How many of each to maximize profit?
- Each unit of A makes profit of $1
- Each unit of B makes profit of $6
Demand <= 300 units of A
Supply <= 700 hours working
A takes 1 hr to make
B takes 3 hr to make
x1 = units of A per day
x2 = units of B per day
So the linear program is expressed as the following:
max x1 + 6x2
s.t.
- 0 <= x1 <= 300
- 0 <= x2 <= 200
- x1 + 3x2 <= 700
The complete standard way:
max x1 + 6x2
s.t.
- x1 <= 300
- x2 <= 200
- x1 >= 0
- x2 >= 0
- x1 + 3x2 <= 700
we use this to construct a feasible region plotting the lines on a 2D graph with x1 being one axis and x2 being the other
We find the optimal point in this shaded region
How do we find the optimum in a linear program?
We find the maximum values of x1, x2, etc. all variables that result in the max or min value (check objective function) and satisfies the formula. We plot the resulting formula line through the credible region of the linear program given the constraints. We find the highest point on this line within the constraint region.
- optimum must lie at a vertex of the polygon shaded region
What are key issues or topics to remember with linear programs?
- integer points vs non integer points determine the optimum point
- LP vs ILP determine whether its P or not
- optimum points lie on corners or vertices of the polygon
- feasible region is convex and no nasty shapes
Provide a 3D example of a linear program
You can now make 3 products
A $1
B $6
C $10
demand:
A <= 300
B <= 200
C unlimited
Supply
<= 1000 total
A takes 1 hr
B takes 3 hrs
C takes 2 hrs
packaging <= 500 total
A takes none
B takes 1
C takes 3
Linear program:
max x1 + 6x2 + 10x3
s.t.
x1 <= 300
x2 <= 200
x1 + 3x2 + 2x3 <= 1000
x2 + 3x3 <= 500
x1, x2, x3 >= 0
What is the standard form?
n variables
x1 … xn
max x1c1 + x2c2 + …xncn
s.t.
a11x11 … a1nx1n < b1
am1x1 …amnxn < bm
x1..xn >= 0 (non negative)
Essentially
max c^T x
s.t.
Ax <= b
x >= 0
What is the equivalence you should remember for converting to standard form?
min c^Tx <=> max -c^Tx
a1x1 + … + anxn >= b <=> -a1x1 - … - anxn <= - b
What is the geometric region or view?
n vars -> n dimensions
n + m constraints
feasible region = intersection of n + m halfspaces = convex polyhedron
vertices = points satisfying n constraints with =
and
points satisfying m constraints with <=
What are polynomial algorithms for solving linear programs in polynomial time?
Ellipsoid algorithms and interior point methods
Simplex algorithm
- worst-case exponential time
- widely used on huge LPs
What is the Simplex algorithm?
We start at x = 0
look for neighboring vertex with higher objective value -> then move there and repeat
else output current vertex
ex) start at point (0,0,0)
keep moving to higher vertex values that result in higher profit from previous example
Explain the following:
max C^Tx
s.t.
- Ax <= b
- x >= 0
n variables
m constraints
This is a linear program in standard form where there are n variables and m constraints
x values that form the feasible region that satisfies the constraints forms a convex set
-> forms a convex polyhedron in m dimensions
m half spaces
What are the exceptions to an optimum being located at the vertex of the feasible region?
A) infeasible = feasible region is empty
ex) max 5x - 7y
s.t.
x + y <= 1
3x + 2y >= 6
x, y >= 0
(you have feasible regions that don’t intersect each other)
THIS DEPENDS ON THE CONSTRAINTS
B) unbounded = optimal is arbitrarily large
ex) max x + y
s.t.
x - y <= 1
x + 5y >= 3
x, y >= 0
The graph for the above is bounded at the bottom, but there is no line bounding the top and thus values in the feasible region can go up forever: we unbounded feasible points of x+y = c
BOUNDEDNESS DEPENDS ON THE OBJECTIVE FUNCTION
How do we check if an LP is feasible?
max C^Tx
s.t.
- Ax <= b
- x >= 0
Look at the LP in standard form
Ask, are there any x’s that satisfy the constraints? Or is the feasible region empty or not?
Make a new variable z
and add to
a1x1 + …anxn <= b
x1…xn >= 0
Take same constraint and z ->
a1x1 + …anxn + z <= b
x1…xn >= 0
There is always a solution to the above equation when z is added with a small enough z
But is there a solution when z >= 0?
We add new objective function where we maximize z
If the objective function original is optimized when z is negative, then we know that the original LP is infeasible
If we can optimize with z values greater than 0, then we know the original LP is feasible
Given the following:
max x1 + 6x2 + 10x3
s.t.
- x1 <= 300
- x2 <= 200
- x1 + 3x2 + 2x3 <= 1000
- x2 + 3x3 <= 500
- x1, x2, x3 >= 0
How do we check if the following is the upper bound?
(200, 200, 100) = 2400
We have the following:
y = (y1, y2, y3, y4)
given point (0, 1/3, 1, 8/3)
we do the following
y1x1 + y2x2 + y3x3 + y4x4 <=>
x1y1 + x2y2 + x1y3 + 3x2y3 + 2x3y3 + x2y4 + 3x3y4 <= 300y1 + 200y2 + 1000y3 + 500y4
you see we multiply the terms (y1, y2, y3, y4) with each of the contraints on both sides of the constrains equation and combine all results into 1 equation above
We know any feasible point x satisfies this inequality
x1y1 + x2y2 + x1y3 + 3x2y3 + 2x3y3 + x2y4 + 3x3y4 <= 300y1 + 200y2 + 1000y3 + 500y4
for any non negative y
we simplify to the following:
x1(y1 + y3) + x2(y2 + 3y3 + y4) + x3(2y3 + 3y4)
<= 300y1 + 200y2 + 1000y3 + 500y4
we plug in the given point (0, 1/3, 1, 8/3)
and get:
x1 + 6x2 + 10x3 <= 2400
this is exactly the objective function of the original LP
Therefore we’ve proven the upper bound
Once proving the upper bound for the LP, how do we find the constraints for the input y values?
We need the left hand side of the equation to be atleast the objective function
ex)
x1(y1 + y3) + x2(y2 + 3y3 + y4) + x3(2y3 + 3y4)
<= 300y1 + 200y2 + 1000y3 + 500y4
x1 + 6x2 + 10x3 <= 2400
thus for y:
y1 + y3 >= 1,
y2 + 3y3 + y4 >= 6 ,
2y3 + 3y4 >= 10
then we want to minimize
Min 300y1 + 200y2 + 1000y3 + 500y4
Give the dual LP for the following:
max x1 + 6x2 + 10x3
s.t.
- x1 <= 300
- x2 <= 200
- x1 + 3x2 + 2x3 <= 1000
- x2 + 3x3 <= 500
- x1, x2, x3 >= 0
Which is the primal and which is the dual?
The given function is primal
min 300y1 + 200y2 + 1000y3 + 500y4
(take the right hand side of the constraints)
y1 + y3 >= 1,
y2 + 3y3 + y4 >= 6 ,
2y3 + 3y4 >= 10
y1,y2,y3 >= 0
(the coefficients of the original objetive function end up on the right hand side)
the above is the dual LP
What is the primal and dual LP general forms?
Primal in canonical form (all constraints are less than or equal to and objective function is maximization problem)
max C^Tx
Ax <= b
x >= 0
n variables
m constants
Dual:
min b^Ty
A^Ty >= c
y >= 0
m variables
n constraints
T of F - the dual of the dual should be equivalent to the original primal LP
True
What is the dual LP for the following primal LP?
max 5x1 - 7x2 + 2x3
s.t.
x1 + x2 - 4x3 <= 1
2x1 - x2 >= 3
x1, x2, x3 >= 0
convert 2x1 - x2 >= 3
to
-2x1 + x2 <= -3
thus
min y1 - 3y2
s.t.
y1 - 2y2 >= 5
y1 + y2 >= -7
-4y1 >= 2
y1, y2 >= 0
above is the dual
Summary:
the primal has 3 variables so dual will have 3 constraints
The primal has 2 constraints and thus dual will have 2 variables (y1,y2)
max becomes min in dual
What is the weak duality theorem? What is the corollary? What is the second corollary?
We take the feasible x for the primal LP
We also take the feasible y for the dual LP
c^Tx (primal LP function) <= b^Ty (dual LP function)
y gives an upper bound of the objective function of the primal LP
Corollary:
If we find a feasible x and feasible y where c^Tx = b^Ty
then x and y are optimal
2nd Corollary:
If the primal is unbouned, then the dual is infeasible (and vice versa)
if the dual is unbounded, then the primal is infeasible
How do we check for unboundedness?
We check if the primal LP is feasible by adding the z variable and check if solution exists when z is above 0
We know that if the primal is unbounded then the dual LP will be infeasible
If the dual LP is infeasible, we know the primal is ubounded or infeasible (don’t know which one)
Check if primal is unbounded in 2 steps:
1) Check if primal is feasible
2) Check if dual is infeasible
What is the strong duality theorem?
The primal is feasible and bounded IFF the dual is feasible and bounded
The primal has an optimal point x* IFF the dual has an optimal point y*
c^Tx* = b^Ty*
Relating to LP of max flow problem:
size of the maximal flow = size of the min S-T cut
What is the max sat problem? Is it in the class NP or NP hard or P? How do we solve it?
Input: CNF formula (m clauses, n literals) similar to SAT
Output: assignment maximizing # of satisfied clauses
Max SAT is NP hard
It’s not a search problem and thus not in the class NP
Thus also not in P
We aim to approximate the max sat problem using Linear Programming
What is the approx Max SAT algorithm?
For a formula with m clauses let m* denote the max # of sat clauses
Clearly m* <= m (formula is satisfiable)
Construct alg A on input f outputs l
where L >= m* / 2 where L is the # satisfied assignment outputted by A
1/2 - approximately algorithm (output is approximately within 1/2 of the assignments satisfied)
Overall pseudocode:
E[ # saturated clauses ]
= sum of E[wj] >= m/2
Randomized algorithm 1/2 - approximation in expectation
Deterministic algorithm by method of conditional exp
for i=1 to n
Try xi = T and xi = F
compute exp performacne for each - take the better
What is the simple scheme for the max sat problem?
consider input f CNF formula
Random assignment of probability 1/2 T or F for each clause -> set each clause with this probability assignment
W = # satisfied clauses
Expectation formula
E[W] = sum l =0 over m l * P(w = l)
What is the expectation formula for the simple schema for the max sat problem?
W = # satisfied clauses
for clause cj
let wj = {
1 if Cj is satisfied
0 otherwise
}
W = sum of all the wj’s
E[W] = sum over m (j=1) of E[Wj]
The chances that this input f is satisfied is 1 - (2 ^ -k)
What is the max exactly k SAT algorithm or EK-SAT? What happens when size = k?
ex) size = 3 or k = 3 and every clause has this size
Probability a particular clause cj is satisfied
- there is one setting of the 3 literals that appear in this clause where the clause is not satisfied is 1/8
Therefore there is a 7/8 chance it is satisfied and therefore for max E-3SAT we achieve a 7/8 approximation
If size is k, then
1 - 2^-k - approximation for max Ek-SAT
What does it imply if we achieve a when the approximation algorithm for max-E3-SAT is the best possible? What is the take away
P = NP
It’s NP-hard to do any better than this
If all the clauses are the same size and happen to be size 3, then we can achieve the best possible algorithm by just random assignment
Take away is that the hard cases is when the formula has varying size clauses
What is integer linear programming? Is it in NP?
ILP (integer linear programming)
max c^Tx
s.t.
Ax <= b
x >= 0
x in Z^n (where z are the integers or each xi is an integer)
ILP is NP-hard and does not lie in the class P or NP
How do we prove that ILP is NP-Hard?
Reduction from Max-SAT to ILP
Take f to the max SAT problem
Add yi to ILP for each xi in input f
Add zj to ILP for each cj in clause in f
constraints
0 <= yi <= 1
0 <= zj <= 1
zj corresponds to cj clause is satisfied or not
yi correspons xi being t or f
How are the clauses dealt with in ILP?
cj = (x5 v x3 v x6)
y5 = 0, y3 = 0, y6 = 0
We want zj = 0 if the clause is not satisfied
otherwise zj is 0 or 1
We enforce this behavior with the following constraint:
y5 + y3 + y6 >= zj
another example)
cj = (x1bar v x3 v x2 v x5bar )
if y1 = 1, y3 = 0, y2 = 0, y5 = 1 then zj = 0
(1 - y1) + y3 + y2 + (1 - y5) >= zj
What is the general reduction of Max-SAT to ILP?
for input f CNF
ILP: max sum of satisfied clauses zj
subjected to constraints:
0 <= yi <= 1 for i=1 to n
0 <= zj <= 1 for j=1 to m
yi and zj are integer values
sum of yi + sum of (1 - yi) is an upper bound on zj
This is how we reduce - in fact the above ILP is equivalent to the original max SAT problem
How does an LP solution relate to an ILP soluton? How does the rounding take place?
We take the LP solution and round the term assignments to come up with an approximate (but not optimal) ILP solution. This is done by rounding.
The integer solution is not far off from the LP solution (fractional solution) we came up with.
Rounding is done by the following steps:
we have the optimal points for the ILP problem yhat and zhat
we want yi and zj to be close to yhat and zhat (then it’s also close to ystar and zstar)
Set yi to be 1 or 0 with a probability proportional to yi hat star (for 1) and 1 - yi hat star (for 0)
We have randomized rounding now
What is the expectation of the solution for the ILP Max sat?
E[W] = sum over m of probability cj sat >= (1 - 1/e) sum of z hat star >= (1 - 1/e)m star
What is the lemma we need to prove in the reduction of max sat to ILP?
Lemma:
Look at cj
(x1 v x2 v …xk)
yi hat star … yk hat star >= z hat star j (constraint of LP)
Want to know
Pr( Cj is SAT) = 1 - Pr(Cj is unSAT)
Pr( Cj is unSAT) = Pi (over k) (1 - yi star hat)
What is the relationship between the arithmetic mean the geometric mean and how does this relate back to the ILP / max sat proof?
We have k nonnegative numbers
Arithmetic mean = sum of wi and divides by k
geometric mean = takes the product of sum of wi and then takes the kth root
AM >= GM (arithmetic mean always atleast the geometric mean)
Thus:
Pr (cj is SAT) = 1 - [ 1 - 1/k sum over i yi hat star ] ^ k
What is the Max SAT approximation take away?
Take an NP Hard problem
we can reduce to ILP
We can then relax to LP and solve
We can take the LP solution and round in some randomized way
How does Max SAT on EK SAT compare with different values of k?
k =1 simple => 1/2 ; LP-based = 1
k = 2 simple => 3/4; LP-based = 3/4
k = 3 simple => 7/8; LP-based = 1 - (2/3) ^ 3
k in general simple => 1 - 2^-k ; LP-based => 1 - (1 - 1/k)^k
Can we combine the simple and LP-based schemes in an algorithm?
Yes
Given f
- first run randomized algorithm and get assignment that satisfies m1
- then we run the LP based scheme that satisfies m2 clauses
- We then take the better of the 2
- expected performance -> E[max(m1, m2)] and this is atleast 3/4 of the optimal value (m*)
This combined algorithm gives a 3/4 approximation of max sat even with formulas having some clauses that are small and some that are big
