An integer programming, also known as integer optimization, problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming (ILP), in which the objective function and the constraints (other than the integer constraints) are linear. Integer programming is NP-complete (the difficult part is showing the NP membership). In particular, the special case of 0–1 integer linear programming, in which unknowns are binary, and only the restrictions must be satisfied, is one of Karp's 21 NP-complete problems. If some decision variables are not discrete, the problem is known as a mixed-integer programming problem.
Canonical and standard form for ILPs Integer linear programs can be expressed either in canonical form or standard form (both as defined below), which are different from each other. An integer linear program in canonical form is expressed thus (note that it is the x {\displaystyle \mathbf {x} } vector which is to be decided):
maximize x ∈ Z n c T x subject to A x ≤ b , x ≥ 0 {\displaystyle {\begin{aligned}&{\underset {\mathbf {x} \in \mathbb {Z} ^{n}}{\text{maximize}}}&&\mathbf {c} ^{\mathrm {T} }\mathbf {x} \\&{\text{subject to}}&&A\mathbf {x} \leq \mathbf {b} ,\\&&&\mathbf {x} \geq \mathbf {0} \end{aligned}}}
and an ILP in standard form is expressed as
maximize x ∈ Z n c T x subject to A x + s = b , s ≥ 0 , x ≥ 0 , {\displaystyle {\begin{aligned}&{\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} \geq \mathbf {0} ,\\&&&\mathbf {x} \geq \mathbf {0} ,\end{aligned}}}
where c ∈ R n , b ∈ R m {\displaystyle \mathbf {c} \in \mathbb {R} ^{n},\mathbf {b} \in \mathbb {R} ^{m}} are vectors and A ∈ R m × n {\displaystyle A\in \mathbb {R} ^{m\times n}} is a matrix. As with linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities, introducing slack variables ( s {\displaystyle \mathbf {s} } ) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables.
Example
The plot on the right shows the following problem.
… excerpt ends here. Continue reading the full article.
