Integer Linear Optimization Program

References

(Wikipedia, 2014) ⇒ http://en.wikipedia.org/wiki/integer_programming#Canonical_and_standard_form_for_ILPs Retrieved:2014-9-26.
- An integer linear program in canonical form is expressed as: :[math]\displaystyle{ \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} \le \mathbf{b}, \\ & && \mathbf{x} \ge \mathbf{0}, \\ & \text{and} && \mathbf{x} \in \mathbb{Z}, \end{align} }[/math], and an ILP in standard form is expressed as :[math]\displaystyle{ \begin{align} & \text{maximize} && \mathbf{c}^\mathrm{T} \mathbf{x}\\ & \text{subject to} && A \mathbf{x} + \mathbf{s} = \mathbf{b}, \\ & && \mathbf{x} \ge \mathbf{0}, \\ & \text{and} && \mathbf{x} \in \mathbb{Z}, \end{align} }[/math] where the entries of [math]\displaystyle{ \mathbf{c}, \mathbf{b} }[/math] are vectors and [math]\displaystyle{ A }[/math] is a matrix, having integer values. Note that similar to linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities by introducing slack variables ([math]\displaystyle{ \mathbf{s} }[/math]) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables

http://en.wikipedia.org/wiki/Integer_programming
- An integer programming 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, which is also known as mixed integer programming when some but not all the variables are restricted to be integers.
  Integer programming is NP-hard. A special case, 0-1 integer linear programming, in which unknowns are binary, is one of Karp's 21 NP-complete problems. However, integer programs with a constant number of variables may be solved in linear time as an LP-type problem