Optimization Online


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

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

Abstract: The Cardinality Constrained Multi-cycle Problem (CCMcP) and the Cardinality Constrained Cycle and Chain Problem (CCCCP) are both combinatorial optimisation problems defined on directed graphs. They have attracted the attention of the combinatorial optimisation community due to the application in kidney exchange and barter exchange optimisation. Consider a digraph where each arc is associated with a weight. A feasible solution of a CCMcP allows multiple cycles on the digraph, but the cardinality of these cycles are constrained by K, for K ≥ 2. It is not required that all vertices be involved in the cycles. The objective is to maximise the sum of the weights of arcs used in the cycles. The digraph of a CCCCP, on the other hand, partition the set of vertices into N and P . Cycles are allowed in the set of P like the way they are in a CCMcP. Chains, on the other hand, must begin from a vertex in N, then immediately travel to a vertex in P, may or may not visit other vertices in P, but must end at a vertex in P. The cardinality of a chain is constrained by L, for L ≥ 2. There can be multiple chains as well as multiple cycles on a CCCCP, each vertex can be involved in at most one cycle or chain, not both. Again, it is not required that all vertices be visited. The objective is to maximise the sum of the weights of arcs used in the cycles and chains. To the best of our knowledge, there is no polyhedral studies so far for the CCMcP and the CCCCP, hence the motivation of this paper. We do so in the hope of finding strong valid cuts in order to apply a Lagrangean relaxation-based branch-and-bound framework where at each node of the branch-and-bound tree, we may be able to obtain a relaxation that can be solved in polynomial time, with the strong cuts dualised into the objective function and the dual multipliers optimised by subgradient optimisation. Such an exact method has demonstrated computational superiority than a branch-and-price-and-cut exact method in the context of Asymmetric Travelling Salesman Problem with Replenishment Arcs. As preliminary results, we implemented the strong cuts we have found by completely enumerating all cardinality violation constraints for small K, and the results are promising. Optimal solutions for up to |P| = 389 and |N| = 2 are found within 18.81 seconds.

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

Category 1: Combinatorial Optimization (Polyhedra )

Citation: Technical Report 2016-01, School of Information Technology, Deakin University, Waurn Ponds, Geelong, Vic 3216, Australia., March 2016

Download: [PDF]

Entry Submitted: 03/15/2016
Entry Accepted: 03/15/2016
Entry Last Modified: 01/11/2017

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