The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods
We introduce the referenced vertex ordering problem (revorder) as a combinatorial decision problem generalizing several vertex ordering problems that already appeared in the scientific literature under different guises. In other words, revorder is a generic problem with several possible extensions c...
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Université de Montpellier
2021-08-01
|
| Series: | Open Journal of Mathematical Optimization |
| Subjects: | |
| Online Access: | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.8/ |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1825204942047019008 |
|---|---|
| author | Omer, Jérémy Mucherino, Antonio |
| author_facet | Omer, Jérémy Mucherino, Antonio |
| author_sort | Omer, Jérémy |
| collection | DOAJ |
| description | We introduce the referenced vertex ordering problem (revorder) as a combinatorial decision problem generalizing several vertex ordering problems that already appeared in the scientific literature under different guises. In other words, revorder is a generic problem with several possible extensions corresponding to various real-life applications. Given a simple undirected graph $G=(V,E)$, revorder basically asks whether the vertices of $G$ can be sorted in a way to guarantee that every vertex is adjacent to a minimal number of its predecessors in the order. Previous works show that revorder, as well as its optimization counterpart, denoted in our work as min revorder, are NP-hard. We give a survey of methods and algorithms that can be applied to the solution of min revorder, and we develop a new enumeration scheme for its solution. Our theoretical analysis of this scheme yields several pruning techniques aimed at the reduction of the number of enumeration nodes. We then discuss how upper and lower bounds can be computed during the enumeration to design a branch-and-bound algorithm. Finally, we validate our branch-and-bound algorithm by conducting a large set of computational experiments on instances coming from various real-life applications. Our results highlight that the newly introduced pruning techniques allow the computation of good-quality solutions (in comparison with other solver’s solutions) while reducing the overall computational cost. Our branch-and-bound outperforms other existing solution methods: among 180 instances with 60 vertices, it solves 179 instances to optimality whereas the best existing method is only able to solve 109 of them. Moreover, our tests show that our algorithm can solve medium-scale instances up to 500 vertices, which opens the perspective of handling new real-life problems. Our implementation of the branch-and-bound algorithm, together with all instances we have used, is publicly available on GitLabGitLab repository: https://gitlab.insa-rennes.fr/Jeremy.Omer/min-revorder.git. |
| format | Article |
| id | doaj-art-28f399d00d43490f9ef07eacf21eb1ac |
| institution | Kabale University |
| issn | 2777-5860 |
| language | English |
| publishDate | 2021-08-01 |
| publisher | Université de Montpellier |
| record_format | Article |
| series | Open Journal of Mathematical Optimization |
| spelling | doaj-art-28f399d00d43490f9ef07eacf21eb1ac2025-02-07T14:02:30ZengUniversité de MontpellierOpen Journal of Mathematical Optimization2777-58602021-08-01212910.5802/ojmo.810.5802/ojmo.8The Referenced Vertex Ordering Problem: Theory, Applications, and Solution MethodsOmer, Jérémy0Mucherino, Antonio1Univ Rennes, INSA Rennes, CNRS, IRMAR, UMR 6625, 35000 Rennes, FranceUniv Rennes, CNRS, IRISA, UMR 6074, 35000 Rennes, FranceWe introduce the referenced vertex ordering problem (revorder) as a combinatorial decision problem generalizing several vertex ordering problems that already appeared in the scientific literature under different guises. In other words, revorder is a generic problem with several possible extensions corresponding to various real-life applications. Given a simple undirected graph $G=(V,E)$, revorder basically asks whether the vertices of $G$ can be sorted in a way to guarantee that every vertex is adjacent to a minimal number of its predecessors in the order. Previous works show that revorder, as well as its optimization counterpart, denoted in our work as min revorder, are NP-hard. We give a survey of methods and algorithms that can be applied to the solution of min revorder, and we develop a new enumeration scheme for its solution. Our theoretical analysis of this scheme yields several pruning techniques aimed at the reduction of the number of enumeration nodes. We then discuss how upper and lower bounds can be computed during the enumeration to design a branch-and-bound algorithm. Finally, we validate our branch-and-bound algorithm by conducting a large set of computational experiments on instances coming from various real-life applications. Our results highlight that the newly introduced pruning techniques allow the computation of good-quality solutions (in comparison with other solver’s solutions) while reducing the overall computational cost. Our branch-and-bound outperforms other existing solution methods: among 180 instances with 60 vertices, it solves 179 instances to optimality whereas the best existing method is only able to solve 109 of them. Moreover, our tests show that our algorithm can solve medium-scale instances up to 500 vertices, which opens the perspective of handling new real-life problems. Our implementation of the branch-and-bound algorithm, together with all instances we have used, is publicly available on GitLabGitLab repository: https://gitlab.insa-rennes.fr/Jeremy.Omer/min-revorder.git.https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.8/Vertex orderingDistance geometryBranch-and-boundInteger programmingValid inequalities |
| spellingShingle | Omer, Jérémy Mucherino, Antonio The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods Open Journal of Mathematical Optimization Vertex ordering Distance geometry Branch-and-bound Integer programming Valid inequalities |
| title | The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods |
| title_full | The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods |
| title_fullStr | The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods |
| title_full_unstemmed | The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods |
| title_short | The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods |
| title_sort | referenced vertex ordering problem theory applications and solution methods |
| topic | Vertex ordering Distance geometry Branch-and-bound Integer programming Valid inequalities |
| url | https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.8/ |
| work_keys_str_mv | AT omerjeremy thereferencedvertexorderingproblemtheoryapplicationsandsolutionmethods AT mucherinoantonio thereferencedvertexorderingproblemtheoryapplicationsandsolutionmethods AT omerjeremy referencedvertexorderingproblemtheoryapplicationsandsolutionmethods AT mucherinoantonio referencedvertexorderingproblemtheoryapplicationsandsolutionmethods |