Integer Linear Programming (ILP)

Prime #

468

Origin domain

Operations Research

Also from

Mathematics, Computer Science & Software Engineering

Aliases

Ilp, Mip, Mixed Integer Programming, Integer Programming, Combinatorial Optimization via Ilp

Related primes

Linear Programming (LP), Branch and Bound, Dynamic Programming, Network Flow Models, Multiobjective Optimization, Sensitivity Analysis (in Operations Research), combinatorial optimization

Core Idea

Integer Linear Programming extends LP by requiring some or all decision variables to be integers—capturing discrete choices like how many warehouses to open or how many staff to hire—often making the problem NP-hard but more aligned with real-world "all-or-nothing" constraints.

How would you explain it like I'm…

Best Plan With Whole Pieces

Imagine you have to pack lunchboxes for a class. You can only pack whole apples — half an apple doesn't work. You want the most food for the lowest cost, but everything has to be a whole number. That's the kind of puzzle this solves: best choice, whole pieces only.

Best Plan, Whole Numbers Only

Integer linear programming is a math method for finding the best plan when your choices have to be whole numbers — like how many trucks to send, which warehouses to open, or which workers to assign. You write down what you want (like lowest cost), the limits (like only so many trucks available), and the rule that answers must be whole. A computer searches huge numbers of options for the best one that fits.

Whole-Number Optimization

Integer linear programming (ILP) is a math optimization method for picking the best plan when some choices must be whole numbers — open a warehouse or don't, send a truck or don't, assign a worker or don't. Like ordinary linear programming, you describe your goal and your limits as straight-line equations, but you also require certain variables to be integers, often 0-or-1. That extra rule captures real-world choices that can't be split (you can't open half a factory), and it makes the problem much harder. Special computer solvers use clever search to find optimal or near-optimal answers for huge real problems.

 

Integer linear programming (ILP) is the variant of linear programming in which some or all decision variables must take integer values, preserving LP's linear objective and linear constraints while adding integrality restrictions that capture discrete, indivisible, or yes/no real-world choices — open or close a facility, assign a task to a worker, route a vehicle over an edge. The integrality requirement transforms a polynomial-time-solvable problem (pure LP) into a generally NP-hard one (no known fast algorithm for all instances), but practical instances are routinely solved through specialized algorithms — branch-and-bound (systematic search over integer choices), cutting planes (tightening the continuous relaxation), and presolve heuristics — implemented in modern solvers like CPLEX, Gurobi, and SCIP. Mixed-integer linear programming (MILP), with some variables continuous and some integer, is the most common practical form, and is the workhorse of vehicle routing, scheduling, facility location, and supply-chain design.

Broad Use

• Facility Location: Select facility sites from candidate locations to minimize total cost while covering demand constraints.

• Scheduling & Staffing: Decide integer shift assignments or tasks without fractional people.

• Transportation Logistics: Dispatch an integer number of trucks or flights among routes.

• Healthcare Resource Allocation: Determine integer counts of hospital beds or staff in different departments.

Clarity

Realistic decision-making often demands discrete counts (e.g., 2 factories, not 2.4 factories), so ILP directly models indivisible resources or yes/no decisions.

Manages Complexity

Though NP-hard, ILP can be approached with advanced solvers (branch-and-bound, cutting planes) or heuristics, letting organizations handle problems that purely continuous LP solutions can't.

Abstract Reasoning

Shows how adding integrality drastically changes complexity—mirroring a widespread phenomenon where discrete constraints break linear solutions, yet reflect reality more faithfully.

Knowledge Transfer

• Software Project Selection: Which set of features or modules to implement given integer constraints on developer resources.

• Media & Advertising: Selecting integer placements of ads across channels for best coverage.

Example

A delivery company uses ILP to decide exactly how many distribution centers to open, each center's capacity, and which customers it should serve, achieving cost-effective operations with discrete facility decisions.

Relationships to Other Primes

Parents (3) — more general patterns this builds on

• Integer Linear Programming (ILP) is a kind of Constraint — Integer linear programming is a specific kind of constraint, binding decision variables to integer values within linear inequalities.
• Integer Linear Programming (ILP) is a kind of Optimization — Integer linear programming is a specialization of optimization that adds integrality restrictions to linear objectives and constraints.
• Integer Linear Programming (ILP) presupposes Discreteness — Integer linear programming presupposes discreteness because the integrality restriction on decision variables imposes the separated-states structure on the feasible set.

Path to root: Integer Linear Programming (ILP) → Constraint

Not to Be Confused With

• Integer Linear Programming (ILP) is not Linear Programming (LP) because ILP restricts variables to integer values (adding combinatorial structure), while LP allows continuous variables (purely convex optimization).
• Integer Linear Programming (ILP) is not Constraint Satisfaction because ILP optimizes a linear objective function subject to constraints, while constraint satisfaction seeks any assignment satisfying constraints without optimization.
• Integer Linear Programming (ILP) is not Knapsack Problem because ILP is a general framework applicable to any linear objective with integer constraints, while the knapsack problem is a specific problem instance constrained by capacity.