  


A polyhedral study of the cardinality constrained multicycle and multichain problem on directed graphs for kidney exchange optimization
V MakHau (vicky.makdeakin.edu.au) Abstract: The Cardinality Constrained Multicycle 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 relaxationbased branchandbound framework where at each node of the branchandbound 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 branchandpriceandcut 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 201601, School of Information Technology, Deakin University, Waurn Ponds, Geelong, Vic 3216, Australia., March 2016 Download: [PDF] Entry Submitted: 03/15/2016 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  