Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

Grad Algorithms > Exam 3 part 2 > Flashcards

Exam 3 part 2 Flashcards

1
Q

What is linear programming?

A

General technique for solving optimization problems

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

What is the linear programming outline for max-flow problem?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Give an example of a linear program

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

How do we find the optimum in a linear program?

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What are key issues or topics to remember with linear programs?

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Provide a 3D example of a linear program

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

What is the standard form?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is the equivalence you should remember for converting to standard form?

A

min c^Tx <=> max -c^Tx

a1x1 + … + anxn >= b <=> -a1x1 - … - anxn <= - b

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is the geometric region or view?

A

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 <=

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What are polynomial algorithms for solving linear programs in polynomial time?

A

Ellipsoid algorithms and interior point methods

Simplex algorithm
- worst-case exponential time
- widely used on huge LPs

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the Simplex algorithm?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Explain the following:

max C^Tx
s.t.
- Ax <= b
- x >= 0

n variables
m constraints

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What are the exceptions to an optimum being located at the vertex of the feasible region?

A

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 well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

How do we check if an LP is feasible?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

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)

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

Once proving the upper bound for the LP, how do we find the constraints for the input y values?

A

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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
17
Q

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?

A

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

18
Q

What is the primal and dual LP general forms?

A

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

19
Q

T of F - the dual of the dual should be equivalent to the original primal LP

A

True

20
Q

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

A

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

21
Q

What is the weak duality theorem? What is the corollary? What is the second corollary?

A

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

22
Q

How do we check for unboundedness?

A

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

23
Q

What is the strong duality theorem?

A

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

24
Q

What is the max sat problem? Is it in the class NP or NP hard or P? How do we solve it?

A

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

25
Q

What is the approx Max SAT algorithm?

A

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

26
Q

What is the simple scheme for the max sat problem?

A

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)

27
Q

What is the expectation formula for the simple schema for the max sat problem?

A

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)

28
Q

What is the max exactly k SAT algorithm or EK-SAT? What happens when size = k?

A

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

29
Q

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

A

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

30
Q

What is integer linear programming? Is it in NP?

A

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

30
Q

How do we prove that ILP is NP-Hard?

A

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

31
Q

How are the clauses dealt with in ILP?

A

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

32
Q

What is the general reduction of Max-SAT to ILP?

A

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

33
Q

How does an LP solution relate to an ILP soluton? How does the rounding take place?

A

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

34
Q

What is the expectation of the solution for the ILP Max sat?

A

E[W] = sum over m of probability cj sat >= (1 - 1/e) sum of z hat star >= (1 - 1/e)m star

35
Q

What is the lemma we need to prove in the reduction of max sat to ILP?

A

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)

36
Q

What is the relationship between the arithmetic mean the geometric mean and how does this relate back to the ILP / max sat proof?

A

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

37
Q

What is the Max SAT approximation take away?

A

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

38
Q

How does Max SAT on EK SAT compare with different values of k?

A

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

39
Q

Can we combine the simple and LP-based schemes in an algorithm?

A

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

Grad Algorithms (6 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions