Linear Programming

Definition

Linear Programming

Linear programming is the optimisation problem of maximising a linear objective over real-valued solutions to a system of linear inequalities. Given rational input data

$$A\in {\mathbb{Q}}^{m\times n},b\in {\mathbb{Q}}^m,c\in {\mathbb{Q}}^n,$$

its feasible solutions and objective are

$$F=\{x\in {\mathbb{R}}^n:Ax\le b\},\underset{x\in F}{\max }{c}^{\top }x.$$

Unlike integer linear programming, the decision vector $x$ need not be integral. Linear programming is solvable in polynomial time.

Decision Version $t\in \mathbb{Q}$, the decision version asks

Given a target

$$\exists x\in {\mathbb{R}}^n:Ax\le b\wedge c^{\top }x\ge t.$$