ILP Beginner’s Guide: Integer Linear Programming

Beginner level

ILP is “choose the best combination” under rules

Think of ILP as a disciplined way to answer: “Out of many possible combinations, which one is best—while obeying all the rules?” The rules are constraints (budgets, capacity, logic). The best is your objective (min cost, max profit, min lateness, etc.).

The integer part matters because many decisions cannot be fractional: you can’t open 0.3 warehouses or assign 0.5 people to a shift. When a model forces those decisions to be whole numbers, it becomes an integer program.

Intermediate level

The standard math form you’ll see in solvers

minimize or maximize:   cᵀx
subject to: A x ≤ b
x ∈ ℤⁿ
Common special cases:
• Binary ILP: x ∈ {0,1}ⁿ
• Bounded integers: ℓ ≤ x ≤ u, x ∈ ℤⁿ

If you add continuous variables (flows, amounts, time) alongside integer variables, you get a mixed-integer linear program (MILP). If you’re not sure which you have, the decision-focused explanation in ILP vs MILP helps.

College-level (simplified)

Why ILP feels harder than LP: geometry + combinatorics

In linear programming (LP), the feasible region is a continuous polytope. In ILP, you’re restricted to integer points inside that polytope. The solver can’t simply slide to the best corner; it must reason about discrete combinations.

Method

Step 1: Write the decision in one sentence

Example: “Choose which projects to fund to maximize expected value without exceeding budget and with at most one project per team.” This sentence already contains your objective and two constraint families.

Method

Step 2: Define variables that match the decision (not the math)

Beginners often define too many variables. Start with the smallest set that directly represents the decision. Common ILP variables: x_i = 1 if you choose item i; x_{ij} = 1 if you assign i to j.

Method

Step 3: Build constraints in “families”

Don’t write constraints randomly. Write them as families: “for each task…”, “for each worker…”, “for each day…”. This is also how you validate them (checking one row at a time).

If you want a pattern library for constraints and logic modeling, use how to model an ILP.

Method

Step 4: Decide objective coefficients and units (then sanity-check)

A common beginner error is unit mismatch: mixing dollars, hours, and penalties without scaling. Your objective coefficients should reflect one consistent “score” you genuinely want to optimize.

Cheat sheet

Common patterns and how they read in English

Once you can write these patterns from memory, the “hard part” becomes choosing the right variables and correct coefficients.

Domains

Choosing the domain is part of modeling—not a technical afterthought

If you have both continuous and discrete decisions, you’re in MILP territory. Use ILP vs MILP to decide whether the mixed structure is necessary.

Key concept

LP relaxation: the fastest bound and the best modeling diagnostic

Relaxing integrality means turning binary/integer restrictions into continuous ones (while keeping bounds). Example: x ∈ {0,1} becomes 0 ≤ x ≤ 1.

The solution gives the LP relaxation bound. For minimization it’s a lower bound; for maximization it’s an upper bound.

Solver mechanics

Branch-and-bound: “prove what’s impossible,” not “try random combinations”

Most ILP/MILP solvers use branch-and-bound (often with cutting planes). The solver repeatedly: (1) solves an LP relaxation to get a bound, (2) branches on a fractional variable, and (3) prunes regions that provably can’t beat the best feasible solution found (the incumbent).

Interpretation

Read solver status like a scientist (what is certified?)

If a run stops with a nonzero gap, treat it as information—not failure. The optimality gap guide shows how to interpret “2% gap” correctly.

Mini-lab

Lab 1: See “integrality” with your own eyes (ILP vs LP relaxation)

1. Solve a small binary selection model in the ILP calculator. Record the chosen items and objective.
2. Relax each binary variable to 0 ≤ x_i ≤ 1 and solve the relaxed model in the LP calculator.
3. Compare objectives. If the LP value is much better, your relaxation is loose—expect more branch-and-bound work. Read: LP relaxation bound.

Mini-lab

Lab 2: Interpret early stopping using incumbent vs bound

1. Run a model in the ILP calculator that may stop early.
2. Capture the incumbent and the best bound (if reported).
3. Interpret uncertainty using optimality gap in MIP.

If your gap is stubbornly large, tightening the formulation often works better than simply increasing runtime.

Worked example (beginner)

Example 1: project selection under budget (0–1 ILP)

maximize Σ value_i x_i
subject to Σ cost_i x_i ≤ Budget
x_i ∈ {0,1}

Why this works: the budget constraint is the knapsack pattern; binaries enforce discrete selection.

Next, relax x_i to 0 ≤ x_i ≤ 1 in the LP calculator. Fractional items explain why ILP differs from LP.

Worked example (structure)

Example 2: assignment with “exactly one” constraints

minimize   Σ cost_ij x_ij
subject to Σ_i x_ij = 1 for each task j
           Σ_j x_ij ≤ cap_i for each worker i
           x_ij ∈ {0,1}

Most “wrong assignment” solutions happen because one constraint family is missing.

Worked example (logic)

Example 3: modeling a dependency (“if A then B”)

x_A ≤ x_B
x_A, x_B ∈ {0,1}

This blocks the only forbidden case: choosing A without choosing B.

For more logic patterns (either/or, at-most-k, linking), use how to model an ILP.

Debugging

Why is my ILP infeasible?

• Check bounds: look for hidden contradictions like x ≥ 1 and x ≤ 0.
• Check equalities: “exactly one” constraints clash easily with tight capacity.
• Relax integrality: if even the LP is infeasible, the issue is constraints/data, not integrality.

The diagnostic logic is explained in LP relaxation bound.

Common mistakes

Mistake: “Not optimal” ≠ “bad solution”

Many solvers stop with a feasible incumbent but without a proof of optimality. Use the optimality gap to quantify what’s still possible.

People ask

How do I know whether my problem should be ILP or MILP?

If some decisions must be discrete (yes/no, counts) but other quantities are naturally continuous (flows, time, energy), you likely need MILP. If everything must be discrete, you’re in ILP. A practical guide is: ILP vs MILP.

People ask

Why does my ILP solution look “weird” even though it’s feasible?

Usually a missing rule. Rewrite your story sentence, then ensure each rule appears as a constraint family. The pattern checklist in how to model an ILP is designed for this.

People ask

What is the LP relaxation bound and why do professionals compute it?

It’s the objective value you get when you drop integrality but keep all linear constraints and bounds. It predicts how hard branch-and-bound may need to work and helps diagnose weak formulations: LP relaxation bound.

Learning path

A progression that mirrors how ILP is learned in practice

1. Build and solve 2–3 tiny models with the ILP calculator.
2. Learn reusable constraint patterns with how to model an ILP.
3. Use LP relaxation bounds as your diagnostic tool with the LP calculator.
4. Interpret early stopping using optimality gap.
5. Understand solver mechanics using branch-and-bound.