How to Model an Integer Linear Program (ILP)

Concept

Modeling is choosing what the solver is allowed to do

An ILP solver is extremely literal. It does not infer “common sense.” If a rule is not written as a constraint, the solver treats it as optional. That’s why many “solver mistakes” are actually modeling omissions.

If you’re deciding whether your model should be pure ILP or mixed (MILP), see ILP vs MILP. For many problems, forcing everything to be integer is a common reason for slow solves.

Beginner → intermediate

Most “bad ILPs” are actually “bad data definitions”

Good models separate what the solver can choose (variables) from what the world provides (data/parameters). Before writing constraints, write down: (1) your index sets, (2) your parameters with units, and (3) reasonable bounds implied by physics/business rules.

Workflow

The “artifact” approach: what to produce at each step

Professionals don’t jump from story to equations in one shot. They create small artifacts that are easy to verify, then solve a tiny instance as early as possible.

Beginner level

Decisions become variables; data stays parameters

Start by asking: “What can the optimizer choose?” Those choices are variables. Everything else—costs, capacities, time limits—is data (parameters).

• Binary x∈{0,1}: choose/assign/open/activate.
• Integer x∈ℤ: counts, batches, number of units.
• Continuous x∈ℝ: flows, quantities, time, energy.

Intermediate

A variable table template (steal this)

A “variable table” prevents ambiguity and makes debugging much faster. You can build this in your notes before writing any constraints:

Advanced (simplified)

Bounds are not optional—they define your feasible region and your Big‑M

Tight bounds shrink the search space and strengthen LP relaxations (which improves pruning in branch-and-bound). They also let you derive smaller (safer) Big‑M values. “Use M = 1,000,000” is not a modeling strategy—it’s usually a performance bug.

If you don’t know a bound, derive one from physical limits: maximum demand, maximum production, maximum time, maximum inventory, or a hard business limit. If you can’t justify a bound in words, it’s rarely a good Big‑M.

Objective design

Don’t hide constraints inside the objective unless you truly mean “soft”

A clean modeling habit is separating: hard rules (must always hold → constraints) from preferences (nice to have → penalties in the objective).

minimize/maximize  Z = Σ c_i x_i + Σ p_k s_k

Here s_k can represent violation/slack variables for “soft constraints.” This is valid modeling, but only if penalty weights p_k represent real trade-offs.

Practical insight

When is it better to use a constraint instead of a penalty?

If violating a rule would be unacceptable in the real world (safety, legal compliance, service-level minimums), write it as a constraint. Penalties are best for “nice-to-have” objectives like balancing workload or reducing overtime, where small violations are acceptable and you want the model to choose the least-bad tradeoff.

Templates

A compact pattern library (the “grammar” of most ILPs)

If your model is primarily shipping/flow with linear costs, test the specialized structure with the Transportation Problem calculator before building a full ILP/MILP. Many flow problems are naturally “LP-friendly” and solve extremely fast.

Logic modeling

Implication with binaries (often no Big‑M needed)

If x and y are binary and you want “if x then y”, use:

x ≤ y

This eliminates the forbidden case (x=1, y=0). It’s one of the cleanest logic constraints you can write.

How do you model AND / OR with binaries?

Let z represent z = (x AND y) for binaries. A common linearization is:

z ≤ x
z ≤ y
z ≥ x + y - 1
x,y,z ∈ {0,1}

For z = (x OR y):

z ≥ x
z ≥ y
z ≤ x + y
x,y,z ∈ {0,1}

Either-or: exactly one option must be chosen

x + y = 1

Big‑M method

Big‑M is a bound disguised as logic

Big‑M works only because M is (implicitly) an upper bound on something. Oversized M weakens the LP relaxation and can make models slow or numerically unstable. Undersized M can cut off valid solutions and create “false infeasibility.”

A repeatable method to choose M (what professionals actually do)

1. Start from reality: what is the maximum possible value of the expression you’re trying to “turn off”?
2. Use constraint-specific M: different constraints often have different valid bounds—avoid one global mega-M.
3. Prefer derived bounds: use capacity, demand, or time windows to compute the smallest safe M.
4. Validate with LP relaxation: if the relaxed model becomes “too good to be true,” M is likely too large (or bounds are missing).

How do you know if M is too small?

You’ll often see infeasibility or suspiciously poor objective values because valid solutions are being cut off. A diagnostic test: temporarily increase M. If feasibility or objective quality changes materially, your original M was likely invalid.

How do you know if M is too large?

Your LP relaxation bound becomes overly optimistic (far from any integer-feasible solution), and branch-and-bound struggles to prune. Use the LP relaxation diagnostic below to confirm.

Diagnostics

The fastest “model health check”: compare ILP vs LP relaxation

The LP relaxation bound is the objective value of your model after relaxing integrality (binaries become 0 ≤ x ≤ 1, integers become continuous). It’s the same diagnostic tool solvers use inside branch-and-bound.

1. Solve the integer model in the ILP calculator → get an incumbent objective.
2. Relax integrality and solve in the LP calculator → get the LP bound.
3. Compare: if the LP bound is unrealistically better, tighten bounds, shrink Big‑M, or strengthen constraints.

Interpretation

What to read when the solver stops early

Solvers track a best feasible solution (the incumbent) and a best proven bound (often from relaxations). The difference becomes the optimality gap.

Minimization: BestBound ≤ Optimum ≤ Incumbent
Maximization: Incumbent ≤ Optimum ≤ BestBound

Practical takeaway: even if you stop early, you can report a certified interval (“the optimum lies between A and B”). For a dedicated interpretation guide, see optimality gap in MIP.

Worked example (numeric)

Example 1: project selection under a budget (0–1 ILP you can verify by hand)

Scenario: You can fund projects A, B, C. Budget = 10. Costs: A=6, B=5, C=4. Values: A=9, B=8, C=6.

Model (x_A, x_B, x_C ∈ {0,1}):

maximize   9xA + 8xB + 6xC
subject to 6xA + 5xB + 4xC ≤ 10
xA, xB, xC ∈ {0,1}

Why each line matters:

• The objective encodes the definition of “best” (total value).
• The budget constraint blocks impossible combinations (like picking all three: cost 15).
• Binaries ensure “pick or don’t pick”—no fractional projects.

Validation (quick manual check):

• A+B cost 11 (infeasible)
• A+C cost 10, value 15 (feasible)
• B+C cost 9, value 14 (feasible)
• Best feasible is A+C with value 15

Worked example (linking + Big‑M as capacity)

Example 2: facility open/close with shipping (Big‑M done right)

Story: Decide which facilities to open, then ship to customers. Variables: open decisions y_j∈{0,1}, shipment quantities x_{j,k}≥0.

minimize   Σ fixed_j y_j + Σ shipCost_{j,k} x_{j,k}
subject to Σ_j x_{j,k} ≥ demand_k               ∀k
           Σ_k x_{j,k} ≤ cap_j · y_j            ∀j
           y_j ∈ {0,1}, x_{j,k} ≥ 0

Interpretation: The linking constraint Σ_k x_{j,k} ≤ cap_j·y_j says: if y_j=0, then shipments must be 0; if y_j=1, shipments are allowed up to real capacity. Here, cap_j is your Big‑M (but it’s meaningful and tight).

Worked example (logic)

Example 3: “Either outsource or build capacity” (either–or logic)

Scenario: You must satisfy demand of 100 units. You can either (a) outsource units at $7/unit, or (b) build a machine (fixed $300) and produce in-house at $3/unit with capacity 120. You want the cheaper plan.

Let y = 1 if you build the machine, else 0. Let x be in-house production, o outsourced units.

minimize   300y + 3x + 7o
subject to x + o = 100
           0 ≤ x ≤ 120y
           o ≥ 0
           y ∈ {0,1}

Why the linking constraint is the key: 0 ≤ x ≤ 120y forces x=0 when y=0. Without it, the solver could produce without paying the fixed cost—an extremely common beginner error.

Quick interpretation:

• If you don’t build (y=0): x=0, o=100, cost = 700
• If you build (y=1): choose x=100, o=0, cost = 300 + 300 = 600

So building is optimal here. If demand dropped to 40, outsourcing might win—this is a good “what-if” test for your model.

Debugging

Why is my ILP infeasible?

1. Check bounds first: are you accidentally forcing something like x ≥ 1 and x ≤ 0?
2. Check equalities: “exactly one” and “exactly meet demand” constraints clash easily with tight capacities.
3. Solve the LP relaxation: if the relaxation is infeasible too, the issue is constraints/data (not integrality).
4. Check Big‑M validity: if LP is feasible but ILP is infeasible, logic/integrality constraints may be too strict (or M too small).

Debugging

Why is my model unbounded?

Unbounded usually means you’re maximizing something with no upper bound (or minimizing with no lower bound), often due to a missing constraint, wrong inequality direction, or missing variable bounds. Add real limits (capacity, demand, conservation) and verify signs carefully.

Debugging

Why is my solution feasible but not what I meant?

This almost always indicates a missing business rule. The fastest fix is to re-write the story sentence and add the missing rule as a constraint family. Common missing pieces:

• Missing linking constraints (binaries not connected to quantities)
• Wrong “one-of” logic (you meant “exactly one,” wrote “at least one”)
• Unit mismatch (objective mixes dollars/hours/penalties without conversion)

Mistakes

High-frequency mistakes (with quick prevention)

• Missing bounds: makes Big‑M huge and relaxations weak. Add realistic maxima early.
• Wrong inequality direction: silently flips feasibility. Re-read each constraint as an English sentence.
• Over-integerization: forcing continuous quantities to be integer can explode runtime (see ILP vs MILP).
• Oversized Big‑M: causes slow branch-and-bound and large gaps; diagnose with LP relaxation bound.
• Coefficient scaling issues: huge magnitude differences can cause numerical instability and weak progress.

Questions people ask

How do I choose decision variables in an ILP model?

Choose variables that directly represent the decision you will implement. If a manager could read your variable definition and say “yes, that’s exactly what we choose,” you’re on the right track. Avoid defining variables that represent intermediate math artifacts unless they are needed to keep constraints linear (e.g., absolute value or max variables).

Questions people ask

What is the difference between a constraint and a penalty in ILP?

A constraint is a rule that must always hold (budget cap, legal requirement, safety). A penalty is a preference: you allow violation but charge for it in the objective using slack/violation variables. If violating the rule would make the solution unusable, model it as a constraint.

Questions people ask

How do I linearize an if-then constraint?

If both sides are binary, “if x then y” is often simply x ≤ y. If a binary controls a continuous quantity, use linking constraints like 0 ≤ q ≤ U·y. When you do use Big‑M, derive M from a real bound (capacity, demand, time limit) instead of a huge constant.

Questions people ask

Why is my MILP/ILP solver so slow even for a small model?

“Small” in number of variables is not the same as “easy.” The strongest predictor is the LP relaxation tightness. If the LP relaxation bound is far from your best integer solution, branch-and-bound has weak pruning power and may explore many nodes. Use LP relaxation bound as your first diagnostic before tuning solver settings.

Questions people ask

What happens if I relax integrality (binary to continuous)?

You get the LP relaxation: the same constraints but with a larger feasible set. That solution provides a bound on the integer optimum and is the core engine behind branch-and-bound. Practically, it tells you whether your formulation is “tight” (good) or “loose” (needs better bounds/Big‑M/constraints).

Questions people ask

How do I know whether to stop early when the solver reports an optimality gap?

Convert the incumbent and best bound into a certified interval and ask: (1) is the incumbent implementable and stable under small changes? (2) is the remaining gap small enough that further improvement isn’t worth time or complexity? If the gap is large and the LP bound is unrealistic, refactor the model first (bounds + Big‑M + strengthening) rather than only increasing time. See optimality gap in MIP.

Next step

Test your model (and learn faster)

Paste your formulation into the Integer Linear Programming Calculator and review feasibility and objective. Then compute the relaxation with the LP calculator to diagnose whether your formulation is tight.