A polyhedral study of the cardinality constrained multi-cycle and multi-chain problem on directed graphs

This paper focuses on the polyhedral study of the arc-based formulations for both problems. We prove that 3 classes of constraints are facet-defining for the CCMcP polytope, identify 4 new classes of constraints and prove their validity. We then prove that the non-negativity and the degree constraints are facet-defining for the CCCCP polytope. Even though we cannot expect to find a complete polyhedral description (CPD) of the CCMcP or the CCCCP, as both problems are NP-hard, any partial description is always interesting for both theoretical and computational purposes, since the wider the linear description, the less need for branching. A CPD is composed of facet-defining constraints, hence the major contribution of this paper is one step towards finding a CPD for the CCMcP and the CCCCP. We tested the strengths of the facet-defining constraints and new valid constraints on two sets of randomly generated data instances. We reported the numerical results and discussed future research directions.