Integer Programming
Integer programming optimizes a linear objective over linear constraints where some or all variables must take whole-number values.
The formulation
An integer linear program (ILP) minimizes c^T x subject to A x <= b with the requirement that x be integer-valued. When variables are restricted to 0 or 1 it is a binary integer program, which naturally encodes yes-or-no decisions: whether to place a facility, select an item, or activate a route. The integrality requirement is what makes these problems combinatorially hard.
Why integrality is hard
Dropping integrality gives a linear program that is solved in polynomial time. Adding it makes the problem NP-hard in general: there is no known polynomial algorithm, and the feasible set becomes a lattice of points rather than a continuous polytope. Rounding an LP solution usually fails, because the rounded point may be infeasible or far from the true integer optimum.
Modeling power
Binary variables express rich logic through linear constraints. A big-M constraint links a continuous quantity to an on-off switch. Logical implications, either-or choices, and fixed setup charges all become linear inequalities. This expressiveness is why ILP models scheduling, routing, network design, unit commitment, and resource allocation across industry.
- Assignment and matching: who does what
- Knapsack and selection: pick a subset under a budget of capacity
- Set covering and partitioning: choose sets to cover all elements
- Sequencing and scheduling with precedence and setup logic
How solvers attack it
Modern solvers combine branch and bound with cutting planes (branch and cut), presolve simplification, and primal heuristics that find good feasible solutions early to enable pruning. The LP relaxation supplies the bound at each node. Formulation quality matters enormously: two mathematically equivalent models can differ by orders of magnitude in solve time depending on how tight their LP relaxations are.
For engineering programs, ILP is the standard tool when discrete choices dominate, such as selecting a configuration from a catalog of components or sequencing indivisible construction tasks under precedence.