New strategy for anti‑loop formulations

Abstract

This paper presents a strategy based on binary labelling of nodes for the creation of anti-loop formulations from existing strategies. This strategy prevents by default the formation of odd cycles, therefore it can have important role in iterative procedures based on generating subtour elimination constraints. It can also be used to modify the classic strategies used in problems associated to graphs. In this paper we focus on this last application. The behavior of this strategy is analyzed with two problems associated with graphs, the Asymmetric Traveling Salesman Problem (ATSP) and the Steiner Problem, where two configurations that modify the Miller-Tucking-Zem- lig proposal to avoid cycles are compared. The experimental analysis shows that this strategy keep a good convergence, highlighting its use for the Steiner problem.