Note
Given a set of variables, assign real values to each to:
- Satisfy a set of linear equations (Linearity) and/or inequalities over the variables
- Maximize or minimize a linear objective function
For example, we are given a list of constraints, values and a goal (optimize for some linear objective problem). You can usually plot the constrains which defines a feasible region. For lines with constant objective values (some equation of a line), the optimal solution for a given problem is the last point in the feasible region that line touches which always lies on a vertex of the feasible region. The only exceptions are when the problem is not well-defined.
- LP could be infeasible, it is not possible to satisfy all constraints (infeasible like in Input-Output Parameterization solving)
- LP could be unbounded (we can achieve arbitrarily large or small objective values)
Solving LPs
Simplex
- Start at a vertex arbitrarily
- Look for an adjacent vertex of better objective values
- Repeat until no better vertex exists This is optimal since the feasible region is convex!