Journals Information
Mathematics and Statistics Vol. 11(1), pp. 223 - 228
DOI: 10.13189/ms.2023.110126
Reprint (PDF) (699Kb)
A Facet Defining of the Dicycle Polytope
Mamane Souleye Ibrahim 1,*, Oumarou Abdou Arbi 2
1 Department of Mathematics and Computer Science, Abdou Moumouni University, Niamey, Niger
2 Department of Mathematics and Computer Science, Dan Dicko Dankoulodo University, Maradi, Niger
ABSTRACT
In this paper, we consider the polytope of all elementary dicycles of a digraph
. Dicycles problem, in graph theory and combinatorial optimization, solved by polyhedral approaches has been extensively studied in literature. Therefore cutting plane and branch and cut algorithms are unavoidable to exactly solve such a combinatorial optimization problem. For this purpose, we introduce a new family of valid inequalities called
alternating 3-arc path inequalities for the polytope of elementary dicycles
. Indeed, these inequalities can be used in cutting plane and branch and cut algorithms to construct strengthened relaxations of a linear formulation of the dicycle problem. To prove the facetness of
alternating 3-arc path inequalities, in opposite to what is usually done that consists basically to determine the affine subspace of a linear description of the considered polytope, we resort to constructive algorithms. Given the set of arcs of the digraph
, algorithms devised and introduced are based on the fact that from a first elementary dicycle, all other dicycles are iteratively generated by replacing some arcs of previously generated dicycles by others such that the current elementary dicycle contains an arc that does not belong to any other previously generated dicycles. These algorithms generate dicyles with affinely independent incidence vectors that satisfy
alternating 3-arc path inequalities with equality. It can easily be verified that all these devised algorithms are polynomial from time complexity point of view.
KEYWORDS
Digraph, Dicycle, Valid Inequality, Facet, Polytope
Cite This Paper in IEEE or APA Citation Styles
(a). IEEE Format:
[1] Mamane Souleye Ibrahim , Oumarou Abdou Arbi , "A Facet Defining of the Dicycle Polytope," Mathematics and Statistics, Vol. 11, No. 1, pp. 223 - 228, 2023. DOI: 10.13189/ms.2023.110126.
(b). APA Format:
Mamane Souleye Ibrahim , Oumarou Abdou Arbi (2023). A Facet Defining of the Dicycle Polytope. Mathematics and Statistics, 11(1), 223 - 228. DOI: 10.13189/ms.2023.110126.