On the kidney exchange problem: cardinality constrained cycle and chain problems on directed graphs: a survey of integer programming approaches

The Kidney Exchange Problem (KEP) is a combinatorial optimization problem and has attracted the attention from the community of integer programming/combinatorial optimisation in the past few years. Defined on a directed graph, the KEP has two variations: one concerns cycles only, and the other, cycles as well as chains on the same graph. We call the former a Cardinality Constrained Multi-cycle Problem (CCMcP) and the latter a Cardinality Constrained Cycles and Chains Problem (CCCCP). The cardinality for cycles is restricted in both CCMcP and CCCCP. As for chains, some studies in the literature considered cardinality restrictions, whereas others did not. The CCMcP can be viewed as an Asymmetric Travelling Salesman Problem that does allow subtours, however these subtours are constrained by cardinality, and that it is not necessary to visit all vertices. In existing literature of the KEP, the cardinality constraint for cycles is usually considered to be small (to the best of our knowledge, no more than six). In a CCCCP, each vertex on the directed graph can be included in at most one cycle or chain, but not both. The CCMcP and the CCCCP are interesting and challenging combinatorial optimization problems in their own rights, particularly due to their similarities to some travelling salesman- and vehicle routing-family of problems. In this paper, our main focus is to review the existing mathematical programming models and solution methods in the literature, analyse the performance of these models, and identify future research directions. Further, we propose a polynomial-sized and an exponential-sized mixed-integer linear programming model, discuss a number of stronger constraints for cardinality-infeasible-cycle elimination for the latter, and present some preliminary numerical results.

Ideal bases in constructions defined by directed graphs

The present article continues the investigation of visible ideal bases in constructions defined using directed graphs. Our main theorem establishes that, for every balanced digraph D and each idempotent semiring R with 1, the incidence semiring ID(R) of the digraph D has a convenient visible ideal basis BD(R). It also shows that the elements of BD(R) can always be used to generate two-sided ideals with the largest possible weight among the weights of all two-sided ideals in the incidence semiring.

Rees semigroups of digraphs for classification of data

Recent research has motivated the investigation of the weights of ideals in semiring constructions based on semigroups. The present paper introduces Rees semigroups of directed graphs. This new construction is a common generalization of Rees matrix semigroups and incidence semigroups of digraphs. For each finite subsemigroup S of the Rees semigroup of a digraph and for every zero-divisor-free idempotent semiring F with identity element, our main theorem describes all ideals J in the semigroup semiring F0[S] such that J has the largest possible weight.

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

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.

Effect of a self-directed learning package on emergency nurses` knowledge of assessment of oxygenation and use of supplemental oxygen

Abstract Emergency nurses frequently and independently make decisions regarding supplemental oxygen. The importance of these decisions for patients is highlighted by the well documented association between respiratory dysfunction and adverse events. This study aimed to: (i) examine the effect of educational preparation on emergency nurses' knowledge of assessment of oxygenation, and the use of supplemental oxygen; (ii) explore the impact of existing knowledge on decisions related to the implementation of supplemental oxygen; and (iii) explore nurses' characteristics that were associated with effectiveness of the educational preparation. A pretest/post-test, controlled, quasi-experimental design was used in this study. Educational preparation was effective in increasing emergency nurses' knowledge. Baseline level of knowledge was predictive of reports of independent decisions regarding the implementation of oxygen. There was a significant positive relationship between postgraduate qualification in emergency nursing and the effect of education, and significant negative relationships between effect of education and baseline level of knowledge and daily decisions to implement supplemental oxygen.

Groups, graphs and mutually unbiased bases

A new characteristic free approach to constructing large sets of mutually unbiased bases in Hilbert space is developed. We associate with a seed set of bases a finite subgroup of which defines a strongly regular graph. Large sets of mutually unbiased bases are obtained as the cliques of the graph.

New cutting-planes for the time-and/or precedence-constrained ATSP and directed VRP

In this paper, we introduce five classes of new valid cutting planes for the precedence-constrained (PC) and/or time-window-constrained (TW) Asymmetric Travelling Salesman Problems (ATSPs) and directed Vehicle Routing Problems (VRPs). We show that all five classes of new inequalities are facet-defining for the directed VRP-TW, under reasonable conditions and the assumption that vehicles are identical. Similar proofs can be developed for the VRP-PC. As ATSP-TW and PC-ATSP can be formulated as directed identical-vehicle VRP-TW and PC-VRP, respectively, this provides a link to study the polyhedral combinatorics for the ATSP-TW and PC-ATSP. The first four classes of these new cutting planes are cycle-breaking inequalities that are lifted from the well-known D^-_k and D⁺_k inequalities (see Grötschel and Padberg in Polyhedral theory. The traveling salesman problem: a guided tour of combinatorial optimization, Wiley, New York, 1985). The last class of new cutting planes, the TW ₂ inequalities, are infeasible-path elimination inequalities. Separation of these constraints will also be discussed. We also present prelimanry numerical results to demonstrate the strengh of these new cutting planes.

Leadership and learning: facilitating self-directed learning in enterprises

Purpose - To show that a key aspect of learning and development of individual employees is that of self-directedness. This paper will consider the role of the leader in facilitating workforce development in terms of employees' self-directedness for learning. The research was designed to investigate the views that 'learning leaders' in organizations have towards the development of self-directedness in employees; and to identify strategies that are feasible in developing self-directedness in operating organizations.

Design/methodology/approach - Draws on a national research project undertaken in 12 organizations in Australia, representing a range of sizes and a number of industry sectors. Data collection involved interviewing learning and development managers in each organization to gauge the relative feasibility of the implementation of a number of pre-identified strategies designed to develop self-directedness among employees within operating work environments.

Findings - Showed that: learning managers and leaders were generally well disposed towards the development of self-directedness, and some had already moved to do so; and identified a number of possible strategies for implementation of varying degrees of feasibility. The paper will consider these findings in relation to the concept of a 'learning leader'.

Research limitations/implications - Although the research was conducted in a diverse set of 12 enterprises, applicability of the results across an even wider set of enterprises would need to be tested.

Originality/value - The findings of this research provide guidance to learning and development personnel on feasible strategies to use within their own organization to assist with the development of self-directed learning among employees.

Clock synchronization state graphs based on clock precision difference

Consistent and stable global states of clock synchronization are very important in distributed and parallel systems. This paper presents an innovative strategy and method to obtain stable global clock synchronization state graphs in asynchronous Internet environments. Our model will introduce the concept of clock precision difference as a means to evaluate running states of all clocks in this system and make this system  self-adaptive well. Finally, we introduce the concept of clock precision difference into global states analysis of clock synchronization and construct clock synchronization state graphs in order to evaluate distributed clock synchronization states. We also present detailed simulations of the strategy and mathematical analysis used on real Internet environments.

A randomized trial of protocol-directed sedation management for mechanical ventilation in an Australian intensive care unit

Objective: To compare protocol-directed sedation management with traditional non-protocol-directed practice in mechanically ventilated patients. Design: Randomized, controlled trial. Setting: General intensive care unit (24 beds) in an Australian metropolitan teaching hospital. Patients: Adult, mechanically ventilated patients (n = 312). Interventions: Patients were randomly assigned to receive sedation directed by formal guidelines (protocol group, n = 153) or usual local clinical practice (control, n = 159). Measurements and Main Results: The median (95% confidence interval) duration of ventilation was 79 hrs (56-93 hrs) for patients in the protocol group compared with 58 hrs (44-78 hrs) for patients who received control care (p = .20). Lengths of stay (median [range]) in the intensive care unit (94 [2-1106] hrs vs. 88 (14-962) hrs, p = .58) and hospital (13 [1-113] days vs. 13 (1-365) days, p = .97) were similar, as were the proportions of subjects receiving a tracheostomy (17% vs. 15%, p = .64) or undergoing unplanned self-extubation (1.3% vs. 0.6%, p = .61). Death in the intensive care unit occurred in 32 (21%) patients in the protocol group and 32 (20%) control subjects (p = .89), with a similar overall proportion of deaths in hospital (25% vs. 22%, p = .51). A Cox proportional hazards model, after adjustment for age, gender, Acute Physiology and Chronic Health Evaluation II score, diagnostic category, and doses of commonly used drugs, estimated that protocol sedation management was associated with a 22% decrease (95% confidence interval 40% decrease to 2% increase, p = .07) in the occurrence of successful weaning from mechanical ventilation. Conclusions: This randomized trial provided no evidence of a substantial reduction in the duration of mechanical ventilation or length of stay, in either the intensive care unit or the hospital, with the use of protocol-directed sedation compared with usual local management. Qualified high-intensity nurse staffing and routine Australian intensive care unit nursing responsibility for many aspects of ventilatory practice may explain the contrast between these findings and some recent North American studies. (C) 2008 Lippincott Williams & Wilkins, Inc.

Experiences of disability consumer-directed care users in Australia : results from a longitudinal qualitative study

The rapidly growing body of literature suggests that Consumer-directed Care (CDC) has the potential to empower consumers and improve the flexibility and quality of care. However, reports highlighting quality and risk concerns associated with CDC focusing on a longer time frame have been few. This paper presents the findings from a qualitative longitudinal evaluation of an Australian CDC programme. Focusing on the period between 2003 and 2008, it reports on the experiences of 12 families caring for a dependent family member. It is based on two external evaluations completed 6 and 36 months after enrolment, and one internal evaluation completed 48 months after enrolment. The findings were triangulated with internal memos, reports and minutes of meetings, as well as with the theoretical literature. The study demonstrates that CDC harbours considerable benefits for people with disabilities and their carers. However, the study also suggests that, over time, carers may experience an increased sense of isolation and lack of support as a result of their involvement in the CDC programme. The paper argues that the development of safeguards addressing these weaknesses is crucial for the sustainability of CDC programmes in contexts where risk cannot be simply transferred onto consumers.

Consumer participation in designing community based consumer-directed disability care : lessons from a participatory action research-inspired project

User participation has been embraced worldwide as a means to provide better consumer outcomes in health and community care. However, methodologies to achieve effective consumer engagement at the programme design level have remained under-explored. The purpose of this study was to evaluate the impact of a Participatory Action Research (PAR)-inspired methodology used to develop a consumer-directed community care/individualised funding service model for people with disabilities. A retrospective analysis of case notes and internal reports for the first 6 years of an ongoing project were examined. The findings suggest that PAR methodologies need to take into account community development, group support, and capacity building as well as succession planning and risk management issues in order to facilitate the often lengthy policy and project development process. Drawing on these findings, this article discusses five lessons and their methodological implications for PAR in a health or social policy/programme design context.