Integer Linear Optimization Program

From GM-RKB
(Redirected from Integer Linear Program)
Jump to navigation Jump to search

An Integer Linear Optimization Program is a linear optimization program that is an integer optimization program (where some or all of the Unknown Variables are Integer Variables).



References

2014

  • (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


2012