Integer Programming — IP and Mixed-Integer Programming (MIP)
- Introduced by
- Ralph Gomory (cutting planes, 1958); land-and-doig branch-and-bound (1960)
- Year
- 1958
- Type
- Mathematical optimisation — exact combinatorial method
What does it do?
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.
The intuition behind the method
Ordinary linear programming finds the best point in a continuous feasible region. But many real decisions are discrete — you cannot staff 2.7 nurses or open half a warehouse. Integer programming adds the constraint that some or all variables must be whole numbers (or binary 0/1 choices). The price of that constraint is computational: the feasible set is no longer a smooth surface but a scattered set of points, and finding the best one can require examining an enormous number of candidate solutions. Solvers manage this by intelligently splitting the problem into smaller sub-problems (branching) and pruning branches that cannot beat the best solution found so far (bounding), while also tightening the continuous approximation through added inequalities (cutting planes).
History
Integer programming emerged in the late 1950s as researchers sought to extend linear programming to discrete decisions. Ralph Gomory introduced the systematic cutting-plane method in 1958, proving that any integer programme could in principle be solved by adding finitely many cuts. Land and Doig (1960) formalised branch-and-bound, which became the dominant exact algorithm. Wolsey (1998) and Nemhauser and Wolsey (1988) provided the canonical textbook treatments that the field still relies on. The practical revolution came with the development of branch-and-cut solvers in the 1990s, combining both techniques with advanced heuristics, and later with the explosion of commercial and open-source solver performance that enables large-scale real-world applications today.
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.
Limitations and considerations
- 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.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- 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.
Applications
- Staff and nurse scheduling — assigning shifts to meet coverage requirements while respecting work-hour regulations.
- Vehicle routing and logistics — finding minimum-cost delivery routes under capacity and time-window constraints.
- Facility location — deciding which warehouses or plants to open to minimise total distribution cost.
- Capital budgeting — selecting a portfolio of investment projects within a budget to maximise total return.
- Production planning — determining integer lot sizes across time periods to balance setup costs and holding costs.
- Network design — choosing which links to install in a communication or transportation network.
How it works
How it works
The problem is cast as a mathematical programme: define decision variables (which must be declared as integer or binary where the problem requires it), write a linear objective function to minimise or maximise, and list all linear constraints. A tight formulation — one whose continuous (LP) relaxation is as close as possible to the true integer optimum — dramatically reduces solve time.
The integrality restrictions are temporarily dropped to obtain the LP relaxation. Solving this relaxation is fast and yields a bound: its optimal value is always at least as good as the true integer optimum (a lower bound for minimisation). If the relaxation solution happens to be all-integer, the problem is solved. Otherwise the gap between the relaxation and integrality guides the search.
A fractional variable in the relaxation solution is selected and the problem is split into two sub-problems — one requiring that variable to be rounded down, one rounded up. Each sub-problem is itself relaxed and solved, creating a search tree. Branches whose relaxation bound is worse than the best integer solution found so far are pruned without further exploration.
Cutting planes are valid linear inequalities that cut off part of the LP-relaxation feasible region without removing any integer feasible point. Adding strong cuts (Gomory cuts, cover inequalities, clique cuts) tightens the LP bound and reduces the number of nodes the solver must explore.
The best integer feasible solution found across all explored nodes is returned as the optimum. The optimality gap — the percentage difference between the best integer solution and the best remaining bound — is reported; a gap of zero certifies global optimality. For large NP-hard instances, the solver may terminate early with a user-specified gap tolerance, returning a near-optimal solution with a provable bound.
Common pitfalls
- Declaring variables as continuous when they should be integer — or vice versa — silently produces wrong solutions; always verify variable types match the physical reality of the problem.
- A loose formulation with a large LP relaxation gap causes excessive branching; invest time in formulation tightening (strong inequalities, symmetry breaking) before solving.
- Ignoring the integrality gap in the solver output: a reported objective value is only the best integer solution found, not necessarily the global optimum unless the gap is zero.
- Applying IP to problems whose objective or constraints are nonlinear without appropriate MINLP treatment will yield incorrect models.
- For scheduling or routing problems, failing to add valid inequalities (such as clique or cover cuts) leaves substantial performance gains on the table.
Frequently asked questions
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.
Related methods
Sources
Wolsey, L.A. (1998). Integer Programming. Wiley.
ISBN: 9780471283669Copied.Nemhauser, G.L. & Wolsey, L.A. (1988). Integer and Combinatorial Optimization. Wiley.
ISBN: 9780471359432Copied.