Selecting directed cycles: a polyhedral study

Given a directed graph G, a cycle selection is a subset of arcs of G forming a union of directed cycles. When the arcs are weighted, the Maximum Weighted Cycle Selection (MWCS) problem consists in finding a cycle selection of maximum total weight.
These definitions are motivated by an application to the kidney exchange problem where patients are incompatible with their associated donor, but can possibly receive a kidney from another donor. Given many such patient/donor pairs, various matching algorithms can be used to maximize the number of feasible transplants by finding exchange cycles in appropriately defined compatibility digraphs. One of the remaining issues is that the actual compatibility between a donor and a patient can only be completely tested after an intended transplant cycle has been identified. Hence, incompatibilities may reveal themselves a posteriori and some exchange cycles turn out not be implementable. A way to tackle this issue is to first select a subset of arcs to be tested, and then to run a matching algorithm. A better understanding of the cycle selection problem may help to address the first step of this procedure.
In our study, we focus on the cycle selection problem associated with a complete digraph. First, we establish that MWCS is strongly NP-hard. Next, we provide four complete ILP formulations of the problem: a "natural" one, featuring an exponential number of constraints which can be separated in polynomial time, one extended non compact formulation and two extended compact ones. We investigate the relative strength of these formulations. We next concentrate on the natural formulation and on the description of the associated selection polytope. We prove that it is full-dimensional, and that all the inequalities used in the IP formulation are facet-defining. Furthermore, we describe three new classes of facet-defining inequalities. Then, we numerically test the proposed ILP formulation of MWCS. Despite the theoretical complexity of the problem, the ILP formulation is very quickly solved for many random instances. We also study the problem when we include an additional constraint on the cardinality of a cycle selection. Most of the results proved for the original case remain valid, but numerical tests show that the ILP formulation of the constrained variant is harder to solve.