Mixed-Integer Programming — Exact optimization over continuous and integer decisions
Mixed-Integer Programming (MIP) — Mathematical optimization with continuous and integer decision variables · 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.
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.
+6 more
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.
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
- Nemhauser, G. L., Wolsey, L. A. (1988). Integer and Combinatorial Optimization. Wiley-Interscience, New York. ISBN: 9780471359432
- Wolsey, L. A. (1998). Integer Programming. Wiley-Interscience, New York. ISBN: 9780471283669
How to cite this page
ScholarGate. (2026, June 3). Mixed-Integer Programming (MIP) — Mathematical optimization with continuous and integer decision variables. ScholarGate. https://scholargate.app/en/simulation/mixed-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.
- Branch and BoundOptimization↔ compare
- Dynamic ProgrammingOptimization↔ compare
- Genetic AlgorithmOptimization↔ compare
- Linear ProgrammingOptimization↔ compare
- Multi-objective mixed-integer programmingSimulation↔ compare
- Stochastic Mixed-Integer ProgrammingSimulation↔ compare