Use continuous solutions as bounds, not rounded answers

Try

A synthetic packing decision maximizes 4x+3y subject to 2x+2y≤7 with nonnegative integer quantities. At most three whole items fit, so choosing x=3,y=0 gives value twelve. The continuous relaxation permits x=7/2,y=0 and reaches fourteen. The relaxed answer is not a feasible integer decision, but it is a valid upper bound. The two values quantify a gap between what a continuous model permits and what the original discrete model can achieve.

Predict

Predict whether rounding the relaxed optimizer always produces an integer optimum. Rounding upward can violate capacity; rounding downward can leave resources unused or choose the wrong combination. Even when a rounded point is feasible, it must be evaluated and compared with a valid bound. A relaxation does not become an equivalent reformulation merely because its variables have the same names. The omitted integrality constraints are mathematically consequential.

Experiment

Compare the continuous and integer decisions in the worked problem. The objective favors x over y when both consume the same resource amount.

Decision	Resource use	Objective	Integer feasible?
(7/2,0)	7	14	No
(4,0)	8	16	No: capacity fails
(3,0)	6	12	Yes
(2,1)	6	11	Yes

Prove the integer upper bound twelve by using x+y≤3 and 4x+3y≤4(x+y). This stronger integrality argument closes the gap without search. A continuous bound of fourteen alone would certify only that the feasible value twelve is within two objective units of optimality.

Understand

A relaxation enlarges the feasible set while keeping the objective and optimization direction. For maximization, its optimum is an upper bound on the original optimum; for minimization, it is a lower bound. A feasible integer incumbent provides the opposite bound. Their difference gives an absolute optimality gap. Relative gaps require a declared denominator and care near zero or negative values; one universal percentage formula is not meaningful for every objective scale.

Some LPs already have integral vertices. A sufficient condition is a totally unimodular constraint matrix A, integral right side b, and the usual form Ax≤b,x≥0. Total unimodularity means every square subdeterminant is zero, one or minus one. Adding identity rows for active nonnegativity preserves that property. A nonsingular active basis therefore has determinant ±1, and Cramer’s rule gives integral vertex coordinates. This statement concerns vertices, not every point in the polyhedron. It also does not permit arbitrary changes to A or nonintegral right sides without rechecking the assumptions.

Apply

Use the feasible fractional point (0.6,0.6) under x+y≤1.2. Rounding both coordinates to the nearest integer produces (1,1), which violates the constraint. The point was feasible before rounding, so the failure is specifically in the recovery rule. In more elaborate models, rounding can also violate equalities, connectivity or logical implications even when individual bounds remain satisfied.

Explain an integrality gap as a property of a particular relaxation and instance. A large gap means that bound may be weak, not that every integer algorithm must be slow. Additional valid inequalities can tighten the relaxation without removing integer feasible points. Each proposed cut needs a proof of validity for all original integer solutions; fitting a cut around observed good solutions is not sufficient.

Continue

Record the original integer model, the relaxed model and the recovery method separately. A relaxed solution may be useful as a bound even when it is not implementable. Continue to Branch and bound to combine these bounds with an exhaustive split of integer possibilities. Correct pruning will depend on valid bounds and a genuinely feasible incumbent, not on a solver’s optimistic intermediate estimate.