Facets of Non-Master Additive System Polyhedra

Eleazar Madriz

Universidade Federal do Reconcavo da Bahia Cruz das Almas, BAHIA, Brazil.

Abstract: The lifting of the facet is a technique used to generate polyhedral facet for the integer optimization problem. For groups, semigroups, and abelian additive systems master problems, homomorphism and sub-morphism can be used for lifting the facets. Another known methodology is the sequential lifting, which provides a new facet from a facet an element which not considered by facet, thus considering a new element. For abelian groups, there exist results for the sequential lifting of facets to consider the algebraic aspect and not the geometric aspect of the polyhedron. In this case of semigroups or additive systems master problems, the subadditive cone is important to the lifting facet. These results do not use the polyhedron polarity to lifting facet, in this paper we used the polarity polyhedra results to define sequential lifting facets of non-master associative, abelian, and b-complementary. The results presented here extend the known theorems of the sequential lifting for groups and semigroups. The sequential lifting of facets theorems for non-master problems doesn’t consider the polarity of the polyhedron to characterize facets, as far as we know, this is the first result that establishes sequential lifting for associative, abelian and b-complementary additive system non-master problems.

Keywords: additive system, polyhedra-polarity, sequential lifting.

Pages: 159 – 169 | Full PDF Paper