Shortest paths with exclusive-disjunction arc pairs conflicts. (English) Zbl 1542.90237
Summary: In this paper, a NP-hard variant of the shortest path problem, involving exclusive-disjunction arc pairs conflicts, is introduced. In this framework, a conflict is violated and a penalty has to be paid if either both the arcs in a pair or none of them are selected. The aim is to find a path for which the overall cost, defined as the sum of the costs of the traversed arcs and the penalties of the violated conflicts, is minimized. The proposed variant is used to model web applications test planning scenarios, where a path represents a sequence of web pages and hyperlinks. A proof of the NP-hardness is provided and two mathematical programming formulations are proposed for the problem. The former is an integer linear program relying on auxiliary variables to model conflict violations, while the latter is characterized by a nonlinear objective function, that uses only the arc variables to derive the penalties associated to the violated conflicts. To solve the problem, a two-stage matheuristic algorithm is also presented and its performances are compared with those provided by the best formulation solved by CPLEX.
MSC:
| 90C35 | Programming involving graphs or networks |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Software:
CPLEXReferences:
| [1] | Adamic, L. A., The small world web, Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 1696, 443-452 (1999) |
| [2] | Ahmed, M.; Lubiw, A., Shortest paths avoiding forbidden subpaths, Networks, 61, 4, 322-334 (2013) · Zbl 1269.90086 |
| [3] | Akbari, S.; Liaghat, V.; Nikzad, A., Colorful paths in vertex coloring of graphs, Electron. J. Combin., 18, 1, 1-9 (2011) · Zbl 1290.05070 |
| [4] | Akçay, M. B.; Akcan, H.; Evrendilek, C., All colors shortest path problem on trees, J. Heuristics, 24, 4, 617-644 (2018) |
| [5] | Albert, R.; Jeong, H.; Barabási, A.-L., Diameter of the world-wide web, Nature, 401, 6749, 130-131 (1999) |
| [6] | Blanco, M.; Borndörfer, R.; Brückner, M.; Hoàng, N. D.; Schlechte, T., On the path avoiding forbidden pairs polytope, Electron. Notes Discrete Math., 50, 343-348 (2015), LAGOS’15 - VIII Latin-American Algorithms, Graphs and Optimization Symposium · Zbl 1347.05100 |
| [7] | Carrabs, F., Cerulli, R., Festa, P., Laureana, F., 2017. On the Forward Shortest Path Tour Problem. In: Springer Proceedings in Mathematics and Statistics, vol. 217. pp. 529-537. |
| [8] | Carrabs, F.; Cerulli, R.; Pentangelo, R.; Raiconi, A., A two-level metaheuristic for the all colors shortest path problem, Comput. Optim. Appl., 71, 2, 525-551 (2018) · Zbl 1409.90213 |
| [9] | Carrabs, F.; Cerulli, R.; Raiconi, A., A reduction heuristic for the all-colors shortest path problem, RAIRO Oper. Res., 55, S2071-S2082 (2021) · Zbl 1472.90108 |
| [10] | Cohen, J.; Italiano, G. F.; Manoussakis, Y.; Thang, N. K.; Pham, H. P., Tropical paths in vertex-colored graphs, J. Combin. Optim., 42, 3, 476-498 (2021) · Zbl 1481.90273 |
| [11] | Conallen, J., Building Web Applications with UML (1999), Addison-Wesley |
| [12] | Di Puglia Pugliese, L.; Ferone, D.; Festa, P.; Guerriero, F., Shortest path tour problem with time windows, European J. Oper. Res., 282, 1, 334-344 (2020) · Zbl 1430.90542 |
| [13] | Ferone, D.; Festa, P.; Guerriero, F., An efficient exact approach for the constrained shortest path tour problem, Optim. Methods Softw., 35, 1, 1-20 (2020) · Zbl 1433.90177 |
| [14] | Ferone, D., Festa, P., Guerriero, F., Laganà, D., The constrained shortest path tour problem. Comput. Oper. Res. 74, 64-77. · Zbl 1349.90812 |
| [15] | Ferone, D.; Festa, P.; Salani, M., Branch and bound and dynamic programming approaches for the path avoiding forbidden pairs problem, (Optimization and Decision Science: ODS, Virtual Conference, November 19, 2020 (2021), Springer International Publishing: Springer International Publishing Cham), 227-235 |
| [16] | Festa, P.; Guerriero, F.; Laganà, D.; Musmanno, R., Solving the shortest path tour problem, European J. Oper. Res., 230, 3, 464-474 (2013) · Zbl 1317.90065 |
| [17] | Fortet, R., L’algebre de Boole et ses applications en recherche operationnelle, Trabajos de Estadistica, 11, 2, 111-118 (1960) · Zbl 0109.38201 |
| [18] | Furini, F.; Traversi, E., Theoretical and computational study of several linearisation techniques for binary quadratic problems, Ann. Oper. Res., 279, 1-2, 387-411 (2019) · Zbl 1434.90115 |
| [19] | Gabow, H. N.; Maheshwari, S. N.; Osterweil, L. J., On two problems in the generation of program test paths, IEEE Trans. Softw. Eng., SE-2, 3, 227-231 (1976) |
| [20] | Glover, F., Improved linear integer programming formulations of nonlinear integer problems, Manage. Sci., 22, 4, 455-460 (1975) · Zbl 0318.90044 |
| [21] | Glover, F.; Woolsey, E., Converting the 0-1 polynomial programming problem to a 0-1 linear program, Oper. Res., 22, 1, 180-182 (1974) · Zbl 0272.90049 |
| [22] | Grudin, J., The GUI shock: Computer graphics and human-computer interaction, Interactions, 13, 2, 45-47+55 (2006) |
| [23] | Hammer, P. L.; Rudeanu, S., (Boolean Methods in Operations Research and Related Areas. Boolean Methods in Operations Research and Related Areas, Ökonometrie und Unternehmensforschung Econometrics and Operations Research, vol. 7 (1968), Springer Berlin, Heidelberg) · Zbl 0155.28001 |
| [24] | Kanter, J. P., Understanding Thin-Client/Server Computing (1998), Microsoft Press |
| [25] | Khuller, S.; Lee, K.; Shayman, M., On degree constrained shortest paths, (Lecture Notes in Computer Science, vol. 3669 (2005)), 259-270 · Zbl 1162.68500 |
| [26] | Kolman, P.; Pangrác, O., On the complexity of paths avoiding forbidden pairs, Discrete Appl. Math., 157, 13, 2871-2876 (2009) · Zbl 1209.05245 |
| [27] | Kováč, J., Complexity of the path avoiding forbidden pairs problem revisited, Discrete Appl. Math., 161, 10, 1506-1512 (2013) · Zbl 1287.05071 |
| [28] | Krause, K. W.; Goodwin, M. A.; Smith, R. W., Optimal Software Test Planning Through Automated Network Analysis (1973), TRW Systems Group |
| [29] | Liberti, L., Compact linearization for binary quadratic problems, 4OR, 5, 3, 231-245 (2007) · Zbl 1211.90154 |
| [30] | Newman, M. E.J.; Watts, D. J., Renormalization group analysis of the small-world network model, Phys. Lett. A, 263, 4, 341-346 (1999) · Zbl 0940.82029 |
| [31] | Nuutila, E.; Soisalon-Soininen, E., On finding the strongly connected components in a directed graph, Inform. Process. Lett., 49, 1, 9-14 (1994) · Zbl 0787.68082 |
| [32] | Sherali, H. D.; Smith, J. C., An improved linearization strategy for zero-one quadratic programming problems, Optim. Lett., 1, 1, 33-47 (2007) · Zbl 1149.90115 |
| [33] | Srimani, P. K.; Sinha, B. P., Impossible pair constrained test path generation in a program, Inform. Sci., 28, 2, 87-103 (1982) · Zbl 0509.68062 |
| [34] | Taccari, L., Integer programming formulations for the elementary shortest path problem, European J. Oper. Res., 252, 1, 122-130 (2016) · Zbl 1346.90793 |
| [35] | Tarjan, R., Depth-first search and linear graph algorithms, SIAM J. Comput., 1, 2, 146-160 (1972) · Zbl 0251.05107 |
| [36] | Watts, D. J.; Strogatz, S. H., Collective dynamics of ‘small-world’ networks, Nature, 393, 440-442 (1998) · Zbl 1368.05139 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
