Editing Integer programming (section)

==Canonical and standard form for ILPs==

In integer linear programming, the ''canonical form'' is distinct from the ''standard form''. An integer linear program in canonical form is expressed thus (note that it is the <math>\mathbf{x}</math> vector which is to be decided):<ref name="optBook">{{cite book|last1=Papadimitriou|first1=C. H.|author1-link=Christos Papadimitriou|last2=Steiglitz|first2= K.|author2-link=Kenneth Steiglitz|title=Combinatorial optimization: algorithms and complexity|year=1998|publisher=Dover|location=Mineola, NY|isbn=0486402584}}</ref>

:<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>

and an ILP in standard form is expressed as

:<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.