Exam 3 - Linear Programming Flashcards
The optimal solution to an LP always lies at a ____ of the feasible region
vertex
Solving LP programs is ____ runtime
polynomial
Solving LP programs is ____ difficulty
P
True/False : Integer LP (ILP) is NP-complete
True
True/False : The feasible region is always convex
True
Vertices of the feasible region are points that satisfy n constraints with _
=
Vertices of the feasible region are points that satisfy m constraints with
<=
The feasible region has at most ____ vertices
n + m choose n
The vertices of the feasible region have at most ____ neighbors
n * m
What is the feasible region?
Possible variable values that satisfy the constraints
If the feasible region is empty and an optimum cannot be found, the LP is ____
infeasible
If the optimal is arbitrarily large, the LP is ____
unbounded
True / False : Whether an LP is feasible depends on the constraints and the objective function
False, feasibility only depends on the constraints
How do you determine the feasibility of an LP?
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.
How do you determine if an LP is bounded?
Check the feasibility of the LP and its dual.
If the dual LP is infeasible, then the primal is either unbounded or infeasible.
Can an LP be unbounded and infeasible?
No, if there is no valid optimum then it cannot be arbitrarily large
What’s the standard form of a linear program?
What’s the linear algebra view of a linear program?
What are the polytime algorithms for solving linear programs?
Ellipsoid and Interior point
What’s the popular algorithm for solving linear programs?
Simplex
How does the Simplex algorithm solve linear programs?
- Start at x = 0
- Look for neighboring vertex w/ higher objective value
- Move there and repeat until no better neighbor found
How do you convert a primal LP to its dual?
If an LP has n variables and m constraints, how many variables and constraints will its dual have?
m variables
n constraints
When converting a standard form primal LP to its dual, the objective function goes from a ___ to a ___
max to a min
When converting a standard form primal LP to its dual, the 2D matrix of parameters on the left side of the constraints gets ____
transposed
When converting a standard form primal LP to its dual, the parameters to the variables in the objective function get ____ and swapped with the ____
transposed and swapped with the parameters on the right side of the constraints
When converting a standard form primal LP to its dual, the parameters on the right side of the constraints get ____ and swapped with the ____
transposed and swapped with the parameters to the variables in the objective function
When converting a standard form primal LP to its dual, the inequality symbol in the constraints goes from __ to __
<= to >=
True/False : When converting a standard form primal LP to its dual, the nonnegative constraint on the variables is flipped
No, the new variables still have a nonnegative constraint
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?
Split the possibly negative variable x into two variables x_+ and x_-, and replace it with x_+ - x_-
