7.2 How to solve linear programs Flashcards
1
Q
How do linear program constraints form a shape
A
2
Q
What is the geometric meaning of the objective function? And why is a solution always in the corner?
A
- (n-1)-d hyperplane
- Corner will always have the maximum c value
3
Q
How does the simplex algorithm work
A
Keep moving up until reach (local and global) maximum vertex
4
Q
Simplex algorithm runtime
A
Typically linear but potentially exponential
5
Q
What is a vertex cover
A
6
Q
How to express finding a vertex cover as an integer linear program
A
Binary value for each vertex
Constraints are the edges >= 1
7
Q
How and why to relax integer linear programs
A
Allow non-binary values, then round. Approx solution
