Integer Programming

Definition

Integer Programming

In the broad sense used here, integer programming is the optimisation problem of maximising a possibly non-linear function over integer assignments satisfying possibly non-linear constraints. Given functions

$$f,g_1,\dots ,g_m:{\mathbb{Z}}^n\to \mathbb{Z},$$

its feasible solutions and objective are

$$F=\{x\in {\mathbb{Z}}^n:\forall i\in \{1,\dots ,m\},g_i(x)\le 0\},\underset{x\in F}{\max }f(x).$$

Products such as $x_i{x}_j$ and higher-degree polynomial terms are permitted. Restricting every $g_i$ and $f$ to be linear yields integer linear programming.

Decision Version $t\in \mathbb{Z}$, the decision version asks

Given a target

$$\exists x\in {\mathbb{Z}}^n:\underset{i=1}{\overset{m}{\bigwedge }}(g_i(x)\le 0)\wedge f(x)\ge t.$$

Allowing polynomial equations over integer variables already makes general feasibility an undecidable decision problem.