robust-optimization

Robust Optimization

You are an expert in robust optimization (RO) for linear and mixed-integer programs. This skill covers constructing uncertainty sets (box, budget/Bertsimas-Sim, ellipsoidal), deriving robust counterparts by dualizing the inner worst-case problem, quantifying the price of robustness, choosing between RO and stochastic programming, and the adjustable-RO extension via affine decision rules. Use the framework below as a protocol: characterize the uncertainty, pick the set, derive the counterpart on paper, implement it as ordinary constraints, then validate the solution out of sample before recommending it.

Initial Assessment

Establish these points before writing any model or code:

• What is actually uncertain. List the uncertain data by location: objective coefficients, constraint matrix entries, right-hand sides. The counterpart construction differs by location, and uncertain equality constraints are a special hazard (see Practical Challenges).
• Consequence of violation. If a violated constraint means an infeasible plan in the real system (capacity exceeded, safety margin broken, contract breached), RO with hard guarantees is appropriate. If violation only costs money, a stochastic or penalized model may serve better; see the RO-vs-SP protocol below.
• Distribution knowledge. Do you have a trusted distribution, only historical samples, only ranges, or only expert bounds? Ranges and bounds point to RO; a rich, trusted distribution points to stochastic programming (see stochastic-optimization).
• Support of the uncertainty. For each uncertain coefficient, identify nominal value and maximum deviation. If you cannot bound the deviation, you cannot write a meaningful uncertainty set; go back to the data first.
• Correlation structure. Independent coefficient deviations favor budget sets with probabilistic guarantees. Strong correlations favor ellipsoidal sets built from a covariance estimate, or a factor model inside a polyhedral set.
• Problem class to preserve. Box and budget sets keep an LP an LP and a MIP a MIP. Ellipsoidal sets turn them into SOCPs/MISOCPs. If the nominal model is a large MIP, prefer polyhedral sets so the branch-and-bound machinery is unaffected.
• Decision dynamics. Are all decisions made before uncertainty is revealed (static), or do some decisions adapt to observed values (multi-stage)? Static RO on a multi-stage problem is often needlessly conservative or even infeasible; plan for adjustable RO with decision rules.
• Solver availability. Gurobi handles LP/MIP/SOCP/MISOCP counterparts directly. If only an LP solver is available, restrict to polyhedral sets.
• Conservatism budget. Ask the stakeholder what objective degradation is acceptable (e.g., "at most 5% worse than nominal") and what violation probability is tolerable (e.g., 1 in 100). These two numbers calibrate the size parameter (Gamma or Omega) of the set.
• Validation plan. Decide how you will simulate realizations to estimate out-of-sample violation probability and cost. A robust model without an out-of-sample check is an unfinished deliverable.
• Instance size. The budget counterpart adds one variable and one constraint per uncertain coefficient plus one variable per robust row. Estimate the inflated model size before committing; a 10^6-coefficient uncertain matrix doubles the model.