A plan must survive the stated uncertainty
A production plan may be chosen before exact resource consumption is known. A nominal constraint checks one estimated coefficient vector; a robust constraint asks the same fixed plan to satisfy the limit for every coefficient vector in a specified uncertainty set. This is a worst-case requirement, not a probability statement or a guarantee when the true coefficients lie outside that set.
We use exact real arithmetic and assume the decision vector is chosen once before the uncertain coefficients are observed.
Definition 8.5.1
(Robust feasibility for one resource constraint)
Let be an uncertainty set of coefficient vectors and a known capacity. A decision is robustly feasible if
Equivalently, . An inequality in alone with exactly the same solution set is a robust counterpart of the constraint.
Independent intervals
Theorem 8.5.2
(Robust counterpart for independent intervals and nonnegative decisions)
Let with finite , and let . Then is robustly feasible if and only if
Proof
(Termwise bound and a test vector)
Sufficiency. For every and every , and give . Summing, .
Necessity. All upper endpoints occur together in the product set, so is an allowed vector. Robust feasibility applied to it gives .
Proof X-ray
Which hypothesis each half of the proof uses
The two halves rest on different hypotheses. Sufficiency uses only the sign of the decision: an upper endpoint maximizes a single term because is nonnegative. Necessity uses only the shape of the uncertainty set: the endpoint vector must itself belong to , which the product structure guarantees. Each half can fail on its own.
If some fixed is negative, the lower endpoint maximizes that term, and for free-sign decisions the exact product-set worst case is the sum over of the larger of and . If is not a product, the sum of upper endpoints remains a safe bound but may be unattainable, so the inequality is no longer exact; the coupled set below is such a case.
A production example
Worked example 8.5.3
(The robust optimum under independent intervals)
Choose to maximize , with unit resource coefficients independently in and capacity . By the theorem, robust feasibility is , or . Since , and attains , the plan is robustly optimal with objective .
Worked example 8.5.4
(A nominal optimum that is not robustly feasible)
If one substitutes the nominal coefficients instead, the constraint is and the nominal optimum is with value . But the allowed coefficient vector consumes units at that plan, exceeding capacity . Nominal optimality is therefore not a robust feasibility certificate. In the degenerate case for all the two models coincide.
Coupled uncertainty changes the answer
Theorem 8.5.5
(Worst case for a one-parameter coupled set)
Let . For ,
so with capacity the robust counterpart is the pair of inequalities , .
Proof
(Maximizing a linear function of the parameter)
For fixed , is linear in , so it is maximized at the endpoint whose sign matches , with value . The identity finishes the computation, and is equivalent to and .
Worked example 8.5.6
(Coupled uncertainty allows a larger plan)
Each coefficient ranges from to , but they cannot both equal . Under the coupled set the best plan maximizes over , which is with objective . Replacing this coupled set by the larger independent box imposes and gives optimum . That box is safe for the coupled set, but conservative: it includes coefficient combinations the model says cannot occur.
Common mistakes
Counterexample mode
Individual ranges do not determine joint uncertainty
At the coupled-set optimum , every allowed uses exactly four units, since . The independent-box vector would use eight, but it is not generated by any single . The same separate coefficient ranges can therefore lead to different exact robust feasible sets. One must state which combinations can occur together.
Common mistake
(Substituting upper endpoints for a negative decision)
If and , then ranges over and is largest at the lower endpoint. Using underestimates the worst case by and can accept an infeasible plan.
Common mistake
(Expecting protection outside the stated set)
The robust plan is safe for coefficients in . If the first coefficient is actually , it uses units and violates capacity . The guarantee covers exactly the declared uncertainty set.
Exercises
Quick check
(Under independent intervals and capacity , are and robustly feasible?)
Solution · Answer
The worst-case uses are and respectively. The first is feasible and the second is not.
Quick check
(For , in the coupled model, find a maximizing and the worst resource use.)
Solution · Answer
, so choose , giving coefficients . The worst use is .
Quick check
(With the coupled set and capacity , verify the upper bound for robustly feasible nonnegative .)
Solution · Answer
Robust feasibility gives and , so , attained at .
Quick check
(If and , which endpoint maximizes , and why does the nonnegative-variable formula fail?)
Solution · Answer
The lower endpoint gives , greater than the upper endpoint's . Multiplication by a negative decision reverses the endpoint ordering, so the sufficiency half of the proof no longer applies.