An Exact Framework for the Trigger Arc Traveling Salesman Problem - Miní, Miguel; Silva, Lucas de Oliveira; Miyazawa, Flávio K. (Anais do Encontro de Teoria da Computação (ETC), 2026)
The Trigger Arc Traveling Salesman Problem generalizes the classical TSP by introducing dynamically evolving arc costs that are modified upon traversal of designated “trigger” arcs. Thus, each arc’s cost is determined by the most recently traversed trigger arc that affects it, leading to an order-dependent cost. Such a structure makes an explicit modeling of trigger arcs computationally expensive, even for moderately sized instances. We propose an exact framework based on a standard MIP formulation of TSP, using classic rounding heuristics, together with a callback to separate trigger violations in candidate tours. Also, to control model size, we incorporate triggers progressively only as needed. The proposed approach solves several benchmark instances from the literature to optimality and achieves single-digit optimality gaps on a subset of larger instances.