ILP vs MILP: What changes when you add continuous variables?

Definitions

ILP vs MILP in one precise statement

Both are linear objective + linear constraints. The difference is the variable domains:

ILP:
  minimize/maximize   cᵀx
  subject to          Ax ≤ b
                      x ∈ ℤⁿ  (often x ∈ {0,1}ⁿ)

MILP:
  minimize/maximize   cᵀx + dᵀy
  subject to          A x + B y ≤ b
                      x ∈ ℤⁿ (some integer/binary)
                      y ∈ ℝᵐ (some continuous)

“MIP” (mixed-integer programming) is the umbrella term. ILP (all integer) and MILP (mixed integer + continuous) are both special cases of MIP.

If you want a warm-up on variables, constraints, and feasibility before comparing ILP vs MILP, start with the ILP beginner’s guide.

Decision guide

Ask these questions in order (to avoid accidental MILPs)

People ask

What is the difference between ILP and MILP in optimization?

In ILP, all decision variables are integer (often 0–1). In MILP, you have a mix of integer and continuous variables. Both use a linear objective and linear constraints; both are typically solved by branch-and-bound/branch-and-cut. The practical difference is that MILP lets you combine binary logic (open/close, yes/no) with continuous decisions (flows, times).

People ask

Is MILP always harder to solve than ILP?

No. Difficulty depends on formulation strength, not just on the presence of continuous variables. What often makes MILPs challenging is the linking logic (Big‑M, on/off constraints) that can create very loose LP relaxations and weak bounds. Tight MILPs can be easier than poorly formulated ILPs. Use the LP relaxation bound as an objective measure of formulation strength.

People ask

Can every MILP be rewritten as an ILP (or vice versa)?

In principle, you can sometimes eliminate continuous variables via substitution or aggregation, turning a MILP into an ILP. But when continuous quantities genuinely matter (flows, times, energies), forcing everything into integer form either loses realism or creates an unnecessarily huge search space. In practice, you choose ILP vs MILP based on the decisions you need to implement, not on theoretical equivalence.

People ask

When should you prefer a pure LP instead of ILP or MILP?

If all decisions can be meaningfully fractional (e.g., splitting flow, continuous production levels) and you do not need discrete logic, a pure LP is usually orders of magnitude faster and easier to analyze. LP is also your main diagnostic relaxation for ILP/MILP models—see LP relaxation bound.

Pattern

1) On/off + amount (facility open/close + flow)

If a binary decision activates a continuous quantity—like “open facility” and “ship amount”—you are in MILP territory. The standard linking is:

0 ≤ y ≤ U x
x ∈ {0,1},  y ≥ 0

The whole formulation quality depends on U. If U is huge “to be safe,” the LP relaxation is weak and bounds are overly optimistic, often causing a stubborn optimality gap.

For practical tightening strategies (choosing the smallest valid U, using real capacities), use how to model an ILP—the same patterns apply to MILP.

Pattern

2) Piecewise-linear costs and tariffs

Tiered pricing, volume discounts, and convex/concave approximations are usually implemented as piecewise-linear functions. They almost always require extra continuous variables for segment amounts and binaries for segment activation.

Pattern

3) Fixed-charge decisions (“pay to use”)

“If we use a lane, pay a fixed cost” or “if we build a plant, pay a fixed charge” is classic MILP structure: binaries encode the fixed decision, and continuous variables encode usage amount.

This is also where naive Big‑M choices often hide. If such models are slow or show a large gap, this is the first area to tighten.

Solver mechanics

ILP and MILP are both solved by branch-and-bound (often branch-and-cut)

Modern solvers use branch-and-bound, enhanced with cutting planes, presolve, and heuristics. So “ILP vs MILP” is less about which algorithm is used and more about what that algorithm sees at each node: tight or loose relaxations, strong or weak bounds, and easy or hard pruning.

For a solver-aligned explanation, see branch-and-bound in integer programming.

Diagnostics

The LP relaxation bound is your formulation “health check”

If your LP relaxation bound is very optimistic compared to your best integer solution, proving optimality will likely take longer. This is true for both ILP and MILP, but loose MILP relaxations are more common because of Big‑M/linking patterns.

Use LP relaxation bound to interpret this gap, and compute relaxations with the LP calculator.

Early stopping

Compare formulations using the optimality gap (not just “how it feels”)

When you stop at a time limit, the right question is: “How far could we still be from the true optimum?” The optimality gap summarized by incumbent and best bound answers this question.

In practice, if one MILP formulation yields a tighter gap than another in the same runtime, it is usually the better model, even if both return similar incumbents.

Mini-lab

Lab 1: Decide “ILP or MILP?” using data, not guesswork

1. Solve the discrete model in the ILP/MILP calculator. Record objective and chosen decisions.
2. Relax integrality and/or remove binaries to create an LP version, then solve it in the LP calculator.
3. If the LP solution uses fractional logic or is unrealistically optimistic, a pure ILP/LP may be insufficient—you may genuinely need MILP.

Mini-lab

Lab 2: Diagnose “MILP is slow” (bound problem vs incumbent problem)

Run your MILP in the ILP/MILP calculator with a modest time limit. Then:

• If the incumbent is good but the gap is large → bound problem (weak relaxation).
• If the bound is decent but there is no good incumbent → incumbent problem (feasibility/heuristics).

Use the bound lens from LP relaxation bound and the gap lens from optimality gap to decide whether you should refactor the model or run longer.

Worked example

Example 1: assignment as a clean ILP (binaries only)

Scenario: assign each of 5 tasks to 5 workers with minimum cost. Why ILP is enough: decisions are discrete; you are not modeling time or amount explicitly.

Variables: x_{i,j} ∈ {0,1}

minimize   Σ cost_{i,j} x_{i,j}
subject to Σ_i x_{i,j} = 1     ∀ task j
           Σ_j x_{i,j} = 1     ∀ worker i

Check after solving: each task is assigned exactly once; no worker handles more than one task; the chosen assignment changes if you alter a cost in the expected direction.

Try this in the ILP calculator, then relax to 0 ≤ x_{i,j} ≤ 1 and solve in the LP calculator. In many assignment problems, the LP is already integral, which is why they solve so quickly.

Worked example

Example 2: facility open/close + shipment quantities (canonical MILP)

Scenario: choose which facilities to open (fixed cost) and ship goods to customers (variable cost) while meeting demand. Why MILP is required: open/close decisions are binary, shipments are continuous.

y_f ∈ {0,1}              (open facility f)
x_{f,c} ≥ 0               (ship from facility f to customer c)

minimize  Σ fixed_f y_f + Σ shipCost_{f,c} x_{f,c}
s.t.      Σ_f x_{f,c} ≥ demand_c           ∀c
          Σ_c x_{f,c} ≤ cap_f · y_f        ∀f

Interpretation: the linking constraint Σ_c x_{f,c} ≤ cap_f · y_f is effectively a Big‑M structure. If cap_f is realistic, the relaxation is tighter; if it’s huge “just in case,” the bound becomes overly optimistic and the tree grows.

If you remove the binary variables (assume all facilities open), you get a pure transportation model; test that in the Transportation Problem calculator for insight into the continuous structure.

Misconception

“MILP is always harder than ILP”

Hardness is driven by weak relaxations, poor bounds, and symmetry—not by the presence of continuous variables alone. A well-structured MILP can be easier than a poorly formulated ILP.

Mistake

Using a huge Big‑M value “to be safe”

Oversized Big‑M values often dominate difficulty: they weaken the LP relaxation and lead to large gaps. Derive the smallest valid M/U from capacity, demand, or physical limits. See how to model an ILP for a practical Big‑M checklist.

Mistake

Skipping relaxation diagnostics and tuning solver knobs first

If the LP relaxation is weak, no amount of solver tuning replaces missing structure. Compute and interpret the relaxation using LP relaxation bound before you invest time in tuning.

Troubleshooting

Symptom → likely cause → best next move

When you stop early, interpret the remaining uncertainty with optimality gap in MIP, and connect that to the bound quality from LP relaxation bound.

Next steps

A practical path to confident ILP vs MILP choices

1. Build a small ILP or MILP in the ILP/MILP calculator.
2. Compute an LP relaxation bound in the LP calculator and interpret it using LP relaxation bound.
3. If the solve stops early, use optimality gap to quantify how far from optimal you could still be.
4. If performance is poor, refactor with how to model an ILP and, if branching seems mysterious, review branch-and-bound.

If anything here still feels abstract, loop back through the ILP beginner’s guide with a tiny example in front of you.