Exam 3 - Linear Programming

Question 1

The optimal solution to an LP always lies at a ____ of the feasible region

Answer 1

vertex

Question 2

Solving LP programs is ____ runtime

Answer 2

polynomial

Question 3

Solving LP programs is ____ difficulty

Answer 3

P

Question 4

True/False : Integer LP (ILP) is NP-complete

Answer 4

True

Question 5

True/False : The feasible region is always convex

Answer 5

True

Question 6

Vertices of the feasible region are points that satisfy n constraints with _

Answer 6

=

Question 7

Vertices of the feasible region are points that satisfy m constraints with

Answer 7

<=

Question 8

The feasible region has at most ____ vertices

Answer 8

n + m choose n

Question 9

The vertices of the feasible region have at most ____ neighbors

Answer 9

n * m

Question 10

What is the feasible region?

Answer 10

Possible variable values that satisfy the constraints

Question 11

If the feasible region is empty and an optimum cannot be found, the LP is ____

Answer 11

infeasible

Question 12

If the optimal is arbitrarily large, the LP is ____

Answer 12

unbounded

Question 13

True / False : Whether an LP is feasible depends on the constraints and the objective function

Answer 13

False, feasibility only depends on the constraints

Question 14

How do you determine the feasibility of an LP?

Answer 14

First check if any constraints are conflicting (e.g. if a constraint specifies that a single variable must be negative, but all of the variables have positivity constraints)

Then check if any of the intersection points are valid for the system of inequalities.

Question 15

How do you determine if an LP is bounded?

Answer 15

Check the feasibility of the LP and its dual.

If the dual LP is infeasible, then the primal is either unbounded or infeasible.

Question 16

Can an LP be unbounded and infeasible?

Answer 16

No, if there is no valid optimum then it cannot be arbitrarily large

Question 17

What’s the standard form of a linear program?

Answer 17

Question 18

What’s the linear algebra view of a linear program?

Answer 18

Question 19

What are the polytime algorithms for solving linear programs?

Answer 19

Ellipsoid and Interior point

Question 20

What’s the popular algorithm for solving linear programs?

Answer 20

Simplex

Question 21

How does the Simplex algorithm solve linear programs?

Answer 21

• Start at x = 0
• Look for neighboring vertex w/ higher objective value
• Move there and repeat until no better neighbor found

Question 22

How do you convert a primal LP to its dual?

Answer 22

Question 23

If an LP has n variables and m constraints, how many variables and constraints will its dual have?

Answer 23

m variables
n constraints

Question 24

When converting a standard form primal LP to its dual, the objective function goes from a ___ to a ___

Answer 24

max to a min

Question 25

When converting a standard form primal LP to its dual, the 2D matrix of parameters on the left side of the constraints gets ____

Answer 25

transposed

Question 26

When converting a standard form primal LP to its dual, the parameters to the variables in the objective function get ____ and swapped with the ____

Answer 26

transposed and swapped with the parameters on the right side of the constraints

Question 27

When converting a standard form primal LP to its dual, the parameters on the right side of the constraints get ____ and swapped with the ____

Answer 27

transposed and swapped with the parameters to the variables in the objective function

Question 28

When converting a standard form primal LP to its dual, the inequality symbol in the constraints goes from __ to __

Answer 28

<= to >=

Question 29

True/False : When converting a standard form primal LP to its dual, the nonnegative constraint on the variables is flipped

Answer 29

No, the new variables still have a nonnegative constraint

Question 30

If I have an LP with a variable with no nonnegative constraint, how do I convert it to one with a nonnegative constraint so it is in standard form?

Answer 30

Split the possibly negative variable x into two variables x_+ and x_-, and replace it with x_+ - x_-