# Open Journal of Mathematical Optimization

The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods
Open Journal of Mathematical Optimization, Volume 2 (2021), article no. 6, 29 p.

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=\left(V,E\right)$, 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.

Revised:
Accepted:
Published online:
DOI: 10.5802/ojmo.8
Keywords: Vertex ordering, Distance geometry, Branch-and-bound, Integer programming, Valid inequalities
Jérémy Omer 1; Antonio Mucherino 2

1 Univ Rennes, INSA Rennes, CNRS, IRMAR, UMR 6625, 35000 Rennes, France
2 Univ Rennes, CNRS, IRISA, UMR 6074, 35000 Rennes, France
@article{OJMO_2021__2__A6_0,
author = {J\'er\'emy Omer and Antonio Mucherino},
title = {The {Referenced} {Vertex} {Ordering} {Problem:} {Theory,} {Applications,} and {Solution} {Methods}},
journal = {Open Journal of Mathematical Optimization},
eid = {6},
publisher = {Universit\'e de Montpellier},
volume = {2},
year = {2021},
doi = {10.5802/ojmo.8},
language = {en},
url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.8/}
}
TY  - JOUR
TI  - The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods
JO  - Open Journal of Mathematical Optimization
PY  - 2021
DA  - 2021///
VL  - 2
PB  - Université de Montpellier
UR  - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.8/
UR  - https://doi.org/10.5802/ojmo.8
DO  - 10.5802/ojmo.8
LA  - en
ID  - OJMO_2021__2__A6_0
ER  - 
%0 Journal Article
%T The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods
%J Open Journal of Mathematical Optimization
%D 2021
%V 2
%I Université de Montpellier
%U https://doi.org/10.5802/ojmo.8
%R 10.5802/ojmo.8
%G en
%F OJMO_2021__2__A6_0
Jérémy Omer; Antonio Mucherino. The Referenced Vertex Ordering Problem: Theory, Applications, and Solution Methods. Open Journal of Mathematical Optimization, Volume 2 (2021), article  no. 6, 29 p. doi : 10.5802/ojmo.8. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.8/

[1] Therese Biedl; Timothy Chan; Yashar Ganjali; Mohammad Taghi Hajiaghayi; David R. Wood Balanced vertex-orderings of graphs, Discrete Appl. Math., Volume 148 (2005) no. 1, pp. 27-48 | Article | MR: 2132060 | Zbl: 1060.05088

[2] Pratik Biswas; Tzu-Chen Lian; Ta-Chung Wang; Yinyu Ye Semidefinite programming based algorithms for sensor network localization, ACM Transactions in Sensor Networks, Volume 2 (2006), pp. 188-220 | Article

[3] Andrea Cassioli; Oktay Günlük; Carlile Lavor; Leo Liberti Discretization vertex orders in distance geometry, Discrete Appl. Math., Volume 197 (2015), pp. 27-41 | Article | MR: 3398958 | Zbl: 1321.05029

[4] Fan R. K. Chung; Linyuan Lu Complex Graphs and Networks, CBMS Regional Conference Series in Mathematics, 107, American Mathematical Society, 2006, 264 pages | MR: 2248695 | Zbl: 1114.90071

[5] Yichuan Ding; Nathan Krislock; Jiawei Qian; Henry Wolkowicz Sensor network localization, Euclidean distance matrix completions, and graph realization, Optim. Eng., Volume 11 (2010) no. 1, pp. 45-66 | Article | MR: 2601732 | Zbl: 1273.74387

[6] Elizabeth D. Dolan; Jorge J. Moré Benchmarking optimization software with performance profiles, Math. Program., Volume 91 (2002) no. 2, pp. 201-213 | Article | MR: 1875515 | Zbl: 1049.90004

[7] Douglas S. Gonçalves; Antonio Mucherino Optimal partial discretization orders for discretizable distance geometry, Int. Trans. Oper. Res., Volume 23 (2016) no. 5, pp. 947-967 | Article | MR: 3508437 | Zbl: 1348.90595

[8] Mehdi Hemmati; J. Cole Smith; My T. Thai A cutting-plane algorithm for solving a weighted influence interdiction problem, Comput. Optim. Appl., Volume 57 (2014) no. 1, pp. 71-104 | Article | MR: 3146501 | Zbl: 1308.91040

[9] Matt J. Keeling; Ken T. D Eames Networks and epidemic models, J. R. Soc. Interface, Volume 2 (2005) no. 4, pp. 295-307 | Article

[10] Carlile Lavor; Jon Lee; Audrey Lee-St. John; Leo Liberti; Antonio Mucherino; Maxim Sviridenko Discretization orders for distance geometry problems, Optim. Lett., Volume 6 (2012) no. 4, pp. 783-796 | Article | MR: 2902263 | Zbl: 1258.90096

[11] Carlile Lavor; Leo Liberti; Nelson Maculan; Antonio Mucherino The discretizable molecular distance geometry problem, Comput. Optim. Appl., Volume 52 (2012) no. 1, pp. 115-146 | Article | MR: 2925767 | Zbl: 1259.90153

[12] Leo Liberti; Carlile Lavor; Nelson Maculan A branch-and-prune algorithm for the molecular distance geometry problem, Int. Trans. Oper. Res., Volume 15 (2008) no. 1, pp. 1-17 | Article | MR: 2387010 | Zbl: 1136.92037

[13] Leo Liberti; Carlile Lavor; Nelson Maculan; Antonio Mucherino Euclidean distance geometry and applications, SIAM Rev., Volume 56 (2014), pp. 3-69 | Article | MR: 3246296 | Zbl: 1292.51010

[14] Leo Liberti; Carlile Lavor; Antonio Mucherino; Nelson Maculan Molecular distance geometry methods: from continuous to discrete, Int. Trans. Oper. Res., Volume 18 (2011) no. 1, pp. 33-51 | Article | MR: 2779655 | Zbl: 1219.90177

[15] Leo Liberti; Benoît Masson; Jon Lee; Carlile Lavor; Antonio Mucherino On the number of realizations of certain Henneberg graphs arising in protein conformation, Discrete Appl. Math., Volume 165 (2014), pp. 213-232 | Article | MR: 3162289 | Zbl: 1288.05121

[16] Moira MacNeil; Merve Bodur Integer Programming, Constraint Programming, and Hybrid Decomposition Approaches to Discretizable Distance Geometry Problems (2019) (https://arxiv.org/abs/1907.12468)

[17] C. Miller; Albert Tucker; R. Zemlin Integer programming formulation of traveling salesman problems, J. Assoc. Comput. Mach., Volume 7 (1960), p. 326-–329 | Article | MR: 149964 | Zbl: 0100.15101

[18] Antonio Mucherino On the identification of discretization orders for distance geometry with intervals, Geometric science of information (Lecture Notes in Computer Science), Volume 8085, Springer, 2013, pp. 231-238 | Article | MR: 3126050 | Zbl: 1405.51008

[19] Antonio Mucherino A pseudo de Bruijn graph representation for discretization orders for distance geometry, IWBBIO15: Bioinformatics and Biomedical Engineering (Lecture Notes in Computer Science), Volume 9043 (2015), pp. 514-523

[20] Antonio Mucherino; Carlile Lavor; Leo Liberti The discretizable distance geometry problem, Optim. Lett., Volume 6 (2012) no. 8, pp. 1671-1686 | Article | MR: 2996476

[21] Jérémy Omer; Douglas S. Gonçalves An integer programming approach for the search of discretization orders in distance geometry problems, Optim. Lett., Volume 14 (2020) no. 2 | Article | MR: 4064458 | Zbl: 1442.90131

[22] Jérémy Omer; Tangi Migot Vertex ordering with optimal number of adjacent predecessors, Discrete Math. Theor. Comput. Sci., Volume 22 (2019) no. 1, 1, 20 pages | MR: 4054362 | Zbl: 1450.05015

[23] Donald J. Rose; R. Endre Tarjan; George S. Lueker Algorithmic aspects of vertex elimination on graphs, SIAM J. Comput., Volume 5 (1976) no. 2, pp. 266-283 | Article | MR: 408312 | Zbl: 0353.65019

Cited by Sources: