Integer linear 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 (ILP), in which the objective function and the constraints (other than the integer constraints) are linear.

Integer programming is NP-hard. A special case, 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.

An integer linear program in canonical form is expressed as:

and an ILP in standard form is expressed as

where ${\displaystyle \mathbf {c} ,\mathbf {b} }$ are vectors and ${\displaystyle A}$ is a matrix, where all entries are integers. Note that similar to linear programs, ILPs not in standard form can be converted to standard form by eliminating inequalities by introducing slack variables (${\displaystyle \mathbf {s} }$) and replacing variables that are not sign-constrained with the difference of two sign-constrained variables

...
Wikipedia