A linear program is a type of Optimization problem where the objective and constraint functions are linear.
Definition of vertex
Given a point in the Polyhedron, it is a vertex if
- It solves the linear system defined by a full rank submatrix of the constraint matrix.
- It can't be written as Convex combination of two other points in the polyhedron.
/ / / / /
Linear programming, best way of solving discrete Optimization problem.. either exactly (when the solution can be found polynomially), or approximately, when NP-hard. There is a conjecture that is unproved, to show this. See Linear programming relaxation
Solution methods
- Simplex algorithm
- Ellipsoid method
- Interior-point method
Mosek
Applications
Duality
Finding the tightest upper bound using constraints! => Can be formulated as a linear program itself!
Max-flow min-cut theorem is an example of duality
Lagrangian duality. Reformulation of duality using Lagrangian multiplier
Integer linear programming (ILP)
Only integer solutions considered.
pdf slides ppt If the vertices are integers, the continuous optimization problem is equivalent to the ILP.
Otherwise, we can approximate with a continuous LP.
Totally unimodular matrix define integer polyhedra. http://mpawankumar.info/teaching/cdt-optimization/lecture4_2.pdf. Incidence matrix of digraphs are always TUM.
Linear model with absolute loss can be rewritten as a linear problem
Can rewrite inequality with absolute values as two inequalities without absolute values.