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.

A Critical Review of the Harm Minimization Ideology in Australia

Harm minimization as a drug-policy approach represents a major step forward in Australian society's method of dealing with the myriad problems associated with illicit drug use. However, harm minimization lacks a substantial theoretical underpinning and there has been little debate about harm minimization at the sociological level. This article investigates a number of the assertions made within the harm minimization literature and the assumptions on which they are based. These assumptions are critically deconstructed from a number of points of view, including a Foucauldian perspective. Areas investigated include: the use of epidemiological data as a foundation for many harm-reduction strategies, the failure of harm minimization theories to deal adequately with the role of discourse in the drug policy arena, the harm minimization claim to amorality, the use of a utilitarian set of values, the supposed popularity of harm reduction and the idea that the current harm-reduction paradigm clearly acts as an extension of 'surveillance medicine' through the vehicle of governmentality. It is concluded that, whilst harm minimization represents the most promising advance in drug policy in the past, the lack of theoretical rigour in the development of these initiatives results in many of the claims made by proponents of harm-reduction strategies being either overly optimistic or fundamentally flawed.

Constrained pole placement for linear systems using low-order output feedback controllers

The paper presents a simple approach to the problem of designing low-order output feedback controllers for linear continuous systems. The controller can place all of the closed-loop poles within a circle, C(- , 1/ β) , with centre at - and radius of 1/ β in the left half s-plane. The design method is based on transformation of the original system and then applying the bounded-real-lemma to the transformed system. It is shown that subjected to the solvability of an algebraic Riccati equation (ARE), output feedback controllers can then be systematically derived. Furthermore, the order of the controller is low and equals only the number of the open-loop poles lying outside the circle. A step-by-step design algorithm is given. Numerical examples are given to illustrate the design method.

Steric control over molecular structure and supramolecular association exerted by tin- and ligand-bound groups in diorganotin carboxylates

Structural data (X-ray and solution and solid-state ^₁₁₉Sn NMR) show that skew-trapezoidal-bipyramidal diorganotin compounds of 2-quinaldate are invariably monomeric, owing to the steric bulk of the carboxylate ligand. In contrast, most of the analogous compounds of 2-picolinate (2-pic) can increase their coordination number by polymerization or the incorporation of solvent in their coordination sphere in the solid state. The exceptional compound is tBu₂Sn(2-pic)₂ (3), for which no increase in coordination number is apparent, a result that is correlated with the bulky tert-butyl groups. Thus, judicious choice of tin or ligand substituents can be exploited to dictate coordination number and/or the degree of supramolecular aggregation in the investigated systems.

Cutting angle method - a tool for constrained global optimization

Cutting angle method (CAM) is a deterministic global optimization technique applicable to Lipschitz functions f: Rn → R. The method builds a sequence of piecewise linear lower approximations to the objective function f. The sequence of solutions to these relaxed problems converges to the global minimum of f. This article adapts CAM to the case of linear constraints on the feasible domain. We show how the relaxed problems are modified, and how the numerical efficiency of solving these problems can be preserved. A number of numerical experiments confirms the improved numerical efficiency.

Scheduling of a parallel computation-bound application and sequential applications executing concurrently on a cluster - a case study

Studies have shown that most of the computers in a non-dedicated cluster are often idle or lightly loaded. The underutilized computers in a non-dedicated cluster can be employed to execute parallel applications. The aim of this study is to learn how concurrent execution of a computation-bound and sequential applications influence their execution performance and cluster utilization. The result of the study has demonstrated that a computation-bound parallel application benefits from load balancing, and at the same time sequential applications suffer only an insignificant slowdown of execution. Overall, the utilization of a non-dedicated cluster is improved.

Polyhedral combinatorics of the cardinality constrained quadratic knapsack problem and the quadratic selective travelling salesman problem

This paper considers the Cardinality Constrained Quadratic Knapsack Problem (QKP) and the Quadratic Selective Travelling Salesman Problem (QSTSP). The QKP is a generalization of the Knapsack Problem and the QSTSP is a generalization of the Travelling Salesman Problem. Thus, both problems are NP hard. The QSTSP and the QKP can be solved using branch-and-cut methods. Good bounds can be obtained if strong constraints are used. Hence it is important to identify strong or even facet-defining constraints. This paper studies the polyhedral combinatorics of the QSTSP and the QKP, i.e. amongst others we identify facet-defining constraints for the QSTSP and the QKP, and provide mathematical proofs that they do indeed define facets.

Design of scalar functional observers of order less than (v-1)

This paper presents a new method of designing scalar functional observers of order less than the well-known upper bound (ν - 1). A condition for the existence of observers of order p where 1 ≤ p ≤ (ν - 1) is given. A simple and effective algorithm for solving the constrained generalized Sylvester equation is proposed. Several numerical examples are given to illustrate the attractiveness of the design algorithm.

Truth is God harm minimization through the practice of ecologically sustainable design and buddhism

The emergence of the global ecological crisis is presenting unique opportunities for the coordination of ethical thinking across cultural boundaries. Harm minimization as an ethical imperative operates as the ‘modus operandi’ behind both Ecologically Sustainable Design (ESD) and Buddhist practice. The architectural response to ESD is founded upon the ‘Declaration of Interdependence for a Sustainable Future’ adopted in 1993 by the International Union of Architects, of which the RAIA is a member.

Buddhism is a response to existential concerns universal to humanity. It developed as a set of principles for personal transformation known as the Four Noble Truths elucidated two and a half thousand years ago. Buddhist meditation practise ‘interrupts automatic patterns of conditioned behaviour’ recognised as the major obstacle to be overcome in any programme for change. Unsustainable egocentric behaviour is considered fundamental to our global ecological crisis and calls for radical behavioural change are increasingly being heard at the professional as well as the personal level. Emerging synergies between the Western cognitive sciences and Buddhist study of the mind increasingly validate the Tibetan Buddhist mind development phenomenon. Buddhists argue that their programme for enhancing ethical behaviour through mind development is a step-by step process of observation and analysis built upon empirical observation – a fundamental pre-requisite of any ‘scientific’ enquiry. Collaborative research programmes currently underway are an attempt to re-interpret Buddhist meditation techniques within a framework acceptable to Western scientific understanding. A truly holistic approach to harm minimization requires its consideration.

Determination of lower-bound ductility for AZ31 magnesium alloy by use of the bulge specimens

Despite the high demand for industrial applications of magnesium, the forming technology for wrought magnesium alloys is not fully developed due to the limited ductility and high sensitivity to the processing parameters. The processing window for magnesium alloys could be significantly widened if the lower-bound ductility (LBD) for a range of stresses, temperature, and strain rates was known. LBD is the critical strain at the moment of fracture as a function of stress state and temperature. Measurements of LBD are normally performed by testing in a hyperbaric chamber, which is highly specialized, complex, and rare equipment. In this paper an alternative approach to determine LBD is demonstrated using wrought magnesium alloy AZ31 as an example. A series of compression tests of bulge specimens combined with finite element simulation of the tests were performed. The LBD diagram was then deduced by backward calculation.

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.