On prime and minimal representations of a face of a polyhedron

Ta Van Tu (t_vantuyahoo.com)

Abstract: 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.

Keywords: Faces of a polyhedron; degeneracy degrees of faces; prime and minimal representations of a face; the maximal descriptor index set

Category 1: Combinatorial Optimization

Category 2: Combinatorial Optimization (Polyhedra )

Category 3: Other Topics (Multi-Criteria Optimization )

Citation: Department of Operations Research, Corvinus University of Budapest, H-1093, Budapest, Hungary December 02, 2018

Download: [PDF]

Entry Submitted: 12/02/2018
Entry Accepted: 12/03/2018
Entry Last Modified: 11/09/2019

Modify/Update this entry