Integer Linear Programming (ILP/MILP) Calculator
Solve integer, binary (0–1), and mixed-integer linear programs. Shows LP relaxation bound and branch-and-bound steps.
Inputs
Branch & Cut is limited to small models (n ≤ 6, m ≤ 8).
Advanced solver settings
Model tables (edit your ILP here)
Tables render automatically when you change n or m. For very large n×m, rendering can be slow; use Render tables if needed. Learn modeling tips: How to model ILP.
Advanced sharing (Import/Export JSON)
JSON is an advanced format for saving/restoring the exact model. If you’re new, you can ignore this section. Learn: What is model JSON?
Results
Enter your model in the tables and click Solve.
Solution walkthrough (very detailed, your current model)
Format: #wt=…&autocalc=1
Graph
For n = 2, this shows a feasible-region scatter. For n > 2, this shows a solution-value bar chart (not a feasible region, since higher-dimensional regions cannot be visualized in 2D). Chart.js is used only if your site already provides it.
Branch-and-Bound steps
Node table shows LP bounds, fractional variables, and fathom reasons.
Steps will appear after you solve (if enabled).
On this page
Worked Examples
Each example includes a “Load this example” button that fills the tables for you.
Beginner
B1 — ILP (2 vars): Max 3x + 2y
2x + y ≤ 4
x + 2y ≤ 5
x,y ≥ 0 integers
Expected optimum: x=1, y=2, Z=7
B2 — Binary (2 vars): Choose at most one
x1 + x2 ≤ 1
x1,x2 ∈ {0,1}
Expected optimum: x1=1, x2=0, Z=5
B3 — Minimization (2 vars): Simple cost minimization
x + y ≥ 4
2x + y ≥ 6
x,y ≥ 0 integers
Notes: LP relaxation gives a bound; branching forces integrality.
Medium
M1 — MILP: One integer + one continuous variable
2x + y ≤ 7
x + 2y ≤ 8
x integer ≥0, y continuous ≥0
This shows why MILP can mix variable types.
M2 — Equality constraint (requires artificials in simplex)
x − y = 0
x ≤ 5, y ≤ 5
x,y integers ≥0
Good for testing equality handling + bounds.
M3 — Infeasible ILP (diagnostic example)
x + y ≤ 1
x + y ≥ 3
x,y integers ≥0
Expected: infeasible.
Difficult
D1 — Binary knapsack (4 items)
4x1 + 6x2 + 3x3 + 2x4 ≤ 9
x1,x2,x3,x4 ∈ {0,1}
Notes: a classic B&B workload.
D2 — Mixed signs (tests numeric stability)
x1 − x2 + x3 ≤ 4
−2x1 + x2 + 2x3 ≤ 3
x1,x2,x3 integers ≥0
Notes: negative coefficients are allowed.
D3 — MILP with bounds (tests UB/LB)
x + y + z ≥ 7
2x + y ≤ 10
x integer [0,10], y continuous [0,10], z binary
Notes: bounds significantly affect feasibility and speed.
Extreme (still browser-safe)
X1 — 6-variable binary knapsack (heavier B&B)
5x1 + 3x2 + 4x3 + 6x4 + 2x5 + 5x6 ≤ 12
x1..x6 ∈ {0,1}
Notes: may explore many nodes; adjust node/time limits if needed.
X2 — Branch & Cut “small mode” demo (n=6,m=8)
x1 + x2 + x3 ≤ 4
x4 + x5 + x6 ≤ 4
x1 + x4 ≤ 4
x2 + x5 ≤ 4
x3 + x6 ≤ 4
x1 + x2 + x4 ≤ 5
x2 + x3 + x5 ≤ 5
x3 + x4 + x6 ≤ 5
x1..x6 integers ≥0
Notes: intended for “Branch & Cut (small; Gomory)” mode.
Questions People Ask
Integer Linear Programming basics (ILP vs LP)
What is the difference between linear programming and integer linear programming?
LP allows continuous variables, so optimal solutions can be fractional. ILP forces some or all variables to be integers (often 0–1), making the feasible set discrete and typically harder. This calculator shows the LP relaxation bound and the integer solution.
Why does the LP relaxation give a fractional solution in ILP?
Relaxing integrality expands the feasible region to a continuous polytope. The best corner point can fall between integer lattice points. Branch-and-bound (and optional cuts in small mode) enforces integrality.
What’s the difference between ILP and MILP?
ILP means all decision variables are integer. MILP allows a mix of integer/binary and continuous variables. Set each variable type in the Variables table. Learn more: ILP vs MILP.
Can I use simplex directly for integer programming?
Simplex solves the LP relaxation only. Integer solvers use simplex repeatedly at branch-and-bound nodes. For guaranteed integrality, you need B&B/cuts in addition to simplex.
Branch-and-Bound step-by-step (how the calculator decides)
How does branch and bound guarantee the optimal integer solution?
Each node solves an LP relaxation that bounds the best possible integer solution within that branch. Nodes are pruned if infeasible, already integral, or dominated by bounds. When all nodes are fathomed, the best found integer solution is optimal.
What is an LP relaxation bound and how is it used for pruning?
For maximization, the node LP objective is an upper bound on integer solutions in that node. If that bound is ≤ the incumbent objective, the node cannot improve and is pruned. The node table shows the prune reason. Learn more: LP relaxation bound.
Which variable should I branch on (most fractional vs largest impact)?
“Most fractional” (closest to .5) is common for reducing depth. “Largest impact” is a heuristic that tries variables that matter more for objective/feasibility. This calculator supports both and logs the chosen branch constraint.
What does “fathomed node” mean in branch and bound?
A node is fathomed when it no longer needs exploration—because it is infeasible, integral, or dominated by bounds. The calculator records the fathom reason for each node.
What is the optimality gap in integer programming?
The gap compares the incumbent objective to the best remaining bound from unexplored nodes. 0% means optimality is proven. If time/node limit stops early, the gap estimates how close the solution is to optimal. Learn more: Optimality gap in MIP.
How This Calculator Works (methodology)
This calculator is a browser-based educational ILP/MILP solver. It solves a sequence of LP relaxations (via a Big-M simplex method) and enforces integrality using Branch-and-Bound. For deeper learning, see the ILP Beginner’s Guide, our Branch-and-Bound guide, and the LP relaxation bound explainer.
Internally, the solver: (1) normalizes constraints, (2) handles variable bounds by turning upper bounds into constraints, (3) applies a nonnegative-variable transformation by shifting lower bounds, (4) solves each node’s LP relaxation, (5) checks integrality using your tolerance, (6) branches on a fractional integer variable, and (7) prunes nodes that are infeasible, integral, or cannot improve the incumbent.
Big‑M simplex note: equalities and “≥” constraints introduce artificial variables. A large penalty (M) discourages them in the optimum. This approach is simple and educational, but can be sensitive to scaling. If you use very large/small coefficients, consider rescaling your model.
Objective: Z = Σ c_i x_i + constant Constraints: Σ a_(j,i) x_i (≤, =, ≥) b_j Integrality check: |x_i - round(x_i)| ≤ tol Display rounding: 6 decimals (internals full precision) Gap: max: (BestBound - Incumbent) / max(1, |BestBound|) min: (Incumbent - BestBound) / max(1, |Incumbent|)
Note: browser solvers can be sensitive to degeneracy and numeric conditioning. For mission-critical decisions, validate with OR‑Tools / CBC / Gurobi / CPLEX and compare results.