Corvinus
Corvinus

Minimal Representations of a Face of a Convex Polyhedron and Some Applications

Van, Tu Ta ORCID: https://orcid.org/0000-0002-9039-5362 (2021) Minimal Representations of a Face of a Convex Polyhedron and Some Applications. Acta Mathematica Vietnamica . DOI https://doi.org/10.1007/s40306-021-00437-y

[img]
Preview
PDF - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader
414kB

Official URL: https://doi.org/10.1007/s40306-021-00437-y

A nyílt hozzáférést az EISZ és a kiadó között létrejött "Read and Publish" szerződés biztosította. Open access was provided "Read and Publish" contract between EIS and the publisher.

Abstract

In this paper, we propose a method for determining all minimal representations of a face of a polyhedron defined by a system of linear inequalities. Main difficulties for determining prime and minimal representations of a face are that the deletion of one redundant constraint can change the redundancy of other constraints and the number of descriptor index pairs for the face can be huge. To reduce computational efforts in finding all minimal representations of a face, we prove and use properties that deleting strongly redundant constraints does not change the redundancy of other constraints and all minimal representations of a face can be found only in the set of all prime representations of the face corresponding to the maximal descriptor index set for it. The proposed method is based on a top-down search strategy, is easy to implement, and has many computational advantages. Based on minimal representations of a face, a reduction of degeneracy degrees of the face and ideas to improve some known methods for finding all maximal efficient faces in multiple objective linear programming are presented. Numerical examples are given to illustrate the method.

Item Type:Article
Uncontrolled Keywords:faces of a polyhedron, degeneracy degrees of faces, prime and minimal representations of a face, maximal descriptor index set, multiple objective programming
Subjects:Mathematics, Econometrics
DOI:https://doi.org/10.1007/s40306-021-00437-y
ID Code:6885
Deposited By: Veronika Vitéz
Deposited On:01 Oct 2021 08:14
Last Modified:01 Oct 2021 08:15

Repository Staff Only: item control page

Downloads

Downloads per month over past year

View more statistics