M. Baratto, Y. Crama
The following "cycle selection problem" is motivated by an application to kidney exchange problems. For a digraph 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. We prove that MWCS is strongly NP-hard.
Next, we focus on the cycle selection problem associated with a complete digraph. 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, and three extended ones. We investigate the relative strength of these formulations. We next concentrate on the natural formulation and on the description of the associated polytope. We prove that it is full-dimensional, and that all the inequalities used in the ILP formulation are facet defining. Furthermore, we describe three new classes of facet-defining inequalities. 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.
Keywords: Graphs, Integer Programming, Polyhedral Combinatorics,
Scheduled
FA1 Graphs and Networks 1
June 11, 2021 9:15 AM
1 - GB Dantzig
