Shortest paths with exclusive-disjunction arc pairs conflicts

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.