Motivation
A communication system can allocate fractional transmission time, but it cannot install half of an indivisible relay. A compiler can choose whether to enable a particular transformation, while the amount of processor time assigned to an enabled task might remain continuous. Integer programming records these discrete choices explicitly. Removing integrality can make a problem easier, but it changes what counts as a feasible decision.
The linear relaxation is still useful. For a maximization problem, allowing extra fractional points can only raise the best attainable objective. Its optimum supplies an upper bound against which actual integer decisions can be compared. This is a logical statement about nested feasible sets, independent of any solver. Confusing a relaxed answer with a realizable answer loses precisely the feature the integer model was introduced to preserve.
The main difficulty is proving that no better discrete decision was missed. Branch and bound divides the candidate decisions into exhaustive cases and uses valid upper bounds to discard whole cases. A valid inequality attacks the same difficulty differently: it removes fractional points while preserving every integer decision. Finally, integrality theory identifies special constraint structures where fractional vertices never appear, so the linear relaxation already solves the integer problem.
Definitions
Definition 3.1.1
(Integer model, relaxation, incumbent, and bound)
An integer linear maximization problem has the form
A binary variable is further restricted to . A mixed-integer model requires integrality only for a specified subset of variables. The linear relaxation replaces the integer restrictions by real-valued restrictions, keeping all other constraints.
An incumbent is an actually feasible integer point found so far. Its objective is a lower bound on the maximum. A valid upper bound is a number at least as large as every feasible integer objective in the relevant search region.
The integer hull is the convex hull of all integer feasible points. A linear inequality is valid if it holds for every such point. Adding a valid inequality may tighten the relaxation without changing the original integer optimization problem. A cut intended to remove a fractional point must therefore be proved valid before it is used.
Concept lensGeometric
An integer program is a linear program over its integer hull
Let the integer feasible set be finite and nonempty, with integer hull and relaxation polyhedron . Then is a polytope whose vertices lie in , and a linear objective attains its maximum over at a vertex, so . Since , the relaxation bound can only be larger. Valid inequalities are exactly the linear inequalities that hold on , each cut moves toward , and the integrality theorems below describe bounded cases with .
Modeling is part of the mathematics. If indicates whether a task is enabled and is its continuous workload, a known bound gives the implication , with binary. This ensures that disabling the task forces zero workload. It does not force positive workload when enabled. The constant must be a valid bound derived from the model; an arbitrary small value removes legitimate decisions, while an unnecessarily large value weakens the relaxation.
For integrality theory, an integer matrix is totally unimodular if every square submatrix has determinant zero, one, or minus one. This property concerns all square minors, not merely the determinant of the whole matrix. A polyhedron is integral when it equals the convex hull of its integer points; for the bounded nonempty polyhedra considered below, it suffices that every vertex is integer.
Theorem/proposition
Proposition 3.1.2
(Relaxation bounds justify pruning)
At a maximization search node, let its linear relaxation have a certified finite upper bound . If an incumbent has value and , no integer point in that node can improve the incumbent. An infeasible relaxation contains no feasible integer point. If an optimal relaxed solution is itself integer, it solves that node's integer problem.
For finding one optimum, equality of bound and incumbent permits pruning. If the task is to enumerate every optimum, a node with equal bound can contain additional optimal points and must be handled accordingly. The bound is on objective value, not on distance between decision vectors.
Theorem 3.1.3
(Unimodularity turns basic solutions into integers)
Let be an integer totally unimodular matrix of full row rank, and let be an integer vector. Every basic feasible solution of , is integer. Consequently, if that standard-form problem has an attained finite linear optimum, it has an integer optimal solution.
Both the matrix property and integer right-hand side matter. Integer coefficients alone do not imply integrality. The theorem does not say every feasible or every optimal point is integer: convex combinations of integer vertices can still be fractional.
Theorem 3.1.4
(Directed incidence matrices are totally unimodular)
The node–arc incidence matrix of a directed graph, with at each arc's tail and at its head, is totally unimodular. Appending unit rows or unit columns preserves total unimodularity.
Proof sketch or proof idea
Proof
(Nested feasible sets and exhaustive branching)
At any node, its integer feasible set is contained in its relaxed feasible set. Thus every integer objective is at most the relaxed optimum and therefore at most a certified upper bound on that optimum. If this bound does not exceed an already attained integer value, no improvement can come from that node. If the relaxation is infeasible, its subset is empty. If a relaxed optimizer is integer, it belongs to the subset and attains the upper bound, proving equality of the two optima.
Suppose a relaxed optimizer has a fractional integer-designated coordinate . Every integer value of that coordinate satisfies exactly one of
The two child regions therefore cover every integer point in the parent and exclude its current fractional optimizer. This is the branching disjunction. A search certificate consists of this exhaustive division together with a valid reason for closing each leaf: infeasibility, an adequate objective bound, or an integer relaxed optimum. Merely showing the best point found is not such a certificate.
If all integer-designated variables have finite integer bounds, repeated branching terminates when implemented without revisiting identical nodes. Each root-to-leaf branch strictly shortens at least one integer coordinate interval; its length is bounded by the sum of the original interval widths. A finite branching tree of bounded depth is finite. Unbounded integer domains require additional arguments; this proof makes no universal finite-termination claim for them.
Proof
(Integer inverses of unimodular bases)
For the unimodularity theorem, let be any nonsingular basis matrix. Its determinant is a nonzero square minor of , so it is one or minus one. The adjugate formula shows that is integer, since its entries are integer cofactors divided by that determinant. Hence is integer, and all nonbasic coordinates are zero. The linear-programming basic-representative theorem now supplies an integer optimum whenever the linear optimum is attained.
Why network matrices have this property
Proof
(Induction on the size of a minor)
Give a directed graph an incidence matrix with minus one at an arc's tail and plus one at its head. For an arc with distinct endpoints, its column has exactly two opposite nonzero entries; a self-loop has the zero column because its tail and head contributions cancel. Consider any square submatrix. If a column has no nonzero entry its determinant is zero. If a column has exactly one nonzero entry, expansion along that column reduces its determinant, up to sign, to a smaller square minor. If every column has two nonzero entries, its column sums are zero, so the rows are dependent and its determinant is zero. Induction proves total unimodularity.
Proof X-ray
Where the opposite signs are used
The induction has three cases, and only the last one uses the structure of the graph. A zero column and a column with a single nonzero entry are handled for any matrix with entries in : the first gives determinant zero, the second reduces to a smaller minor by expansion. The decisive case is a square submatrix in which every column keeps both of its entries. There the opposite signs and make every column sum zero, so the all-ones row combination vanishes and the determinant is zero.
That is exactly the step that fails without orientation. The undirected incidence matrix of a triangle has every column with two entries , and its determinant is . The proof also never uses the size of the graph or connectivity, which is why deleting rows and appending unit rows or columns can be handled by the same expansion.
Deleting a redundant incidence row preserves the property. Adding unit columns or unit rows also preserves it, by the same determinant expansion. Thus a capacitated flow system can be written with integer right-hand side and a totally unimodular standard-form matrix: conservation uses incidence rows, and capacity equations add one unit slack column and one unit-variable row pattern. More explicitly, the equality matrix on variables is
Expanding a minor along slack columns first, and then along surviving capacity rows containing a single original-variable entry, reduces it to an incidence minor. Redundant equalities may be removed to obtain full row rank. Integer supplies and capacities therefore give integer vertices. This explains why a minimum-cost feasible flow can have an integer optimum even though it is solved as a linear program. Arbitrary additional coupling constraints need not preserve the argument.
Worked examples
Worked example 3.1.5
(A small branch-and-bound tree with a complete certificate)
Choose binary task switches to maximize subject to . The relaxed region has . Its optimum is , with value four: allocating to the larger coefficient first gives , then the remaining half unit of total allowance goes to .
Branch on . At , the relaxed optimum is , giving integer incumbent value three. At , the constraint gives , so the relaxed upper bound is .
All integer feasible objectives are integers because both objective coefficients and variables are integers. Therefore the second node has integer upper bound . It cannot improve the incumbent and is pruned. The two children cover both possible values of ; both have justified outcomes. Thus is globally optimal with value three.
Without the integer-objective argument, the raw bound would not justify pruning against three. One would need another branch or a stronger certificate. A rounding step in the bound must have its own hypothesis.
Worked example 3.1.6
(Rounding a relaxed solution loses the optimum)
Consider binary choices satisfying
The relaxation fills variables in decreasing objective-per-capacity ratio: , , then . It gives , with value . This is also certified by multiplier on capacity and multiplier on the upper bound of : these inequalities combine to bound the objective by .
Rounding down produces , with value seven. But is feasible with value eight. To certify the integer optimum, observe that if , neither other item fits, giving at most seven; if , both remaining items fit and give at most eight. These exhaustive cases prove eight is optimal.
The set of items is a cover: their total capacity usage seven exceeds five. Hence the valid cover inequality holds for every binary feasible point. The relaxed optimizer violates it, since its left side is . This cuts away that point without deleting any integer decision. One cover inequality need not describe the entire integer hull.
Worked example 3.1.7
(Recognizing and breaking structural integrality)
An integer-capacity network with integral supplies has integer flow vertices by the incidence argument. For a one-arc flow with supply one at its tail and demand one at its head, the unique feasible value is one, provided the capacity is at least one.
Now consider the unrelated scalar constraint , , with objective maximize . Its matrix has a one-by-one minor equal to two and is not totally unimodular. The relaxed vertex is , whereas the integer optimum is zero. Integer data did not prevent a fractional vertex.
Even a totally unimodular matrix needs an integer right-hand side: , uses coefficient one but again has fractional relaxed optimum. Conversely, failure of total unimodularity does not prove that a particular right-hand side produces a gap. For , the optimum of maximizing is one in both models. The theorem gives a sufficient structural guarantee, not a necessary test for every individual instance.
Common mistakes
Common mistake
(Rounding is a heuristic, not a proof)
Rounding a relaxed solution is a heuristic, not an optimality proof. In a nonnegative packing model, coordinatewise rounding down preserves feasibility because every constraint coefficient is nonnegative. That statement fails with equality constraints, negative coefficients, or lower requirements. Rounding up can violate even a simple packing capacity. Always check the actual model after rounding.
Common mistake
(An upper bound must cover every integer point in the node)
An upper bound must apply to every integer point in the node. A feasible relaxed point supplies an objective value, but that value is not generally an upper bound for maximization. Use a proven relaxed optimum, a dual-feasible bound, or another valid inequality argument. An interrupted solver's current point and its certified bound have different meanings. Do not prune because a fractional coordinate is close to an integer without a stated numerical policy and feasibility recheck. The mathematical argument uses exact inequalities.
Common mistake
(An unbounded relaxation does not certify an improving integer point)
An unbounded relaxation does not prove the integer model has an improving integer ray: even the integer feasible set may be empty. For example, , with integer and objective maximize has an unbounded relaxation but no integer feasible point.
A valid cut cannot be justified only by rejecting the observed fractional optimizer. It must preserve all integer feasible points. Cover inequalities rely on binary upper bounds and nonnegative capacity coefficients; applying the same formula to unrestricted integer multiplicities changes the argument and can remove feasible solutions.
Counterexample mode
Integral vertices do not make every optimizer integral
A false inference from unimodularity is that a solver's every optimal point must be integer. Consider with the identically zero objective. The constraint matrix is totally unimodular and both vertices are integer, yet is also optimal. It is the average of the two vertices. The repaired statement is existence of an integer basic optimum under the theorem's hypotheses. If an algorithm returns an interior point of an optimal face, integrality of the polyhedron does not by itself make that returned point integral.
Summary
Integer restrictions change the feasible set. Relaxation bounds, exhaustive branching, and valid inequalities each provide a different part of a proof that an integer decision is best. Some matrices, especially incidence matrices with ordinary capacity constraints, guarantee integral vertices and avoid the gap altogether. Every conclusion has explicit assumptions: objective integrality for flooring bounds, finite domains for the elementary termination proof, and integer right-hand sides for unimodularity.
Exercises
Quick check
(In the first example, replace the objective by . Find the relaxed optimum value and the integer optimum value. Write a complete two-case integer certificate.)
Solution · Answer
The relaxation allows and attains objective , for example at . If , the binary variable gives value at most three. If , the capacity forces , again giving three. Both and attain three, so this is the integer optimum. A fractional combination can achieve the larger relaxed value without representing a realizable binary choice.
Quick check
(In the knapsack example, prove that is another valid cover inequality. Does also hold for every feasible integer point?)
Solution · Answer
Selecting both items one and three consumes , so every binary feasible point has at most one of them. This proves the first inequality. Items two and three consume exactly five, and is feasible. It violates the proposed second inequality, which is therefore invalid and would delete the true optimum.
Quick check
(A maximization node has certified upper bound and incumbent value . Can it be closed if all objective values are integers? What if the objective includes a continuous variable with coefficient one half?)
Solution · Answer
With integer objective values, every objective in the node is at most , so it cannot improve the incumbent and may be closed when seeking one optimum. A continuously varying objective term removes that integrality guarantee. Values such as can exceed the incumbent while respecting the bound; the raw bound alone then does not permit closure.
Quick check
(Show that rounding down the relaxed point fails feasibility for the integer requirement . Give an integer feasible point instead. Explain the direction of a relaxation bound for minimization.)
Solution · Answer
Rounding down gives one, which violates the lower requirement. The integer point two is feasible. For minimization, the relaxed feasible set still contains the integer one, but taking a minimum over a larger set produces a lower bound. A feasible integer incumbent supplies an upper bound. The names of the bounds reverse relative to maximization because the order of preferred objectives reverses.
Quick check
(Prove that a matrix formed by appending one unit column to a totally unimodular matrix remains totally unimodular. Explain why this result alone does not justify an arbitrary new coupling row.)
Solution · Answer
Take any square minor. If it excludes the new column, it is already a minor of the original matrix. If it includes that column and no nonzero entry from it, its determinant is zero. Otherwise expand along its sole nonzero entry; the determinant is plus or minus a smaller original minor, hence zero or plus or minus one. A new coupling row can contain many nonzero entries, so this expansion argument need not apply. Its minors must be checked by an appropriate separate structural argument.