Optimal Cycle Selections: An Experimental Assessment of Integer Programming Formulations

In this paper, we conduct numerical experiments to test the effectiveness of several integer programming formulations of the cycle selection problem. Specifically, we carry out experiments to identify a maximum weighted cycle selection in random or in structured digraphs. The results show that random instances are relatively easy and that two formulations outperform the other ones in terms of total running time. We also examine variants of the problem obtained by adding a budget constraint and/or a maximum cycle length constraint. These variants are more challenging, especially when a budget constraint is imposed. To investigate the cycle selection problem with a maximum cycle length equal to 3, we provide an arc-based formulation with an exponential number of constraints that can be separated in polynomial time. All inequalities in the formulation are facet-defining for complete digraphs.