On 2‐stage robust LP with RHS uncertainty: complexity results and applications

We investigate here the class–denoted R‐LP‐RHSU–of two‐stage robust linear programming problems with right‐hand‐side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with uncertain task durations); robust maximum flow (with uncertain arc capacities); robust network capacity expansion problems; robust inventory management; some robust production planning problems in the context of power production/distribution systems. It is shown that such problems can be formulated as large scale linear programs with associated nonconvex separation subproblem. A formal proof of strong NP‐hardness for the general case is then provided, and polynomially solvable subclasses are exhibited. Differences with other previously described robust LP problems (featuring row‐wise uncertainty instead of column wise uncertainty) are highlighted.