Integer Programming — IP and Mixed-Integer Programming (MIP)
Integer Programming (IP / Mixed-Integer Programming) · Also known as: IP, MIP, mixed-integer programming, mixed-integer linear programming, MILP, Tam Sayılı Programlama (IP / MIP)
Integer programming (IP), also called mixed-integer programming (MIP) when only some variables are restricted to whole numbers, is a branch of mathematical optimisation in which some or all decision variables must take integer or binary values. Building on linear programming, it was formalised through Ralph Gomory's cutting-plane method (1958) and the Land-and-Doig branch-and-bound algorithm (1960), and it has since become the standard exact framework for scheduling, assignment, routing, and resource-allocation problems.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
+1 more
When to use it
Use integer programming when decisions are inherently discrete — binary yes/no choices, integer quantities, or logical on/off constraints — and when you need an exact or near-exact optimal solution with a provable quality bound. It suits scheduling, crew and resource assignment, vehicle routing, facility location, capital budgeting, and portfolio selection. There is no minimum sample-size requirement because IP is a deterministic optimisation framework rather than a statistical inference procedure. Variable types can be binary, categorical (encoded as binary), or continuous (in the mixed-integer case). The key practical requirement is that the problem can be modelled with a linear objective and linear constraints; if the objective or constraints are nonlinear, mixed-integer nonlinear programming (MINLP) extensions are needed.
Strengths & limitations
- Produces exact optimal solutions with a certified optimality gap, unlike heuristics that offer no quality guarantee.
- Handles binary and general integer variables natively, making it the natural framework for combinatorial decisions.
- Applicable across a wide range of domain problems — scheduling, routing, assignment, knapsack — with the same mathematical machinery.
- Modern branch-and-cut solvers can solve problems with millions of variables and constraints that would have been intractable decades ago.
- Integer programming is NP-hard in general; solve time can grow exponentially with problem size and poor formulation.
- A weak LP relaxation (large integrality gap) leads to deep, expensive search trees and long runtimes.
- Binary expansion of large-cardinality categorical variables can blow up model size.
- For very large instances, solvers may need to be terminated early with a gap tolerance rather than achieving zero gap.
Frequently asked
What is the difference between IP and MIP?
In pure integer programming (IP) every decision variable must be an integer. In mixed-integer programming (MIP), some variables are integers or binary while others are allowed to be continuous. MIP is the more general and more commonly used framework in practice, because most real problems mix discrete choices with continuous quantities.
Why is integer programming NP-hard if linear programming is polynomial?
Linear programming optimises over a convex polytope and can be solved in polynomial time by the simplex or interior-point methods. Adding integrality constraints shatters this convexity: the feasible set becomes a finite but potentially astronomically large set of integer points, and no polynomial-time algorithm is known to find the best one in general. The LP relaxation provides a bound but not a direct solution.
How do I know whether my solution is optimal?
The solver reports an optimality gap — the percentage difference between the best integer solution found and the best remaining lower bound. A gap of 0% certifies global optimality. For large problems you may set a gap tolerance (e.g., 1%) and accept a near-optimal solution; the bound still guarantees that the true optimum cannot be more than that percentage better.
What makes a 'tight' formulation and why does it matter?
A tight formulation is one whose LP relaxation gives a bound close to the integer optimum, leaving a small integrality gap. When the gap is small, branch-and-bound needs to explore fewer nodes and terminates faster. Adding valid inequalities such as Gomory cuts, cover inequalities, or clique cuts tightens the formulation and is often the most impactful way to speed up a solver.
Sources
- Wolsey, L.A. (1998). Integer Programming. Wiley. ISBN: 9780471283669
- Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley. ISBN: 9780471359432
How to cite this page
ScholarGate. (2026, June 1). Integer Programming (IP / Mixed-Integer Programming). ScholarGate. https://scholargate.app/en/optimization/integer-programming
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Constraint ProgrammingOptimization↔ compare
- Dynamic ProgrammingOptimization↔ compare
- GOAL-PROGRAMMINGDecision-making↔ compare
- Linear ProgrammingOptimization↔ compare