The Benders Decomposition for the Dual of the b- Complementary Multi-Semigroup Problem

Eleazar Gerardo Madriz Lozada

CETEC-UFRB, Cruz da Almas, BA, Brazil.

Abstract: Multi-valued Additive Systems defined by Araoz and Johnson in 1982, these finite algebraic structures are a generalization of finite groups and semigroups. A particular case of these systems are the b-complemetary multisemigroups. In 1980 Johnson studied the dual primal problem over a semigroup, and in 1985 Araoz and Johnson presented a study that classifies the polyhedron associated with an additive system, a study that features vertices and faces of this polyhedron. Madriz in 2016 presents the duality results for the primal problem over a b-complementary multisemigroup. In this work, we show that systems of two different bases of the cone associated with an integer linear programming problem under a b-complementary Multisemigroup are equivalent. We also present the decomposition of Benders for the dual problem of the a b-Complementary Multisemigroup.

Keywords: Additive System, Multisemigruop, b-Complementary, Duality, Benders Decompostion.

Pages: 193 – 205 | Full PDF Paper