Enumeration of possibly optimal extreme points in linear programming problems with single objective function coefficient vectors in convex polytopes

In this paper, we deal with a linear programming problem whose objective function coefficient vector is not known exactly but contained in a convex polytope. While the independence among uncertain coefficients has been implicitly assumed in interval linear programming problems, a certain kind of interaction (dependency) among uncertain coefficients can be treated in our problem. To such a problem, two kinds of optimal solutions are defined: possibly and necessarily optimal solutions. A necessarily optimal solution is the most reasonable solution. However, it does not exist in many problems. On the other hand, a possibly optimal solution is the least reasonable solution and always exists. Any possibly optimal solution can be represented as a convex combination of possibly optimal extreme points. Therefore, enumeration of possibly optimal extreme points is discussed in this paper. It is shown that the possibly optimal solution set coincides with the weakly efficient solution set to a certain multiobjective linear programming problem. This result implies that all possibly optimal extreme points can be enumerated by tracing adjacent basic solutions from a possibly optimal basic solution. In order to apply this approach, a possible optimality test of an adjacent basic solution is necessary. We show that the possible optimality test problem is reduced to a linear programming problem. Based on this possible optimality test, an enumeration algorithm of possibly optimal extreme points is proposed. On the other hand, in many applications, it is sufficient to obtain a superset of the possibly optimal extreme point set. From this point of view, an alternative method is conceivable, i.e., using an outer box-set approximation of the given convex polytope, such a superset can be obtained by Steuer's enumeration method previously proposed for the interval coefficient case. By numerical experiments, the proposed enumeration method is compared with the above alternative method. The results show that the proposed method is more efficient.