Separation of convex polyhedral sets with uncertain data

This paper is a contribution to the interval analysis and separability of convex sets. Separation is a familiar principle and is often used not only in optimization theory, but in many economic applications as well. In real problems input data are usually not known exactly. For the purpose of this paper we assume that data can independently vary in given intervals. We study two cases when convex polyhedral sets are described by a system of linear inequalities or by the list of its vertices. For each case we propose a way how to check whether given convex polyhedral sets are separable for some or for all realizations of the interval data. Some of the proposed problems can be checked efficiently, while the others are NP-hard.


Proceedings of the 24-th Int. Conf. Mathematical Methods in Economics MME06, Pilsen, 2006, pp. 227-234.



View Separation of convex polyhedral sets with uncertain data