Integer Programming (ILP)
Optimize when your decisions must be whole numbers, how many facilities to open, which projects to fund, whether to build or not. Integer programming extends linear programming with integrality, handling yes/no and count decisions that fractional solutions cannot.
Solve Integer Program →What is Integer Programming?
Integer programming (IP), or integer linear programming, is an optimization method like linear programming, but with the added requirement that some or all decision variables must take integer (whole-number) values. This handles the many real decisions that are inherently discrete: numbers of vehicles, facilities, or workers, and yes/no choices.
When variables are restricted to 0 or 1, the model is a binary integer program, used for decisions such as whether to build a facility, select a project, or assign a task. When only some variables are integer and others continuous, it is a mixed-integer program (MIP), the most common form in practice.
Integer programming is considerably harder to solve than linear programming, because the feasible integer points do not form a smooth region and the corner-point shortcut of LP no longer applies. Solvers use methods such as branch-and-bound, which systematically explores and prunes the space of integer possibilities, so problems can grow computationally expensive as they scale.
In plain terms: Linear programming can tell you to open 2.7 factories, which is nonsense. Integer programming forces whole-number answers, and handles yes/no decisions (build it or not, pick this project or not). That realism comes at a cost: these problems are much harder for computers to crack than ordinary LP.
Key Variants
Pure Integer
All decision variables must be whole numbers, such as counts of items, machines or trips.
Binary (0/1)
Variables take only 0 or 1, modeling yes/no decisions: build or not, select or not, assign or not.
Mixed-Integer (MIP)
Some variables are integer and others continuous, the most common and flexible form in practice.
Key Formulas
Understanding the Solution
The solver returns integer-valued decisions and the optimal objective. Because integer programs are solved by systematically exploring possibilities, the solver also tracks a bound on how far the current best solution could be from the true optimum, useful when a problem is too large to solve exactly in reasonable time.
Do not obtain integer answers by simply rounding a linear programming solution. Rounding can produce an infeasible solution (violating constraints) or a feasible but suboptimal one; the correct integer optimum often differs from the rounded LP result in non-obvious ways.
Assumptions & Validation
Linear Objective & Constraints
The objective and constraints are linear, as in LP.
If violated: For nonlinear relationships, use nonlinear integer methods.
Integrality Required
Some or all variables genuinely must be whole numbers.
If violated: If fractional values are acceptable, plain LP is faster.
Tractable Size
The problem is small enough to solve in acceptable time.
If violated: For very large problems, use heuristics or accept a bounded gap.
⚠️ Check assumptions first
The temptation to solve an integer problem by rounding a linear programming answer is a common and serious mistake: rounding can violate constraints or land far from the true integer optimum. Use a genuine integer programming method instead. Be aware, too, that integer programs are computationally hard, so large models may not solve exactly in reasonable time, and a solution within a small optimality gap may be the practical goal.
When NOT to Use Integer Programming
Fractional Values OK
If decisions can be fractional, linear programming solves faster and exactly.
Conflicting Goals
To balance multiple competing objectives, use goal programming.
Nonlinear Structure
When relationships are nonlinear, standard integer linear programming does not apply.
Industry Applications
Facility Location
Decide which facilities to open (binary) to minimize cost while meeting demand.
Project Selection
Choose which projects to fund under a budget, a classic 0/1 knapsack-style problem.
Scheduling & Assignment
Assign shifts, crews or tasks where decisions are discrete.
Capital Budgeting
Select an optimal portfolio of indivisible investments under constraints.
Frequently Asked Questions
What is integer programming?
Integer programming is an optimization method that, like linear programming, maximizes or minimizes a linear objective subject to linear constraints, but additionally requires some or all decision variables to take whole-number values. This handles inherently discrete decisions such as counts of items or facilities and yes/no choices, which fractional solutions cannot represent meaningfully.
What is the difference between integer and linear programming?
Linear programming permits variables to take any fractional value, while integer programming requires some or all to be whole numbers. This makes integer programming suitable for discrete decisions but also much harder to solve, because the efficient corner-point methods of linear programming no longer apply directly. Integer solvers use approaches such as branch-and-bound to search the integer possibilities systematically.
What is a binary integer program?
A binary integer program restricts variables to the values 0 or 1, which model yes/no decisions such as whether to build a facility, select a project, or make an assignment. Binary variables are extremely versatile for representing logical choices and either-or conditions, and many classic optimization problems, including facility location and project selection, are formulated as binary integer programs.
Why can't I just round a linear programming solution?
Rounding a fractional linear programming solution to the nearest integers can produce a solution that violates the constraints, making it infeasible, or that is feasible but far from the true integer optimum. The optimal integer solution often lies at a different combination of values than the rounded result. This is precisely why dedicated integer programming methods are needed rather than rounding.
What is a mixed-integer program?
A mixed-integer program, or MIP, is one in which some decision variables must be integer while others may be continuous. It is the most common form in practice, because many real models combine discrete decisions, such as whether to open a facility, with continuous ones, such as how much to ship. MIP solvers handle both variable types within a single optimization.
Why is integer programming harder than linear programming?
In linear programming the optimum lies at a corner of a smooth feasible region, which efficient algorithms exploit. Integer programming restricts solutions to discrete points, so that shortcut disappears and the solver must search among many integer combinations. This search, typically via branch-and-bound, can grow expensive as the problem scales, making large integer programs computationally demanding to solve to proven optimality.
Optimize Whole-Number and Yes/No Decisions
Solve integer and mixed-integer programs correctly, without rounding. Free during Beta.
Solve Integer Program →