Optimization Online


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

V Mak-Hau (vicky.mak***at***deakin.edu.au)

Abstract: In this paper, we study the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Car- dinality Constrained Cycle and Chain Problem (CCCCP). A feasible solution allows one or more cardinality-constrained cycles to exist on the digraph. A vertex can only be involved in at most one cycle, and there may be vertices not involved in any cycles. The CCCCP has an additional set of vertices that can only serveľand are the only vertices that can serveľas the starting vertex of a chain. Apart from cycles, a feasible solution to the CCCCP may also contain multiple cardinality- constrained chains. A vertex can be involved in a chain or a cycle, but not both. Both of the CCMcP and the CCCCP are NP-hard. 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 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.

Keywords: integer programming, combinatorial optimisation, cardinality constrained cycle and chains, kidney exchange, clearing barter exchange

Category 1: Combinatorial Optimization (Polyhedra )

Citation: http://www.deakin.edu.au/~vicky/TechnicalReport2.pdf


Entry Submitted: 03/15/2016
Entry Accepted: 03/15/2016
Entry Last Modified: 06/13/2018

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society