The maximal descriptor index set for a face of a convex polyhedral set and some applications

A face of a convex polyhedral set can be investigated on the basis of only the maximal descriptor index set for it. This helps us reduce difficulties and computational efforts in solving many problems. In this paper, we consider a multiple objective linear programming (MOLP) problem in which the constraint polyhedron may have no extreme points and the variables may be negative. First we deal with determining the maximal descriptor index set for an arbitrary face of the constraint polyhedron, then we apply the maximal descriptor index sets for faces to compare descriptor sets for the faces and find all maximal efficient faces for the MOLP problem. The methods known so far compare descriptor sets at large computational cost (in terms of computing times and storage) because they require finding all extreme points and directions of them. Known top-down search methods have been devised to find the efficient set of the MOLP problem but they may fail to find all maximal efficient faces and the computational cost is considerable. We propose a new method to compare descriptor sets and a new top-down search method which finds all maximal efficient faces and requires less computational cost. A numerical example is given to illustrate how the method works.