# Linear program

An optimization problem in which the objective and constraints are linear. Forms include $LaTeX: \min \{c^Tx: Ax = b,\, x >= 0\}$ and $LaTeX: \max \{c^Tx : Ax \le b\}$. The standard form assumes $LaTeX: A$ has full row rank. Computer systems ensure this by having a logical variable $LaTeX: (y)$ augmented, so the form appears, for example, as $LaTeX: \min \{c^Tx: Ax + y = b,\, L \le (x, y) \le U\}$ (also allowing general bounds on the variables). The original variables $LaTeX: (x)$ are called structural. Note that each logical variable can be a slack, surplus, or artificial variable, depending on the form of the original constraint. This computer form also represents a range constraint with simple bounds on the logical variable. Some bounds can be infinite (i.e., absent), and a free variable (logical or structural) is when both of its bounds are infinite.