Content deleted Content added
No edit summary |
m →Canonical and standard form for ILPs: Improve formatting of optimization problems |
||
Line 11:
:<math> \begin{align}
& \underset{\mathbf{x} \in \mathbb{Z}^n}{\text{maximize}} && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} \le \mathbf{b}, \\
& && \mathbf{x} \ge \mathbf{0}
\end{align} </math>
Line 20 ⟶ 19:
:<math> \begin{align}
& \underset{\mathbf{x} \in \mathbb{Z}^n}{\text{maximize}} && \mathbf{c}^\mathrm{T} \mathbf{x}\\
& \text{subject to} && A \mathbf{x} + \mathbf{s} = \mathbf{b}, \\
& && \mathbf{s} \ge \mathbf{0}, \\
& && \mathbf{x} \ge \mathbf{0},
\end{align} </math>
where <math>\mathbf{c}\in \mathbb{R}^n, \mathbf{b} \in \mathbb{R}^m</math> are vectors and <math>A \in \mathbb{R}^{m \times n}</math> is a matrix. As with linear programs, ILPs not in standard form can be [[simplex algorithm#Standard form|converted to standard form]] by eliminating inequalities, introducing slack variables (<math>\mathbf{s}</math>) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.
| |||