An optimization method that selects integer-valued decision variables to maximize or minimize a linear objective function subject to a finite set of linear equality and inequality constraints.

Principle

When decision variables are constrained to integers, feasible solutions are a discrete subset of the linear-relaxation polyhedron; optimal integer solutions can be found by exploring that discrete set using combinatorial branching, cutting, or enumeration guided by linear bounds.

Demonstration

Situation: A factory schedules whole machines (0 or 1) to produce two products under capacity and demand constraints. Recognition: Variables represent counts of machines assigned to each product and must be integers. Action: Formulate objective as linear profit, constraints linear capacities, and solve via branch-and-bound on the LP relaxation. Consequence: The solver returns an integer assignment that maximizes total profit while respecting capacity and demand.

Misapplication

Treating ILP as equivalent to solving the continuous linear program and rounding the continuous optimum to integers. The semantic error is assuming rounded solutions satisfy integer feasibility and optimality conditions; rounding can violate constraints and produce suboptimal or infeasible solutions.

Consequence

Correct application produces implementable, integer-feasible plans (e.g., machine counts, vehicle routes) and valid optimality bounds; incorrect application (naive rounding) can result in infeasible schedules, violated constraints, unexpected costs, or overestimation of achievable objective value.

Reversal

If all variables that must be integer appear in the formulation only multiplicatively by other integer decision variables (nonlinear interaction) or if integer integrality is relaxed by allowing fractional but interpretively meaningful decisions (e.g., expected fractional allocations in stochastic programming), the standard ILP assumptions and solution methods no longer apply and require mixed-integer nonlinear or stochastic formulations.

Boundary

Clearly within: A facility location problem with binary open/close variables and linear capacity constraints. Boundary case: Variables representing numbers of identical items that could be large — integer integrality matters but LP relaxation provides close bounds; specialized cutting planes may be required. Clearly outside: A nonlinear integer optimization where objective or constraints are nonlinear (not ILP).

Semantic Tension

Optimality ↔ Tractability — enforcing integer constraints yields exact implementable solutions but can make problems NP-hard and computationally costly compared with tractable continuous relaxations.

Synthesis

ILP distinguishes implementability (discrete, integer decisions) from the convex, continuous optimization world; effective use balances exact discrete feasibility with computational strategies that exploit LP bounds, branching, and cutting to manage combinatorial complexity.