Abstract: We present an adaptation of the classical algorithm of the decomposition of Bender to the b-complementary multisemigroup dual problem. Despite this decomposition has been shown in literature as a good tool for dealing with high dimensional mixed-integer linear programming, that is not the case for the presented one in this paper, which is better to be solved by the simplex algorithm without partitioning. We present results from computer experiments to show that conclusion.
Keywords: Multisemigroup; Complementary; Duality; Benders Decomposition
[1]. Aráoz J. and Johnson E., "Polyhedra of Multivalued System Problems", Report No.82229-OR, Institut für Ökonometrie und Operations Research, Bonn, W. Germany (1982)
[2]. Aráoz J. and Johnson E.,"Morphic Liftings between of pairs of Integer Polyhedra", Research Report 89616OR, Int. Operations Research, Bonn 1989.
[3]. Benders, J. F., "Partitioning procedures for solving mixed variables programming problems", Numerische Mathematik, Set. 1962, 4(3): 238-252.
[4]. Madriz E., "Duality for a b-complementary multisemigroup master problem", Discrete Optimization Volume 22, Part B, November 2016, Pages 364-371
[5]. Rahmaniani R. Cranic T. G. and Rei W.,"The Benders Decomposition Algorithm: A Literature Review", CIRRELT -2016-30, June 2016, https://www.cirrelt.ca/DocumentsTravail/CIRRELT-2016-30.pdf