ILPs

Integer Linear Programs (ILPs) are mathematical optimization problems that seek to optimize a linear objective function subject to linear constraints, with the added requirement that the decision variables take integer values. In its most common form, an ILP minimizes c^T x subject to Ax ≤ b, with x in the integer lattice Z^n, where c is a vector of coefficients, A is a matrix of coefficients, and b is a vector of bounds. When some variables are restricted to integers and others may be continuous, the problem is called a mixed-integer linear program (MILP).

ILPs are NP-hard; the decision version of an ILP is NP-complete. Solving ILPs usually relies on algorithms such as branch-and-bound, branch-and-cut, and cutting planes, often implemented in MILP solvers. The linear programming relaxation, which ignores integrality constraints, provides lower or upper bounds and can be solved in polynomial time. In some cases, if the constraint matrix is totally unimodular and b is integral, the LP solution is already integral, yielding a polynomial-time solution.

Applications of ILPs are broad and include scheduling, production planning, facility location, transportation and logistics, knapsack-type selection, and network design. These problems are often combinatorial in nature and can be formulated as ILPs or MILPs, enabling exact optimization for reasonably sized instances despite their worst-case exponential complexity.

Relation to others: ILPs are a subset of integer programming, and MILPs extend them by allowing some variables to be continuous. Binary decision variables are common in modeling many ILP formulations.