In this paper, a new method for determining all minimal representations of a face of a polyhedron is proposed. A main difficulty for determining prime and minimal representations of a face is that the deletion of one redundant constraint can change the redundancy of other constraints. To reduce computational efforts in finding all minimal representations of a face, we prove and use properties that deleting strong redundant inequality constraints does not change the redundancy of other constraints and all minimal representations of the face can be found in only the set of all prime representations of the face corresponding to the maximal descriptor index set for it. An algorithm based on a top-down search method is given for finding all minimal representations of a face. Numerical examples are given to illustrate the performance of the algorithm.
Citation
Department of Operations Research, Corvinus University of Budapest, H-1093, Budapest, Hungary December 02, 2018
Article
View On prime and minimal representations of a face of a polyhedron