Robust solutions of uncertain linear programs. (English) Zbl 0941.90053

Summary: We treat in this paper Linear Programming (LP) problems with uncertain data. The focus is on uncertainty associated with hard constraints: those which must be satisfied, whatever is the actual realization of the data (within a prescribed uncertainty set). We suggest a modeling methodology whereas an uncertain LP is replaced by its Robust Counterpart (RC). We then develop the analytical and computational optimization tools to obtain robust solutions of an uncertain LP problem via solving the corresponding explicitly stated convex RC program. In particular, it is shown that the RC of an LP with ellipsoidal uncertainty set is computationally tractable, since it leads to a conic quadratic program, which can be solved in polynomial time.


90C05 Linear programming
90C25 Convex programming
90C51 Interior-point methods
Full Text: DOI


[1] Ben-Tal, A., The entropic penalty approach to stochastic programming, Math. Oper. Res, 10, 263-279 (1985) · Zbl 0565.90052
[2] Ben-Tal, A.; Nemirovski, A., Robust truss topology design via semidefinite programming, SIAM J. Optim, 7, 991-1016 (1997) · Zbl 0899.90133
[3] Ben-Tal, A.; Nemirovski, A., Robust convex optimization, Math. Oper. Res, 23, 769-805 (1998) · Zbl 0977.90052
[4] Ben-Tal, A.; Zibulevsky, M., Penalty/barrier multiplier methods for convex programming problems, SIAM J. Optim, 7, 347-366 (1997) · Zbl 0872.90068
[11] Mulvey, J. M.; Vanderbei, R. J.; Zenios, S. A., Robust optimization of large-scale systems, Oper. Res, 43, 264-281 (1995) · Zbl 0832.90084
[14] Rockafellar, R. T.; Wets, R. J.-B., Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res, 16, 119-147 (1991) · Zbl 0729.90067
[15] Singh, C., Convex programming with set-inclusive constraints and its applications to generalized linear and fractional programming, J. Optim. Theory Appl, 38, 1, 33-42 (1982) · Zbl 0472.90047
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.