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
[5] A. Ben-Tal, T. Margelit, A. Nemirovski, Robust modeling of multi-stage portfolio problems, in: Proc. Workshop on High-Performance Optimization, S. Zhang (Ed.), Rotterdam, August 1997, Kluwer Academic Press, Dordrecht, to appear, 1999.
[6] J.R. Birge, F. Louveaux, Introduction to Stochasatic Programming, Springer, Berlin, 1997. · Zbl 0892.90142
[7] J.E. Falk, Exact solutions to inexact linear programs, Oper. Res. 1976, 783-787. · Zbl 0335.90035
[8] M. Grötschel, L. Lovasz, A. Schrijver, The Ellipsoid Method and Combinatorial Optimization, Springer, Heidelberg, 1988.
[9] P. Kall, S.W. Wallace, Stochastic Programming, Wiley-Interscience, New York, 1994. · Zbl 0812.90122
[10] H.M. Markovitz, Portfolio Selection: Efficiency Diversification of Investment, Wiley, New York, 1959.
[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
[12] Yu. Nesterov, A. Nemirovski, Interior Point Polynomial Algorithms in Convex Programming, SIAM Studies in Applied Mathematics, SIAM, Philadelphia, 1994. · Zbl 0977.90081
[13] A. Prékopa, Stochastic Programming, Kluwer Academic Publishers, Dordrecht, 1995.
[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
[16] A.L. Soyster, Convex programming with set-inclusive constraints and applications to inexact linear programming, Oper. Res. 1973, 1154-1157. · Zbl 0266.90046
[17] K. Zhou, J.C. Doyle, K. Glover, Robust and Optimal Control, Prentice-Hall, Englewood Cliffs, NJ, 1996. · Zbl 0999.49500
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.