Maximin and Maximal Solutions for Linear Programming Problems with Possibilistic Uncertainty

Abstract We consider linear programming problems with uncertain constraint coefficients described by intervals or, more generally, possi-bility distributions. The uncertainty is given a behavioral interpretation using coherent lower previsions from the theory of imprecise probabilities. We give a meaning to the linear programming problems by reformulat-ing them as decision problems under such imprecise-probabilistic uncer-tainty. We provide expressions for and illustrations of the maximin and maximal solutions of these decision problems and present computational approaches for dealing with them