As shown in previous work, robustlinearprogramming problems featuring polyhedral right-hand side (RHS) uncertainty (a) arise in many practical applications;(b) frequently lead to robust equivalents belonging to the ...
详细信息
As shown in previous work, robustlinearprogramming problems featuring polyhedral right-hand side (RHS) uncertainty (a) arise in many practical applications;(b) frequently lead to robust equivalents belonging to the class of strongly NP-hard problems. In the present paper the case of ellipsoidal RHS uncertainty is investigated and similar complexity results are shown to hold even when restricting to simplified specially structured problems related to robust production planning under uncertain customer requirements. The proof is based on a reduction which significantly differs from the one used in the case of polyhedral RHS uncertainty.
We investigate here the class-denoted R-LP-RHSU-of two-stage robustlinearprogramming problems with right-hand-side uncertainty. Such problems arise in many applications e.g: robust PERT scheduling (with uncertain ta...
详细信息
We investigate here the class-denoted R-LP-RHSU-of two-stage robustlinearprogramming 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.
暂无评论