Linear Programming#

Linear Programming (LP; same abbreviation for “Linear Program”) is a linear optimization technique which became widely known for resource planning tasks after World War II. As the name suggests, the objective function and (in-)equality constraint functions are linear.

The term “programming” should be understood as “planning” or “conception”, rather than the action of writing a program in a particular programming language.

In this work the following LP standard form is chosen:

\[\begin{split} \begin{array}{lll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax = b \\ & x \geq 0, \end{array} \end{split}\]

where \(c,x \in \mathbb{R}^{n}\), \(A \in \mathbb{R}^{m \times n}\), and \(b \in \mathbb{R}^{m}\).

Meeting other LP standard forms#

To compute an optimal LP solution, there exist many functions or programs, which are referred to in short as solver. An LP solver usually specifies an own standard form. In the following a few conversion techniques are described.

  • “minimize \(c^{T}x\)” is equivalent to “maximize \(-c^{T}x\)”. Flip the sign of the computed objective value.

  • Slack variables \(s \in \mathbb{R}^{m}\) help expressing inequality constraints as equality constraints:

    \[\begin{split} \begin{array}{ll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax {\color{red}{\;\leq\;}} b \\ & x \geq 0 \end{array} \quad\iff\quad \begin{array}{ll} \textrm{minimize} & c^{T} x {\color{red}{\;+\; [0]^{T} s}} \\ \textrm{subject to} & Ax {\color{red}{\;+\; Is =}}\; b \\ & x \geq 0 \\ & {\color{red}{s \geq 0}} \end{array} \end{split}\]

    or

    \[\begin{split} \begin{array}{ll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax {\color{red}{\;\geq\;}} b \\ & x \geq 0 \end{array} \quad\iff\quad \begin{array}{ll} \textrm{minimize} & c^{T} x {\color{red}{\;+\; [0]^{T} s}} \\ \textrm{subject to} & Ax {\color{red}{\;-\; Is =}}\; b \\ & x \geq 0 \\ & {\color{red}{s \geq 0}} \end{array} \end{split}\]

    where \(I\) is the \(m \times m\) unit matrix (main diagonal elements are \(1\), \(0\) otherwise) and \([0] \in \mathbb{R}^{m}\) is a vector of zeros.

  • Free variables \(y \in \mathbb{R}^{k}\) can be modeled as difference of two non-negative LP variables \(y := y^{+} - y^{-}\):

    \[\begin{split} \begin{array}{ll} \textrm{minimize} & c^{T} x {\color{red}{\;+\;d^{T} y}} \\ \textrm{subject to} & Ax {\color{red}{\;+\;By}} = b \\ & x \geq 0 \\ & {\color{red}{y \quad\text{"free"}}} \end{array} \quad\iff\quad \begin{array}{ll} \textrm{minimize} & c^{T} x {\color{red}{\;+\;d^{T} y^{+} \;-\; d^{T} y^{-}}} \\ \textrm{subject to} & Ax {\color{red}{\;+\;By^{+} \;-\; By^{-}}} = b \\ & x \geq 0 \\ & {\color{red}{y^{+} \geq 0}} \\ & {\color{red}{y^{-} \geq 0}} \end{array} \end{split}\]

    However, due to the introduced redundancy this approach might fail in practical applications and other techniques are known, see [LY16] (part I).

  • Expressing box constraints \(l,x,u \in \mathbb{R}^{n}\).

    \[\begin{split} \begin{array}{ll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax = b \\ & {\color{red}{l \;\leq\; x \;\leq\; u}} \end{array} \quad\iff\quad \begin{array}{ll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax = b \\ & {\color{red}{-Ix\;\leq\;-l}} \\ & {\color{red}{Ix\;\leq\;u}} \\ & {\color{red}{x \quad\text{"free"}}} \end{array} \end{split}\]

    where \(I\) is the \(n \times n\) unit matrix (main diagonal elements are \(1\), \(0\) otherwise). See also the note about “free variables” above.

  • Expressing equality constraints with inequality constraints.

    \[\begin{split} \begin{array}{ll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax {\color{red}{\;=\;}} b \\ & x \geq 0 \end{array} \quad\iff\quad \begin{array}{ll} \textrm{minimize} & c^{T} x \\ \textrm{subject to} & Ax {\color{red}{\;\leq\;}} b\; {\color{red}{(\;+\;\varepsilon)}} \\ & Ax {\color{red}{\;\geq\;}} b\; {\color{red}{(\;-\;\varepsilon)}} \\ & x \geq 0 \end{array} \end{split}\]

    The resulting problem is usually ill-posed and a small tolerance \(\varepsilon > 0\) can be added to each element of \(b\) for numerical stability.

For more information on LP and equivalent formulations, see [LY16] (part I) and [BV04] (chapter 4).