You are not logged in.

Polyhedral results for the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Cardinality Constrained Cycles and Chains Problem (CCCCP)

Mak-Hau, V. 2015, Polyhedral results for the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Cardinality Constrained Cycles and Chains Problem (CCCCP), in MODSIM 2015 : Proceedings of the 21st International Congress on Modelling and Simulation, Modelling and Simulation Society of Australia and New Zealand, [Canberra, A.C.T.], pp. 1773-1779.

Attached Files
Name Description MIMEType Size Downloads

Title Polyhedral results for the Cardinality Constrained Multi-cycle Problem (CCMcP) and the Cardinality Constrained Cycles and Chains Problem (CCCCP)
Author(s) Mak-Hau, V.ORCID iD for Mak-Hau, V. orcid.org/0000-0002-9306-5780
Conference name Modelling and Simulation. International Congress (21st : 2015 : Gold Coast, Queensland)
Conference location Gold Coast, Queensland
Conference dates 29 Nov. - 4 Dec. 2015
Title of proceedings MODSIM 2015 : Proceedings of the 21st International Congress on Modelling and Simulation
Editor(s) Weber, T.
McPhee, M.J.
Anderssen, R.S.
Publication date 2015
Start page 1773
End page 1779
Total pages 7
Publisher Modelling and Simulation Society of Australia and New Zealand
Place of publication [Canberra, A.C.T.]
Keyword(s) integer programming
combinatorial optimization
cardinality constrained cycle problems
kidney exchange
clearing barter exchange
Summary In recent years, there has been studies on the cardinality constrained multi-cycle problems on directed graphs, some of which considered chains co-existing on the same digraph whilst others did not. These studies were inspired by the optimal matching of kidneys known as the Kidney Exchange Problem (KEP). In a KEP, a vertex on the digraph represents a donor-patient pair who are related, though the kidney of the donor is incompatible to the patient. When there are multiple such incompatible pairs in the kidney exchange pool, the kidney of the donor of one incompatible pair may in fact be compatible to the patient of another incompatible pair. If Donor A’s kidney is suitable for Patient B, and vice versa, then there will be arcs in both directions between Vertex A to Vertex B. Such exchanges form a 2-cycle. There may also be cycles involving 3 or more vertices. As all exchanges in a kidney exchange cycle must take place simultaneously, (otherwise a donor can drop out from the program once his/her partner has received a kidney from another donor), due to logistic and human resource reasons, only a limited number of kidney exchanges can occur simultaneously, hence the cardinality of these cycles are constrained. In recent years, kidney exchange programs around the world have altruistic donors in the pool. A sequence of exchanges that starts from an altruistic donor forms a chain instead of a cycle. We therefore have two underlying combinatorial optimization problems: Cardinality Constrained Multi-cycle Problem (CCMcP) and the Cardinality Constrained Cycles and Chains Problem (CCCCP). The objective of the KEP is either to maximize the number of kidney matches, or to maximize a certain weighted function of kidney matches. In a CCMcP, a vertex can be in at most one cycle whereas in a CCCCP, a vertex can be part of (but in no more than) a cycle or a chain. The cardinality of the cycles are constrained in all studies. The cardinality of the chains, however, are considered unconstrained in some studies, constrained but larger than that of cycles, or the same as that of cycles in others. Although the CCMcP has some similarities to the ATSP- and VRP-family of problems, there is a major difference: strong subtour elimination constraints are mostly invalid for the CCMcP, as we do allow smaller subtours as long as they do not exceed the size limit. The CCCCP has its distinctive feature that allows chains as well as cycles on the same directed graph. Hence, both the CCMcP and the CCCCP are interesting and challenging combinatorial optimization problems in their own rights. Most existing studies focused on solution methodologies, and as far as we aware, there is no polyhedral studies so far. In this paper, we will study the polyhedral structure of the natural arc-based integer programming models of the CCMcP and the CCCCP, both containing exponentially many constraints. We do so to pave the way for studying strong valid cuts we have found that can be applied in 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 strong valid cuts dualized into the objective function and the dual multipliers optimised by subgradient optimisation.
ISBN 9780987214355
Language eng
Field of Research 010206 Operations Research
080202 Applied Discrete Mathematics
080199 Artificial Intelligence and Image Processing not elsewhere classified
Socio Economic Objective 920499 Public Health (excl. Specific Population Health) not elsewhere classified
HERDC Research category E1 Full written paper - refereed
ERA Research output type E Conference publication
Copyright notice ©2015, Modelling and Simulation Society of Australia and New Zealand
Persistent URL http://hdl.handle.net/10536/DRO/DU:30080602

Document type: Conference Paper
Collections: School of Information Technology
Deposit Agreements needed
Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 114 Abstract Views, 1 File Downloads  -  Detailed Statistics
Created: Thu, 23 Jun 2016, 15:31:11 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.