Practice: The Linear Relaxation and Its Bound

(a) The relaxation. Drop integrality. The two constraints bind where $3x_1+4x_2=12$ and $4x_1+x_2=10$. From the second, $x_2=10-4x_1$; substituting, $3x_1+40-16x_1=12$, so $-13x_1=-28$ and $x_1=28/13\approx 2.154$, giving $x_2=10-112/13=18/13\approx 1.385$.

Value: $4(28/13)+3(18/13)=(112+54)/13=166/13\approx 12.77$.

This is a maximisation, so the relaxation gives an upper bound: no integer plan exceeds $12.77$. Since the objective coefficients are whole and the variables are integer, the value is a whole number, so no integer plan exceeds $12$.

(b) Rounding. $(2.154,1.385)$ rounds to $(2,1)$. Check: $3(2)+4(1)=10\le 12$ and $4(2)+1=9\le 10$. Feasible, with value $8+3=11$.

Rounding up on $x_2$ instead gives $(2,2)$: . Infeasible.

(c) The integer optimum. Check the feasible whole-number points with high value. $(0,3)$: $12\le 12$, $3\le 10$, feasible, value $9$. $(1,2)$: $3+8=11\le 12$, $4+2=6\le 10$, feasible, value $10$. $(2,1)$: feasible as above, value $11$. $(2,0)$: value $8$. $(1,1)$: value $7$.

The integer optimum is $11$ at $(2,1)$.

The gap. $12.77-11=1.77$, or against the tightened bound of $12$, a gap of $1$.

What to notice. Here rounding to nearest happened to land on the optimum, and that is luck, not method. The other rounding direction was infeasible, and nothing in the rounding step distinguishes the two cases. The bound is what actually certifies $(2,1)$: no integer plan can exceed $12$, and we have found $11$, so at most $1$ remains.

The rounded point is feasible. $(0,1)$ gives $0+11=11\le 21$. Value $10$. So far the analyst is correct.

It is not optimal. Consider $(1,1)$: $10+11=21\le 21$, feasible, with value . The rounded plan is beaten.

Why rounding could never have found it. Rounding adjusts each coordinate to a neighbour of its fractional value. Here $x_1$ was $0$ in the relaxation and is $1$ at the optimum, rounding $0$ gives $0$. The improvement required increasing a variable the relaxation had set to zero, which no rounding rule does.

Why 'conservative' is the wrong idea. Rounding down preserves feasibility for constraints of this form, so it avoids one failure mode. It says nothing about optimality, and 'conservative' quietly suggests the answer is safe in a sense it is not. It is safe to use and may be far from best.

What the bound actually tells us. The relaxation gives an upper bound of $19.09$, so no integer plan exceeds $19$. Against the analyst's $(0,1)$ with value $10$ that is a gap of $9$, enormous relative to the value, and a clear signal that searching further was worthwhile. The analyst had the number that showed their answer was questionable and read it as support instead.

The general point. The continuous and integer optima answer different questions, so there is no reason for them to be near each other. Here the relaxation puts everything into $x_2$ because its ratio is far better, while the integer optimum takes one unit of each. A structurally different plan, not a nearby one.

What should have been reported. The plan $(1,1)$ with value $11$, together with the bound: no integer plan exceeds $19$, so at most $8$ remains unclaimed, and whether to keep searching depends on what $8$ is worth.

What the two numbers are. The incumbent, $18795$, is the best integer plan found so far. A real, implementable plan with that cost. The best bound, $18240$, comes from relaxations and says no integer plan costs less. Together:

What the answer is. The plan costing $18795$. That is a genuine answer available now, not a provisional one, and it can be implemented today.

Is it optimal? Unknown. It may be. The gap can persist because the bound is slack rather than because a better plan exists. What is certain is that it is within $555$ of optimal, which is the $3\mathrm{\%}$ the solver reports.

Should we keep running? That depends on what $555$ is worth against the cost of computing, not on how long the solver has run. If these are pounds on a one-off schedule, an overnight run to chase at most $555$ is likely poor value. If they are pounds per day on an annual contract, it is worth continuing. The bound has converted a computational question into a business one, which is its real utility.

What would change the advice.

• A shrinking gap. If the gap has moved substantially in the last few minutes, progress is being made and continuing is more attractive.
• A static gap. An hour with no movement suggests the remaining work is large, and the marginal value of more time is low.
• The decision's own tolerance. If the plan must be acted on this afternoon, a $3\mathrm{\%}$ guarantee is a good position and further computation is irrelevant.
• Model quality. A large stubborn gap often indicates loose linking bounds. Tightening the formulation can close it far faster than more computing time, which is why 'improve the model' is sometimes the right answer to 'should we run longer'.

What not to say. That the answer is $18240$. Nothing establishes any plan attains the bound, and frequently none does. Reporting it as the cost would understate a real plan's price by $555$.