Wait, What?
The hardest part of an integer optimisation problem is often not finding a good answer. It is proving that no better integer answer exists.
Mixed-integer programming sits at a powerful boundary between continuous optimisation and discrete choice. A linear program may suggest that a factory should build 2.4 machines, a hospital should assign 0.6 of a nurse, or a delivery route should be used 0.3 times. Mathematics allows those fractional points. The real problem often does not.
The professional task is therefore two-sided: find high-quality feasible integer solutions and simultaneously build evidence that the remaining search space cannot contain something better. Modern solvers do this through relaxations, branching, bounds, cutting planes, presolve, heuristics and carefully managed search.
Quick Answer
Learn mixed-integer programming through the route discrete decisions → mathematical model → LP relaxation → incumbent solution → lower/upper bounds → branching → pruning → cutting planes → presolve → heuristics → branch-and-cut → MIP gap → numerical reliability → solver diagnostics → professional model design. A beginner should be able to draw the feasible integer points of a tiny problem. A professional should be able to explain why the formulation, relaxation, branching strategy and stopping criterion make the solution credible.
1. Start With a Decision That Really Must Be Discrete
Integer variables are not decorations. They encode decisions whose fractional versions are meaningless or forbidden: open this facility or not, assign this worker or not, choose how many vehicles to buy, schedule a machine in one time slot, select one of several designs.
Before writing equations, ask which decisions are continuous, which are integer counts and which are binary yes/no choices. Google OR-Tools gives this distinction clearly in its current introduction to integer optimisation and MIP.
2. The LP Relaxation Is a Deliberate Simplification
If an integer restriction is temporarily removed, the result is often a linear-programming relaxation. The relaxed problem is easier to solve and its objective value provides a bound on what the integer problem can achieve.
For a maximisation problem, the relaxed optimum can be better than any feasible integer solution, so it supplies an upper bound. For minimisation it supplies a lower bound. This is the first key mental move: a fractional answer can be useful even when it cannot be accepted.
The existing How to Learn Linear Programming Algorithms article owns simplex, duality and continuous LP foundations. This article begins where integrality changes the search problem.
3. A Feasible Integer Solution Becomes the Incumbent
Once the solver finds a legal integer solution, it has an incumbent: the best feasible solution discovered so far. The incumbent gives the search a target to beat.
This creates a productive tension. Relaxations tell us how good a still-unexplored region could possibly be. The incumbent tells us how good we already know how to be. Search ends when the remaining possibility and the known reality become close enough—or equal.
4. Branching Divides One Impossible Choice Into Smaller Possible Worlds
Suppose the relaxation returns x=3.7 for a variable that must be integral. One simple branch is x≤3 versus x≥4. The original problem becomes two smaller subproblems.
Branching builds a search tree. Each node represents the original model plus extra restrictions inherited from the path above it. SCIP describes integer and constraint problems in exactly this recursive way: successively divide the problem into smaller subproblems.
5. Branch-and-Bound Is Search With Mathematical Receipts
A naïve tree search might explore every branch. Branch-and-bound avoids this by solving a relaxation at each node and comparing its bound with the incumbent.
- If the node is infeasible, prune it.
- If its relaxation already produces an integer solution, update the incumbent if appropriate and close the node.
- If its bound cannot beat the incumbent, prune it.
- Otherwise branch again.
The crucial lesson is that pruning is not a guess. It is justified by a bound.
6. A Strong Relaxation Can Matter More Than a Clever Search Order
If the LP relaxation is extremely loose, many nodes look artificially promising and the tree grows. If the relaxation closely approximates the convex hull of feasible integer solutions, large parts of the tree can be ruled out early.
This is why formulation quality matters. Two mathematically equivalent integer models can lead to dramatically different search behaviour because their relaxations differ in strength.
7. Cutting Planes Remove Fractional Regions Without Removing Valid Integer Solutions
A valid inequality is a constraint satisfied by every legitimate integer solution. If it also excludes the current fractional relaxation point, it acts as a cut. The relaxation becomes tighter without changing the true integer feasible set.
Professional solvers maintain families of separators that search for useful cuts. SCIP’s current documentation describes separators, relaxators, branching, propagation and other components within a branch-cut-and-price framework: SCIP documentation.
8. Branch-and-Cut Combines Two Different Kinds of Progress
Branching shrinks the feasible region by committing to alternatives. Cutting planes shrink the relaxation while keeping all valid integer solutions. Modern MIP algorithms interleave both.
The learning goal is not to memorise a list of cut families. It is to understand why the solver keeps improving the representation of the same discrete problem while also decomposing it into smaller regions.
9. Presolve Tries to Solve Easy Consequences Before the Main Search Begins
Presolve can remove fixed variables, tighten bounds, detect redundant constraints, substitute variables and infer infeasibility. These transformations may dramatically reduce the problem before branch-and-bound starts.
This is a valuable general algorithmic habit: simplify structure before spending computation on the full problem.
10. Propagation Pushes Local Consequences Through the Model
Suppose a binary variable must be 1 because all alternatives would violate a capacity constraint. That decision can tighten other domains, which can trigger more deductions. Propagation uses constraints to reduce possibilities without enumerating them.
The neighbouring How to Learn Constraint Programming article owns domain propagation as a general constraint-programming idea. Here propagation is taught as one component inside modern integer optimisation.
11. Primal Heuristics Search for Good Feasible Solutions Early
A strong incumbent makes pruning easier. Solvers therefore use heuristics to turn fractional or partial information into feasible integer solutions. Rounding, local improvement, diving and neighbourhood search can all contribute.
Heuristics and proof are different jobs. A heuristic may quickly find an excellent solution without proving optimality. Branch-and-bound machinery supplies the proof side.
12. Node Selection Changes When Evidence Arrives
Depth-first search may find feasible solutions quickly and use little memory. Best-bound search may improve the global bound efficiently. Hybrid strategies try to obtain useful incumbents and useful proofs at the same time.
The lesson is subtle: search order can change runtime enormously without changing the mathematical answer.
13. Branching Variable Choice Is an Information Decision
Not every fractional variable is equally useful to branch on. A strong branching decision should split the remaining search into children whose bounds improve meaningfully. Modern solvers estimate this through pseudocosts, historical behaviour and more expensive trial solves.
This turns branching from “pick any fractional variable” into a prediction problem about how much uncertainty each split is likely to remove.
14. Symmetry Can Make the Solver Prove the Same Thing Many Times
If five identical machines can be permuted without changing the solution, a model may contain many equivalent branches. Symmetry-breaking constraints or specialised solver machinery can remove redundant representations.
For learners, this is an important distinction between the number of real decisions and the number of symbolic descriptions of those decisions.
15. The MIP Gap Is a Statement About What Remains Unknown
Solvers often stop before proving exact optimality. They report the incumbent and a best bound. The gap between them summarises how much improvement could still exist.
A 0% gap means optimality has been established under the solver’s numerical tolerances. A small nonzero gap may be operationally sufficient. A professional must understand the absolute and relative gap definitions used by the software rather than treating the percentage as a generic confidence score.
16. Time Limits Turn Exact Optimisation Into Anytime Optimisation
In real operations, a solver may have five seconds, five minutes or five hours. A useful MIP algorithm can often return the best incumbent found so far together with a bound when time expires.
Google’s current MPSolver interface exposes time limits and multiple LP/MIP back ends. The professional question becomes not only “What is optimal?” but also “What quality guarantee can we obtain before the decision deadline?”
17. Numerical Tolerances Matter Because Computers Do Not Solve Over Exact Real Numbers
A computed value such as 0.999999999 may need to be treated as 1 within an integrality tolerance. Constraint feasibility also depends on tolerances. Poor scaling can produce unreliable decisions about feasibility or bounds.
This connects directly to numerical analysis: the combinatorial logic may be correct while the finite-precision representation creates practical difficulties.
18. Big-M Constraints Can Be Correct and Still Be Terrible
Big-M formulations encode conditional logic with a large constant. If M is unnecessarily huge, the relaxation becomes weak and numerical conditioning can worsen. If M is too small, the model may exclude legitimate solutions.
The professional habit is to derive the tightest justified bound—or use indicator constraints or alternative formulations when the solver supports them.
19. Formulation Is Often More Important Than Solver Knobs
Adding variables can sometimes make a model solve faster if the new formulation creates a much stronger relaxation. Conversely, a tiny model can be difficult if its constraints convey little structure.
Google’s newer MathOpt separates model construction from solver choice. That separation is pedagogically useful: first express the mathematical object correctly; then evaluate solution machinery.
20. MIP, CP-SAT and Constraint Programming Are Neighbours, Not Synonyms
Some scheduling and Boolean-heavy models perform better with constraint or SAT-based methods than with a conventional LP-based MIP solver. OR-Tools explicitly notes that there is no universal rule: MIP is often natural for models close to LP with integer restrictions, while CP-SAT can be attractive for predominantly Boolean/integer combinatorial structure.
The professional skill is method selection, not loyalty to one solver family.
21. Complexity Theory Explains Why Search Cannot Usually Be Magicked Away
Many integer optimisation problems are NP-hard. That does not mean real instances are hopeless. It means we should not expect a known polynomial-time algorithm that solves every instance exactly.
The existing How to Learn NP-Completeness and Reductions article owns the complexity-theory job. Here the practical question is how relaxations, cuts, structure and heuristics make important instances tractable despite worst-case hardness.
22. Common Learning Failure States
- Treating integer variables as merely rounded continuous variables.
- Accepting the LP relaxation as though it were the original problem.
- Confusing a good feasible solution with a proof of optimality.
- Thinking branch-and-bound is just brute force with a tree diagram.
- Adding huge Big-M constants without deriving valid bounds.
- Reading a MIP gap as a probability of correctness.
- Changing solver parameters before checking formulation strength.
- Ignoring numerical scaling and feasibility tolerances.
- Comparing solver runtime without checking objective quality and bound quality.
23. A Beginner-to-Professional Learning Ladder
- Level 1: mark integer and fractional points on a two-variable feasible region.
- Level 2: solve the LP relaxation and explain why its optimum may be illegal.
- Level 3: perform one manual branch on a fractional variable.
- Level 4: calculate node bounds and prune a tiny branch-and-bound tree.
- Level 5: add a valid inequality that removes a fractional point.
- Level 6: compare two equivalent formulations by relaxation strength.
- Level 7: implement a small MIP with OR-Tools or SCIP and inspect incumbent, bound and gap.
- Level 8: diagnose symmetry, weak Big-M constraints and scaling.
- Level 9: compare MIP with CP-SAT or a specialised network-flow formulation.
- Level 10: justify stopping criteria, formulation choice and solver evidence for a real decision deadline.
24. Teach the Search Tree as an Evidence Tree
For beginners, make each node visible. Write the added branch constraint, relaxation value, incumbent and pruning reason beside it. Ask learners to predict whether the node should survive before showing the solver’s action.
This follows a strong programming-education progression: predict and trace before writing from scratch. PRIMM’s Predict–Run–Investigate–Modify–Make structure supports that movement from reading behaviour to constructing solutions. See the Raspberry Pi Foundation PRIMM course and the research on teachers’ use of PRIMM.
25. Scaffold Implementation Without Removing the Reasoning
Learners who understand the tree concept may still struggle to write solver code or a toy branch-and-bound implementation. Adaptive Parsons problems can reduce syntax burden while preserving sequencing and reasoning; see Hou, Ericson and Wang, ICER 2022. Worked examples should then fade so the learner increasingly chooses the formulation, branch and bound independently.
26. Immediate, Delayed and Transfer Checks
- Immediate: explain why a fractional relaxation is still useful.
- Trace: label each node in a small branch-and-bound tree with its pruning reason.
- Model: convert a verbal yes/no decision into a binary variable and linear constraints.
- Delayed: reconstruct the branch-and-bound logic from memory without notes.
- Transfer: choose among MIP, CP-SAT and a specialised polynomial-time algorithm for three different problems.
- Professional: report incumbent, best bound, gap, runtime, numerical warnings and modelling assumptions together.
Spacing and retrieval matter here because solver terminology is easy to recognise and harder to reconstruct independently. The ICER study A Spaced, Interleaved Retrieval Practice Tool provides useful evidence for designing that practice.
27. AI Assistance Boundary
AI can help translate a verbal problem into candidate variables and constraints, generate toy instances, explain solver logs and compare formulations. The learner should still be able to identify whether the model matches the real decision, derive valid bounds, recognise weak formulations, interpret the MIP gap and independently test whether the returned solution satisfies the original constraints.
Professional Direction
Advanced study includes polyhedral theory, lift-and-project methods, Gomory and mixed-integer cuts, branch-and-price, Benders decomposition, column generation, decomposition for stochastic and robust optimisation, primal heuristics, symmetry handling, conflict analysis, learning-guided branching, exact rational verification and parallel MIP. Modern SCIP documentation is especially useful because it exposes these components as parts of one solver framework.
Algorithm-learning rule: do not ask only whether the solver found a good integer answer. Ask what relaxation bounded the unseen possibilities, what evidence justified pruning, how large the remaining gap is, and whether the mathematical model still represents the real decision.
eduKate Sengkang 