Modelo de paridade e heurísticas para o problema do caminho positivo mínimo

Abstract

Given a digraph G = (V,A) with weighted arcs labeled with positive or negative signs, the Minimum Positive Path problem (Shortest Positive Path, SPP) seeks the minimum-cost path between a pair of vertices in G, subject to the constraint that the path contains an even number of negative arcs. Frequently applied in social networks to establish connections between individuals or assess their compatibility, the problem also appears in studies of relationships and influences among biological entities. This work proposes new Integer Linear Programming formulations, improves existing ones through valid inequalities and constraints derived from linear relaxations, and introduces two heuristics for the problem. The new solution approaches were evaluated on synthetic instances of small, medium, and large scale, as well as on real-world instances. For instances with arbitrary real weights, the (SP+) formulation outperforms the models in the literature in terms of running time and enables obtaining optimal solutions on larger-scale digraphs, especially when combined with the bucket heuristic. For instances with strictly positive weights, the new parity model (SPxor), based on an expanded digraph, achieved the best computational performance across all experiments conducted, being on average 94% faster than the models in the literature for the synthetic instances considered. Furthermore, incorporating the proposed heuristics into preexisting formulations consistently reduced solving times, reinforcing their robustness and general applicability. The results obtained allow large-scale SPP instances to be handled with significantly shorter computational times than those reported in the literature.