LP (AI generated from transcript)

Question 1

What can Max Flow be modeled as?

Answer 1

Linear Programming (LP)

Max Flow models the flow of resources through a network while adhering to constraints.

Question 2

What is the objective function for Max Flow in LP?

Answer 2

Maximize sum of flow for all edges in E

Question 3

What are the constraints for Max Flow in LP?

Answer 3

• Must have non-negative flow
• For every vertex, flow in must equal flow out

Question 4

In a 2D LP example, what is the objective function?

Answer 4

A + 6B

Question 5

What are the constraints in the 2D LP example?

Answer 5

• A <= 300
• B <= 200
• A + 3B <= 700
• A, B >= 0

Question 6

What does the orange area represent in the 2D LP geometric view?

Answer 6

The feasible region

Question 7

What is the optimal point in the 2D LP example?

Answer 7

x1=100 and x2=200 with profit = 1300

Question 8

Is Linear Programming in P or NP?

Answer 8

Linear Programming is in P

Question 9

What is Integer Linear Programming (ILP)?

Answer 9

NP-Complete

Question 10

What characterizes the optimal point in LP?

Answer 10

Lies at a vertex of the feasible region

Question 11

How many vertices are in the given 2D LP example?

Answer 11

5 vertices: {(0,0), (0, 200), (100,200), (300,0), (300, ~120)}

Question 12

True or False: A feasible region is convex.

Answer 12

True

Question 13

What happens to the feasible region defined by the intersection of half spaces?

Answer 13

It must be a convex set

Question 14

In the standard form of LP, what does the objective function maximize?

Answer 14

A linear function of n variables

Question 15

What are the coefficients in the standard form of LP?

Answer 15

c1, c2, …, cn

Question 16

What constraints are included in the standard form of LP?

Answer 16

• m constraints
• Non-negativity constraints

Question 17

What is the significance of non-negative constraints in LP?

Answer 17

Used to find a trivially feasible point or to determine if the LP is infeasible

Question 18

What is the first step in converting a linear program to standard form?

Answer 18

To minimize a linear function, multiply the objective function by -1

Question 19

How do you handle equality constraints when converting to standard form?

Answer 19

Replace with 2 inequality constraints

Question 20

What is the geometric view of LP with n variables?

Answer 20

Corresponds to points satisfying all n+m constraints

Question 21

What does the Simplex algorithm do?

Answer 21

Solves linear programs in polynomial time

Question 22

What is the starting point for the Simplex algorithm?

Answer 22

Feasible point, typically the zero vector

Question 23

What happens if no higher-value neighbors are found in Simplex?

Answer 23

The current vertex is optimal

Question 24

What is an example of infeasibility in LP?

Answer 24

Non-intersecting half spaces yield an empty feasible region

Question 25

What is the result of an unbounded LP?

Answer 25

Infinite optimal value of the objective function

Question 26

What is the method to detect infeasibility?

Answer 26

Add a single new variable z that is unrestricted

Question 27

What is the dual LP?

Answer 27

A minimization problem derived from the original maximization LP

Question 28

What do the coefficients from the original LP constraints define in the dual LP?

Answer 28

The objective function of the dual LP

Question 29

What is the relationship between the number of variables in the primal LP and the dual LP?

Answer 29

Orig: # Vars → Dual: # Constraints

Question 30

What is the relationship between the number of constraints in the primal LP and the dual LP?

Answer 30

Orig: # Constraints → Dual: # Vars

Question 31

What is the general objective of the primal LP?

Answer 31

Maximize a profit function represented by obj. func. max(cTx) under constraints Ax≤b, x≥0

Question 32

What does the Dual LP aim to do?

Answer 32

Minimize profit, finding smallest upper bound by obj. func. minbTy

Question 33

What constraints are derived from the primal LP's objective function?

Answer 33

ATy≥c, y≥0

Question 34

What is the relationship between the number of variables and constraints in the primal and dual LPs?

Answer 34

Orig: # Vars → Dual: # Constraints; Orig: # Constraints → Dual: # Vars

Question 35

What is required for the Dual LP formulation?

Answer 35

The primal LP must be in canonical form with 'at most' inequalities and maximization objective

Question 36

True or False: The Dual LP of a Dual LP is the original Primal LP.

Answer 36

True

Question 37

How many variables are in the Dual LP if the primal has 2 constraints?

Answer 37

2

Question 38

How many constraints are in the Dual LP if the primal has 3 variables (excluding non-negative constraints)?

Answer 38

3

Question 39

Fill in the blank: The values of d are _______.

Answer 39

[1, -3]

Question 40

What does the Weak Duality theorem state?

Answer 40

For any feasible solution x to the primal and y to the dual, cTx≤bTy

Question 41

What is the implication of matching objective function values in primal and dual LPs?

Answer 41

Both are optimal (x = optimal max, y = optimal min)

Question 42

What does the Strong Duality theorem guarantee?

Answer 42

The existence of optimal primal-dual pairs if both LPs are feasible and bounded

Question 43

What happens if the primal LP is unbounded?

Answer 43

The dual LP is infeasible

Question 44

What is the first step to check if a primal LP in canonical form is unbounded?

Answer 44

Check feasibility by adding new z variable Ax+z≤b, x≥0

Question 45

What must be checked for the dual LP to determine primal unboundedness?

Answer 45

If the dual is infeasible

Question 46

What is the key idea behind Strong Duality?

Answer 46

A feasible and bounded primal LP has an equivalent dual LP that is also feasible and bounded

Question 47

What is the max flow min cut theorem in relation to LPs?

Answer 47

Max flow = primal LP; min cut = dual LP

Question 48

Fill in the blank: The constraints in the primal LP must be transformed into _______.

Answer 48

Canonical form