Optimization · 2010 · 41 citations · 3 references
Natural SciencesDecision SciencesMathematicsDecision TheoryOptimizationRevenue ManagementConstrained OptimizationDecision Under UncertaintyDecision-making Under UncertaintyOptimization TheoryOptimization Under UncertaintyRobust OptimizationCost Uncertainty AnalysisLinear Programming OptimizationOptimization Under Demand UncertaintyPolyhedral Uncertainty SetsRobust Linear ProgrammingUncertainty SetsWorst-case Optimization
Abstract We identify and discuss issues of hidden over-conservatism in robust linear optimization, when the uncertainty set is polyhedral with a budget of uncertainty constraint. The decision-maker selects the budget of uncertainty to reflect his degree of risk aversion, i.e. the maximum number of uncertain parameters that can take their worst-case value. In the first setting, the cost coefficients of the linear programming problem are uncertain, as is the case in portfolio management with random stock returns. We provide an example where, for moderate values of the budget, the optimal solution becomes independent of the nominal values of the parameters, i.e. is completely disconnected from its nominal counterpart, and discuss why this happens. The second setting focusses on linear optimization with uncertain upper bounds on the decision variables, which has applications in revenue management with uncertain demand and can be rewritten as a piecewise linear problem with cost uncertainty. We show in an example that it is possible to have more demand parameters equal their worst-case value than what is allowed by the budget of uncertainty, although the robust formulation is correct. We explain this apparent paradox. Keywords: linear optimizationrobust optimizationover-conservatismAMS Subject Classifications:: 90C0590C4690C47 Acknowledgements The author would like to thank an anonymous referee for his comments, which have improved the clarity of this note. This work was supported in part by NSF Grants CMMI-0540143 and CMMI-0757983.
3
Dimitris Bertsimas, Melvyn Sim · Operations Research · 2004 · 4.4K citations
Aharon Ben‐Tal, Arkadi Nemirovski · Mathematics of Operations Research · 1998 · 2.6K citations
Robust discrete optimization and network flows
Dimitris Bertsimas, Melvyn Sim · Mathematical Programming · 2003 · 1.8K citations