Linear Programming

Question 1

What is the main method of solving linear programs?

Answer 1

The simplex algorithm. Begin at a random vertex, repeatedly look for an adjacent vertex connected by an edge of the feasible region of better value. A local optimum is guaranteed to be the global optimum.

Question 2

What runtime is solving an ILP?

Answer 2

NP-Hard

Question 3

What runtime is solving an LP?

Answer 3

Polynomial

Question 4

What are the cases where you can’t solve a linear program?

Answer 4

1. Infeasible. Constraints can’t be simultaneously satisfied.
2. Unbounded. You can shoot endlessly for a higher number to maximize the objective.

Question 5

What is the mathematical form of an LP (Primal)?

Answer 5

n variables, m constraints
max c^T x
Ax <= b
x >= 0

Question 6

What’s the difference between LP and ILP?

Answer 6

Aside from runtime, ILPs are constrained by x must be integers.

Question 7

How do solutions to LP and ILP relate?

Answer 7

ILP solutions are always a subset of LP solutions, but are not guaranteed to be optimal LP solutions.

Question 8

How do you solve an ILP (approximation)?

Answer 8

1. Take a problem and convert it into an ILP
2. Remove the integer constraints of ILP to get an LP problem
3. Solve the LP problem as you would normally using Simplex
4. Take the optimal solution for the LP, and convert it to a feasible point for the ILP

Question 9

Given a primal LP, how do you write the dual LP?

Answer 9

1. Convert the Primal to Standard Form
2. Dual LP is minimize
3. Move terms around
   a. Gather RHS of Primal as Dual minimization terms
   b. Gather Primal x1 and put them as coefficients on the first row of Dual constraints, x2 as coefficients on the second row, etc.
   c. Gather coefficients of Primal maximization as Dual RHS

Question 10

What is the mathematical form of the Dual LP?

Answer 10

m variables, n constraints
min b^T y
A^T y >= c
y >= 0

Question 11

How do you check if an LP has a solution?

Answer 11

Validate that it’s feasible and bounded by checking that the Primal and Dual LPs are feasible.

• If the Primal LP is not feasible, then there is no feasible solution.
• If the Dual LP is not feasible, then the problem is unbounded.

Question 12

How do you check if an LP is feasible?

Answer 12

Add a new variable z and maximize it to see if it is positive.

max z
Ax + z <= b
x >= 0

If z >= 0, the LP is feasible. If z < 0, infeasible.

Question 13

What is the weak duality theorem?

Answer 13

Feasible x for Primal LP <= Feasible y for Dual LP

c^T x <= b^T y

Question 14

What is the strong duality theorem?

Answer 14

Primal LP is feasible and bounded iff Dual LP is feasible and bounded

Primal LP has an optimal x iff Dual LP has an optimal y

Question 15

If the Primal LP is unbounded, what does that tell you about the Dual LP?

Answer 15

Infeasible

Question 16

If the Dual LP is unbounded, what does that tell you about the Primal LP?

Answer 16

Infeasible

Question 17

If the Primal LP is infeasible, what does that tell you about the Dual LP?

Answer 17

Irrelevant because the problem can’t be solved

Question 18

If the Primal LP is feasible, what does that tell you about the Dual LP?

Answer 18

Nothing/bounded

Question 19

If the Primal LP is feasible, what does that tell you about its boundedness?

Answer 19

Nothing without evaluating the Dual LP

Question 20

If the Primal LP is feasible and the Dual LP is infeasible, what does that tell you about the Primal LP?

Answer 20

Unbounded

Question 21

How do you write the Linear Program for a problem?

Answer 21

1. Determine the variables
2. Determine objective function (min/max)
3. Determine constraints (supply, demand), usually non-negative
4. Write in Standard Form

Question 22

How do you write a Linear Program in Standard Form?

Answer 22

1. Convert objective function to maximize (negative it if it’s a min)
2. Convert equalities to two inequalities
3. Change constraints to form LHS <= RHS by negating them
4. Constrain all variables to >= 0