In linear programming, variables can take any real value. For many problems that is perfectly fine: litres of fuel, hours of work, kilograms of feed. But you cannot buy 2.7 lorries, open half a warehouse or assign a shift to a third of a person. When some variables must be integers we enter the world of integer linear programming (ILP), far more expressive and far harder.
Why rounding is not enough
The temptation is to solve the linear problem and round. It sometimes works, but it can give infeasible solutions or ones far from the optimum. An example:
maximise x + y
-2x + 2y ≥ 1
-8x + 10y ≤ 13
x, y ≥ 0, integer
The continuous optimum is x = 4, y = 4.5, with value 8.5. Rounding y to 4 or to 5 violates a constraint in both cases. The integer optimum is x = 1, y = 2, with value 3: very far from the continuous point. In real problems, with hundreds of variables, rounding is even less reliable.
The power of binary variables
The real power of ILP lies in binary variables, which are 0 or 1 and represent yes/no decisions. With them you can model situations LP cannot express:
- fixed costs: if warehouse j is opened (y_j = 1) a fixed cost is paid, and only then can goods be shipped there: x_ij ≤ capacity_j · y_j;
- exclusive choices: at most one of projects A and B: y_A + y_B ≤ 1;
- implications: if A is done, B must be done too: y_A ≤ y_B;
- alternative constraints: satisfying at least one of two constraints, using the «big M» technique that switches a constraint off when a binary variable is 0.
Shift assignment, facility location, timetabling, production planning with minimum batch sizes, investment selection: almost every business decision problem can be written as an ILP.
The linear relaxation
Given an integer problem, its linear relaxation is the same problem without the integrality constraints. Two properties make it very useful:
- in a maximisation problem, the value of the relaxation is an upper bound on the integer optimum, because it removes constraints;
- if the solution of the relaxation is already integer, it is also the integer optimum.
The relaxation is solved quickly with the simplex method, and it is the engine of the most widely used method for ILP.
Branch and bound
Branch and bound explores the tree of possibilities intelligently.
- Solve the linear relaxation. If the solution is integer, you are done.
- Branch: choose a fractional variable, for example x = 2.6, and create two subproblems: one with x ≤ 2, the other with x ≥ 3. No integer solution is lost, because every integer satisfies one of the two constraints.
- Solve the relaxation of each subproblem.
- Bound: keep track of the best integer solution found so far, called the incumbent. If the relaxation of a subproblem gives a value no better than the incumbent, that branch cannot contain anything better and is discarded without being explored.
- Also discard infeasible subproblems, and continue while open nodes remain.
The pruning in step 4 is what makes the method practical: instead of examining every combination, whole branches are discarded thanks to the bounds.
The optimality gap
During the search two numbers are known: the value of the incumbent (a real solution) and the best bound among the nodes still open. The relative difference between them is the optimality gap.
| Moment | Incumbent | Best bound | Gap |
|---|---|---|---|
| After 1 minute | 9,200 | 10,100 | about 9% |
| After 10 minutes | 9,750 | 9,900 | about 1.5% |
| At the end | 9,810 | 9,810 | 0% |
In practice it is normal to stop when the gap falls below an acceptable threshold, for example 1%: you have a solution with a guarantee of quality, something pure heuristics do not offer.
Cuts and strong formulations
Two correct models of the same problem can behave very differently. What matters is how close the linear relaxation is to the integer optimum: the tighter it is, the more branch and bound prunes.
- Cutting planes are extra constraints satisfied by all integer solutions but violated by the current fractional solution. Gomory cuts are the classic example; modern solvers generate many kinds automatically. Combining cuts and branching is called branch and cut.
- Strong formulations avoid huge «big M» constants, which make the relaxation weak: it pays to choose the smallest value that does not cut off valid solutions.
- Symmetries slow things down a lot: if ten identical lorries are interchangeable, the solver explores the same solution ten times under different names. Adding constraints that impose an order among identical items helps.
Practical tips
- Start from a small, correct model, then add the details.
- Give the solver a good initial solution, perhaps from a heuristic: a good incumbent from the start increases pruning.
- Set a realistic time limit and gap threshold.
- If the model is too slow, try strengthening the formulation before changing solver.
In short
- ILP adds integer and binary variables, essential for yes/no decisions and fixed costs.
- Rounding the linear solution can give infeasible or very poor results.
- Branch and bound splits the problem on fractional variables and discards hopeless branches.
- The gap between the solution found and the best bound measures its guaranteed quality.
- Cuts, strong formulations and symmetry removal often matter more than the solver.
