Mixed-Integer Programming — Exact optimization over continuous and integer decisions
Also known as: MIP, Mixed-Integer Linear Programming, MILP, Integer Programming
Mixed-Integer Programming (MIP) is a mathematical optimization framework in which some decision variables must take integer values while others may be continuous. It generalizes linear programming and is widely used in operations research, logistics, scheduling, resource allocation, and engineering design, where indivisibility constraints — such as yes/no decisions or whole-unit quantities — arise naturally.
Key highlights
- Produces provably optimal solutions with a quantifiable optimality gap, enabling rigorous decision justification.
- Handles binary and general integer variables natively, capturing real-world indivisibility and logical constraints.
- Modern solvers (Gurobi, CPLEX, SCIP) exploit advanced branch-and-bound, cutting planes, and presolve to handle large instances efficiently.
- Transparent model formulation makes assumptions explicit and auditable by domain experts.
- Supports sensitivity analysis and parametric studies to understand how solutions change with input data.
- Widely supported by modeling languages (AMPL, GAMS, Pyomo, JuMP) enabling rapid prototyping.
Intuition
This section is available to Pro members. Upgrade to Pro
How it works
This section is available to Pro members. Upgrade to Pro
When to use it
Use MIP when your problem has a linear or linearizable objective and constraints and includes decisions that must be integer-valued (facility location, crew scheduling, capital budgeting, network design, cutting-stock problems). It is the method of choice when you need a provably optimal or bounded-gap solution and problem size is tractable (thousands of variables with modern solvers). Do NOT use MIP when the objective or constraints are highly nonlinear (use nonlinear or mixed-integer nonlinear programming instead), when the problem is so large that exact methods are prohibitive (consider heuristics or metaheuristics), or when continuous approximations are accurate enough (use LP for speed).
Strengths & limitations
- Produces provably optimal solutions with a quantifiable optimality gap, enabling rigorous decision justification.
- Handles binary and general integer variables natively, capturing real-world indivisibility and logical constraints.
- Modern solvers (Gurobi, CPLEX, SCIP) exploit advanced branch-and-bound, cutting planes, and presolve to handle large instances efficiently.
- Transparent model formulation makes assumptions explicit and auditable by domain experts.
- Supports sensitivity analysis and parametric studies to understand how solutions change with input data.
- Widely supported by modeling languages (AMPL, GAMS, Pyomo, JuMP) enabling rapid prototyping.
- Worst-case complexity is NP-hard; solve time can grow exponentially with the number of integer variables.
- Requires a precise mathematical formulation; poorly formulated models can be intractable even when the underlying problem is manageable.
- Non-convex or nonlinear elements require additional linearization or specialized solvers, increasing model complexity.
- Solver licensing costs can be significant for commercial tools, though high-quality open-source alternatives exist.
- Results are only as good as the model: incorrect constraint specification leads to meaningless optima.
Common pitfalls
This section is available to Pro members. Upgrade to Pro
Applications
This section is available to Pro members. Upgrade to Pro
Frequently asked
How is MIP different from linear programming (LP)?
LP requires all decision variables to be continuous (real-valued), which can yield fractional solutions that are physically infeasible (e.g., 2.7 trucks). MIP adds integrality constraints on some or all variables, enforcing whole-number or binary solutions at the cost of greater computational complexity.
When should I use a heuristic instead of MIP?
When the problem has millions of variables, highly nonlinear structure, or requires a near-real-time solution, exact MIP may be too slow. Metaheuristics (genetic algorithms, simulated annealing) can produce good solutions quickly, but without optimality guarantees. MIP is preferred when solution quality certification matters.
What is the optimality gap and how small should it be?
The gap is (incumbent objective - LP bound) / LP bound, expressed as a percentage. It certifies how far the best known integer solution can be from the true optimum. For most practical applications a 0.1–1% gap is sufficient; tighter gaps require exponentially more solver time.
Can MIP handle nonlinear objectives or constraints?
Standard MIP assumes linearity. Nonlinear relationships must be linearized (e.g., piecewise-linear approximation, binary expansion of products) or handled by mixed-integer nonlinear programming (MINLP) solvers, which are significantly harder to solve.
Which solvers are recommended for MIP?
Commercial: Gurobi and CPLEX are the industry benchmarks. Open-source: SCIP, CBC (via COIN-OR), and HiGHS are competitive for moderate-sized problems. All support standard modeling interfaces such as AMPL, Pyomo, and JuMP.
Sources
- 1.Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York.ISBN 9780471359432
- 2.Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York.ISBN 9780471283669
You have read it. What now?
Cite this page
ScholarGate. (2026, June 3). Mixed-Integer Programming. ScholarGate. https://scholargate.app/simulation/mixed-integer-programming