1
Use a relaxation as a bound and refuse it as an answer
Solve the relaxation, test every rounding of its optimum for feasibility, find the integer optimum by enumeration on a small instance, and state the bound relation between the three numbers.
Course · Operations Research
Integer Programming
Algebra’s “Systems of Inequalities and Linear Programming” closes by saying that rounding an optimal corner is not guaranteed to give the best whole-number answer — and that this is a different subject. This is the subject. Binary variables turn logic into inequalities; a big-M links a fixed cost to a decision and charges you for being careless about its size; and because integer problems are hard in the precise sense Discrete Mathematics gave the word, the tools that remain are bounds — from a relaxation, from a cut, from a search tree — and the certificate you finish with is a gap of zero, or an honest number.
relaxation: drop integrality ⟹ z_LP ≥ z_IP (max) a bound, not an answer
at most k Σy ≤ k if A then B y_A ≤ y_B
A or B y_A + y_B ≥ 1 exactly one Σy = 1
fixed charge x ≤ M y M as small as validity allows
either–or A + M(1 − y), B + M y one binary chooses
branch on x = v fractional: x ≤ ⌊v⌋ or x ≥ ⌈v⌉; re-solve by dual simplex
gap = bound − incumbent; the gap is what is proved
What this course is about
- Subject
- Operations Research
- Lessons
- 9
- Format
- Interactive
Overview
What you will be able to do
By the end you can say why the integer answer is not near the fractional one, encode a logical condition as an inequality and prove the encoding right, size a big-M and price the choice, run a search tree by hand and prune for the right reason, derive a cut from a tableau row, and report a result with a gap attached.
2
Encode a logical condition and prove the encoding
At-most-k, if-then, either-or, exactly-one and fixed-charge conditions as linear inequalities on binaries — each verified against the condition's truth table, assignment by assignment, with the row that would refute a wrong encoding named.
3
Build the two atoms and read their relaxations
A knapsack and a set-covering model from data; the single fractional item in one relaxation and the spread halves in the other; and why each relaxation's value is a bound.
4
Size a big-M and pay for it
The tightest valid M for a fixed-charge link, and the measured cost of a looser one — a weaker bound and more nodes for the same answer.
5
Run branch-and-bound and report a gap
The tree by hand with each node's bound and status, pruning for one of the three right reasons, and an incumbent and a global bound reported together at every stage.
6
Cut, and solve a hard problem exactly
A Gomory cut derived from a fractional tableau row and verified to remove no lattice point; and a six-city travelling salesman solved by relaxation, subtour cuts and branching, with a heuristic tour measured against the bound.
Lessons
9 lessons
The failure first, because a reader who has not seen rounding fail will keep reaching for it; then modelling — logic, the two atoms, the fixed charge, the disjunction — because an integer programme is mostly a modelling problem; and then the three tools, in the order that makes each one the answer to the previous one's weakness: branch, measure the gap, cut it.
When Rounding FailsSolve the relaxation, test every rounding of its optimum, and find the whole-number optimum by enumeration.Not marked
Binary Variables and Logical ConstraintsTurn five stated conditions into inequalities on binaries and verify each against its truth table.Not marked
Knapsack and Set CoveringBuild both atoms from data, solve both relaxations, and say what each one made fractional.Not marked
Fixed Charges, Facility Location and Big-MLink a fixed cost to a decision, size the constant that does the linking, and measure what a loose one costs.Not marked
Either–Or ConstraintsWrite a disjunction as two relaxed rows switched by one binary, and verify both branches by re-solving.Not marked
Branch and BoundSplit on a fractional variable, bound each child, and close a node for one of exactly three reasons.Not marked
Incumbents, Bounds and the GapProduce a plan and a bound, compute the gap, and say exactly what has been proved after each node.Not marked
Cutting Planes and Gomory CutsDerive a cut from a fractional tableau row, test it on every lattice point, and re-solve by the dual simplex.Not marked
The Travelling Salesman ProblemBound a tour by the assignment problem, cut the subtours it leaves, branch, and measure a heuristic against the result.Not marked
Recommended background
Linear programming models, the simplex method, duality and sensitivity analysis — the dual simplex in particular — and network optimisation, for total unimodularity as the contrast case and the assignment problem as a relaxation; from discrete mathematics, logical connectives, truth tables, the complexity classes, greedy algorithms, euler and hamilton paths, permutations, and functions, which is where the floor and ceiling of a rational are defined and the cutting-plane lesson needs them; and from algebra, interval and set-builder notation.
Practice suggestions
Prove every encoding before using it. The lab of “Binary Variables and Logical Constraints” evaluates your inequality on all 2ⁿ assignments against the condition’s truth table, and a wrong encoding is refuted by a row rather than by an argument. Get into the habit there and keep it in the fixed-charge and either-or lessons, where the same check is harder to run.
Solve the relaxation first, always, and look at what is fractional. A single split item, a pair of halves, a y at 1/20 — each of those tells you which constraint is doing the work and often which branching variable to pick.
Make M as small as validity allows, and say why your value is valid. “The facility’s capacity” and “total demand, whichever is smaller” are reasons; “a million” is not, and the lab of “Fixed Charges, Facility Location and Big-M” prices the difference on your own instance.
Report a gap rather than an answer whenever the tree has not closed. A result with a stated gap is a proof; a result without one is a hope, and the difference is what this course is for.
What it does not cover
Branch-and-cut as solvers implement it. Cut management, node presolve, pseudo-cost branching and restarts are engineering on top of the last four lessons, and naming them is as far as this course goes.
Lagrangian relaxation and column generation. Both produce bounds by a different route and both need machinery — subgradients, pricing subproblems — this path does not have.
Constraint programming. A different formalism with different propagation, and a genuinely different subject rather than a variant of this one.
Nonlinear integer problems of any kind, including anything quadratic.
The results this course cites and does not prove. The pseudo-polynomial dynamic programme for 0/1 knapsack, the knapsack approximation scheme, the ln n ratio for greedy set cover, Held–Karp for the travelling salesman, the metric two-approximation, and the hardness reductions — all six belong to the Algorithms path, in “Dynamic Programming and Optimal Substructure” and “Intractability and Approximation”. Each is stated in the lesson where it is needed, with its owner named.
The exponential worst case, restated. The search tree and its worst case are the Algorithms path’s “Backtracking and Branch-and-Bound”; the search lessons here cite it and add what is this course’s own — that the bound is a linear programme and the child is re-solved from the parent tableau.