On 2-stage robust LP with RHS uncertainty: complexity results and applications |
| |
Authors: | Michel Minoux |
| |
Affiliation: | (3) University Paris, Paris, France; |
| |
Abstract: | 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. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|