The Core Aim of Mathematics Mastery

Did you know that the “best” answer to a mathematics problem can be impossible to carry out in real life? A factory cannot usually deliver 2.3 buses, a school cannot employ 4.7 teachers, and a courier cannot assign half a delivery van to a route. When decisions come in whole units, ordinary optimisation needs another layer of reasoning.

The core aim of integer programming mastery is to solve optimisation problems in which some or all decision variables must be whole numbers. Students learn to distinguish continuous and integer solutions, write objective functions and constraints, test feasible combinations, understand why rounding is unsafe, and recognise how branch-and-bound methods search efficiently for the best admissible answer. Integer programming is not simply linear programming with a rounding step. It is the mathematics of decisions that cannot be divided.

This guide extends eduKateSG’s Linear Programming, Inequalities, Simultaneous Equations and Mathematical Modelling. For the larger optimisation framework, see How Mathematical Optimisation Works. Here the distinct learning objective is to make whole-number constraints mathematically explicit and solve them reliably.

Integer Programming Begins With a Practical Restriction

In ordinary linear programming, variables are usually allowed to take any real values satisfying the constraints. Integer programming restricts selected variables to integers, often non-negative integers.

A decision variable might represent the number of workers assigned to a shift, vehicles purchased or classrooms opened. Such a choice cannot automatically take fractional values. The mathematics must preserve that meaning.

Pure Integer, Mixed-Integer and Binary Models

Pure integer programming: all decision variables are integers.
Mixed-integer programming: some variables are integers while others remain continuous.
Binary programming: variables can only be 0 or 1, representing choices such as no/yes or off/on.

When the objective and constraints are linear, the common terms include integer linear programming (ILP) and mixed-integer linear programming (MILP).

Binary Variables Turn Logical Decisions Into Mathematics

Suppose a school is deciding whether to open an additional class. Define z=1 if it opens and z=0 if it does not. If opening requires at least one teacher and incurs a fixed setup cost, a binary variable can connect that yes/no choice to staffing and budget constraints.

Binary variables are useful for assignments, scheduling, location choice and “either/or” planning. The important lesson is to model the logic clearly before sending an equation to an optimiser.

The Objective Still Describes What We Want to Optimise

Integer programming can maximise profit, minimise cost, reduce distance or optimise another clearly defined quantity.

The objective remains separate from constraints. A plan can look attractive under the objective but be disallowed by insufficient staff, budget, equipment or integer restrictions.

Worked Example: Two Whole-Number Products

A workshop produces two kinds of kits. Let x and y be the whole-number quantities produced. Each X kit contributes 5 units of value, and each Y kit contributes 4.

The workshop wants to maximise:

P=5x+4y.

Two resources impose the limits:

2x+y≤7;
x+2y≤7;
x,y≥0 and both integers.

Notice the final condition. It changes the problem from a continuous linear programme into an integer programme.

First Solve the Continuous Relaxation

The linear programming relaxation ignores integrality temporarily. The boundary equations are:

2x+y=7 and x+2y=7.

Subtracting gives x=y. Substitution gives x=y=7/3.

The objective there is P=5(7/3)+4(7/3)=21. The other continuous feasible vertices give lower values, so the relaxation optimum is 21.

But 7/3 kits of each type cannot be produced. The relaxed solution gives an upper bound for the integer maximum, not a feasible production plan.

Why Rounding the Continuous Answer Is Not a Solution

Rounding both 7/3 values down to 2 gives (2,2), worth 18. Rounding both up to 3 gives (3,3), which violates both constraints: 2(3)+3=9>7 and 3+2(3)=9>7.

Neither rounding choice proves optimality. The best integer solution could be a different feasible combination that does not result from rounding either variable independently.

Worked Example: Find the Best Integer Solution

The first resource constraint gives x≤3 because x is a non-negative integer and 2x≤7. We can test the best allowed y for each x:

x	Largest feasible integer y	P=5x+4y
0	3	12
1	3	17
2	2	18
3	1	19

The best integer solution is (x,y)=(3,1), with objective value 19. It satisfies the constraints: 2(3)+1=7 and 3+2(1)=5≤7.

This example teaches three separate numbers: continuous upper bound 21, rounded-down candidate 18, and true integer optimum 19. They must not be confused.

Feasible Does Not Mean Optimal

Many integer pairs satisfy the resource limits. For example, (2,2) is valid. But validity only tells us a plan is allowed; it does not tell us it is the best allowed plan.

A complete solution needs both: demonstrate feasibility and show no better feasible integer choice exists.

Linear Relaxation Gives Useful Bounds

In a maximisation problem, dropping integer restrictions cannot make the optimum worse. So the relaxed optimum is an upper bound on the integer optimum.

In our example, 21 is the relaxation bound. Once a feasible integer solution worth 19 is found, we know the true optimum lies between 19 and 21 until the remaining possibilities have been ruled out.

Branch-and-Bound Avoids Testing Every Combination

For a small problem, a table can enumerate feasible integer choices. For a large one, that becomes impractical. Branch-and-bound creates smaller subproblems and uses bounds to eliminate regions that cannot beat the best current feasible solution.

If the relaxed solution has fractional x=7/3, one possible branch splits the search into:

x≤2;
x≥3.

Every integer value of x lies in one branch or the other. Solving relaxations within each branch supplies bounds that help decide where further search is worthwhile.

An Incumbent Is the Best Feasible Integer Solution So Far

In branch-and-bound, the best known feasible integer solution is called the incumbent. Any branch whose best possible bound cannot improve the incumbent can be pruned.

For example, if a maximisation branch has a proven upper bound of 17 and we already have a feasible solution worth 19, there is no reason to search that branch further.

Why the Search Can Still Be Difficult

With many binary variables, the number of possible assignments can grow as 2ⁿ. With 30 yes/no decisions, there are over a billion possible combinations before accounting for constraints.

Good optimisation methods exploit structure, bounds and problem-specific relationships instead of testing every assignment one by one.

Logical Conditions Can Be Written as Constraints

Suppose x and y are binary variables indicating whether two facilities are selected. If they cannot both be selected, write x+y≤1.

If at least one must be selected, write x+y≥1. If exactly one must be selected, write x+y=1.

These relationships turn plain-language conditions into checkable mathematics.

Scheduling Is a Natural Integer Programming Problem

Suppose each worker can cover certain shifts. A binary variable xᵢⱼ may indicate whether worker i is assigned to shift j.

Constraints can enforce shift coverage, availability, maximum working hours and rest conditions. An objective can minimise staffing cost or imbalance. The integer restrictions ensure that an individual worker is assigned or not assigned, rather than fractionally allocated under an incompatible model.

Integer Programming Connects With Graph Theory

Routing, matching and facility-location problems can be modelled through integer variables and graph connections. Some special network-flow and matching formulations have structure that permits integral optimal solutions using continuous linear programming. Others require explicit integer decisions.

This is a useful bridge to Graph Theory.

Integer Programming and Mathematical Modelling

A model can be mathematically correct yet practically unhelpful if it omits setup costs, dependencies, time windows or meaningful whole-number restrictions.

Mastery therefore includes choosing variables that correspond to real decisions, checking whether constraints reflect actual limits and asking whether the objective measures the outcome the decision-maker truly values.

Common Integer Programming Mistakes

Rounding a continuous solution without checking feasibility or optimality.
Forgetting which variables must be integers.
Using a binary variable when a non-negative integer count is required.
Omitting linking constraints between yes/no choices and quantities.
Reporting a relaxed bound as a feasible solution.
Confusing a feasible incumbent with a proven optimum.
Ignoring practical meaning when interpreting an algorithm’s result.

Three Learning Pathways

Repair: Variables and Inequalities

Begin with non-negative integer quantities, at-most and at-least conditions, and simple resource tables. Make the student say why a fractional value is or is not meaningful.

Stabilise: Relaxation and Complete Checks

Solve a two-variable continuous relaxation, list feasible integer points, compare objective values, and explain why a rounded point cannot prove the answer. Distinguish feasibility, bounds and optimality in writing.

Extend: Branch-and-Bound and Model Design

Introduce binary logical constraints, branch-and-bound, integer scheduling and network design. Compare a mathematically valid model with a real operating decision, identifying assumptions that matter.

A Weekly Integer Programming Practice Routine

Translate one everyday decision into integer variables.
Write an objective and two resource constraints.
Solve the continuous relaxation.
Check a rounded candidate for feasibility.
Find and justify the best feasible integer choice.
Explain what changes when one resource limit increases.

Student Progress Checklist

I understand the difference between continuous and integer decision variables.
I can identify pure, mixed-integer and binary models.
I can write objectives and constraints.
I understand feasibility.
I can solve a small integer problem systematically.
I know why rounding may fail.
I understand a relaxation bound.
I can explain branch-and-bound conceptually.
I distinguish an incumbent from a proven optimum.
I can interpret the chosen integer solution in context.

Frequently Asked Questions

What is integer programming in simple terms?

It is mathematical optimisation in which some or all choices are restricted to whole numbers.

Why can’t I just round a linear programming answer?

Rounding may violate constraints or miss the best allowed whole-number choice. Feasibility and optimality must both be checked.

What is a binary decision variable?

It is a variable restricted to 0 or 1, often representing whether an option is selected.

What is branch-and-bound?

It is a search strategy that divides a problem into subproblems and uses mathematical bounds to reject branches that cannot improve the best feasible solution found so far.

Helpful Reading in the eduKateSG Ecosystem

The Core Aim

The core aim of integer programming mastery is not to force students to count every possible combination. It is to make whole-number decisions mathematically defensible.

A strong learner can formulate integer restrictions, understand a continuous relaxation, find feasible candidates and distinguish a good answer from a proven optimum. That is the difference between calculating a number and planning a decision that could actually be carried out.

The Core Aim of Mathematics Mastery | Integer Programming