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.

Real-time traffic flow statistical analysis based on network-constrained moving object trajectories

In this paper, we propose a novel traffic flow analysis method, Network-constrained Moving Objects Database based Traffic Flow Statistical Analysis (NMOD-TFSA) model. By sampling and analyzing the spatial-temporal trajectories of network constrained moving objects, NMOD-TFSA can get the real-time traffic conditions of the transportation network. The experimental results show that, compared with the floating-car methods which are widely used in current traffic flow analyzing systems, NMOD-TFSA provides an improved performance in terms of communication costs and statistical accuracy.

Robust nonlinear adaptive backstepping excitation controller design for rejecting external disturbances in multimachine power systems

This paper proposes a new approach to design a robust adaptive backstepping excitation controller for multimachine power systems in order to reject external disturbances. The parameters which significantly affect the stability of power systems (also called stability sensitive parameters) are considered as unknown and the external disturbances are incorporated into the power system model. The proposed excitation controller is designed in such a way that it is adaptive to the unknown parameters and robust to external disturbances. The stability sensitive parameters are estimated through the adaptation laws and the convergences of these adaptation laws are obtained through the negative semi-definiteness of control Lyapunov functions (CLFs). The proposed controller not only provides robustness property against external disturbances but also overcomes the over-parameterization problem of stability sensitive parameters which usually appears in some conventional adaptive methods. Finally, the performance of the proposed controller is tested on a two-area four machine 11-bus power system by considering external disturbances under different scenarios and is compared to that of an existing nonlinear adaptive backstepping controller. Simulation results illustrate the robustness of the proposed controller over an existing one in terms of rejecting external disturbances.

An alternative LQR-based excitation controller design for power systems to enhance small-signal stability

This paper presents a new approach to design excitation controller for power systems to enhance small-signal stability. Partial feedback linearization scheme is used to design the controller for a linearized power system model which transforms a part of this model into a new system through linear coordinate transformation. In this paper, the excitation control law as a function of state variables is determined from the dynamics of the partly transformed new system provided that the controller stabilizes the remaining dynamics of the system which are not transformed through feedback linearization. The stability of the remaining dynamics is also discussed in this paper. Since the proposed control scheme uses state variables as feedback, it is analogous to a linear quadratic regulator (LQR) based excitation controller. Therefore, the performance of the proposed scheme is evaluated on a single machine infinite bus (SMIB) system and compared to that of an LQR controller.

Characteristics evaluation of a μ-Synthesis H∞ controller for a grid-connected three-phase photovoltaic system

This paper presents a μ-Synthesis H∞ Controller for regulating the switching signal of the inverter connected with a three-phase photovoltaic (PV) system. To facilitate the control design, the system is represented in terms of state space realization with uncertainties. The control design involves selecting proper weighting functions and performing synthesis. The controller order is reduced by Henkel-norm method. Simulations are carried out to evaluate the characteristics of the controller under parametric uncertainties. It is found out that the proposed controller is inherently stable, possesses significantly small tracking error, and preserves nominal performance, robust stability and robust performance for the grid-connected three-phase PV system.

Characteristics evaluation of an LMI-synthesis H∞ controller for a superconducting magnetic energy systems applied in power systems

© 2015 IEEE.This paper presents an H« controller synthesised based on linear matrix inequalities (LMI) for a current source converter based superconducting magnetic energy systems (SMESs) connected to a node of power systems where the regulation of grid current has considered as a control objective. To facilitate the control design, the system is represented in terms of state space realization with uncertainties. The control design involves selecting proper weighting functions and performing LMI-synthesis. The controller order is reduced by Henkel-norm method. Simulations are carried out to evaluate the characteristics of the controller under parametric uncertainties. It is found out that the proposed controller is inherently stable, possesses significantly small tracking error, and preserves robust performance for the SMES.

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 new genetic algorithm based on modified Physarum network model for bandwidth-delay constrained least-cost multicast routing

A mobile ad hoc network is a kind of popular self-configuring network, in which multicast routing under the quality of service constraints, is a significant challenge. Many researchers have proved that such problem can be formulated as a NP-complete problem and proposed some swarm-based intelligent algorithms to solve the optimal solution, such as the genetic algorithm (GA), bees algorithm. However, a lower efficiency of local search ability and weak robustness still limit the computational effectiveness. Aiming to those shortcomings, a new hybrid algorithm inspired by the self-organization of Physarum, is proposed in this paper. In our algorithm, an updating scheme based on Physarum network model (PM) is used for improving the crossover operator of traditional GAs, in which the same parts of parent chromosomes are reserved and the new offspring by the PM is generated. In order to estimate the effectiveness of our proposed optimized scheme, some typical genetic algorithms and their updating algorithms (PMGAs) are compared for solving the multicast routing on four different datasets. The simulation experiments show that PMGAs are more efficient than original GAs. More importantly, the PMGAs are more robustness that is very important for solving the multicast routing problem. Moreover, a series of parameter analyses is used to find a set of better setting for realizing the maximal efficiency of our algorithm.

Robust adaptive backstepping controller design for DC-DC buck converters with external disturbances

In modern power electronic systems, DC-DC converter is one of the main controlled power sources for driving DC systems. But the inherent nonlinear and time-varying characteristics often result in some difficulties mostly related to the control issue. This paper presents a robust nonlinear adaptive controller design with a recursive methodology based on the pulse width modulation (PWM) to drive a DC-DC buck converter. The proposed controller is designed based on the dynamical model of the buck converter where all parameters within the model are assumed as unknown. These unknown parameters are estimated through the adaptation laws and the stability of these laws are ensured by formulating suitable control Lyapunov functions (CLFs) at different stages. The proposed control scheme also provides robustness against external disturbances as these disturbances are considered within the model. One of the main features of the proposed scheme is that it overcomes the over-parameterization problems of unknown parameters which usually appear in some conventional adaptive methods. Finally, the effectiveness of the proposed control scheme is verified through the simulation results and compared to that of an existing adaptive backstepping controller. Simulation results clearly indicate the performance improvement in terms of a faster output voltage tracking response.

Robust partial feedback linearizing excitation controller design for multimachine power systems

This paper presents a new robust nonlinear excitationcontroller design for synchronous generators in multimachine powersystems to enhance the transient stability. The mismatches betweenthe original power system model and formulated mathematical modelare considered as uncertainties which are modeled through thesatisfaction of matching conditions. The exogenous noises appearingfrom measurements are incorporated with the power system modelincluding the two-axis model of synchronous generators. The partialfeedback linearization technique is used to design the controller whichtransforms the original nonlinear multimachine power system modelinto several reduced-order linear and autonomous subsystems. Thedesired control law is obtained for each subsystem and implemented ina decentralized manner provided that the dynamics of the autonomoussubsystems have no effects on the overall stability of the system. Theanalysis related to the dynamics of noisy autonomous subsystems isalso included and the proposed controller has the excellent capabilityto decouple these noises. Finally, the performance of the proposedcontrol scheme is evaluated on an IEEE 39-bus benchmark powersystem following different types of large disturbances. The performanceof the proposed controller is compared to that of a partialfeedback linearizing controller, which is designed without robustnessproperties, to verify the effectiveness of the proposed control scheme.

Transient stability enhancement of multimachine power systems using nonlinear observer-based excitation controller

This paper presents an approach to design a nonlinear observer-based excitation controller for multimachine power systems to enhance the transient stability. The controller is designed based on the partial feedback linearization of a nonlinear power system model which transforms the model into a reducedorder linear one with an autonomous dynamical part. Then a linear state feedback stabilizing controller is designed for the reduced-order linear power system model using optimal control theory which enhances the stability of the entire system. The states of the feedback stabilizing controller are obtained from the nonlinear observer and the performance of this observer-based controller is independent of the operating points of power systems. The performance of the proposed observer-based controller is compared to that of an exact feedback linearizing observer-based controller and a partial feedback linearizing controller without observer under different operating conditions.

Nonlinear DSTATCOM controller design for distribution network with distributed generation to enhance voltage stability

This paper presents a nonlinear controller design for a DSTATCOM connected to a distribution network with distributed generation (DG) to regulate the line voltage by providing reactive power compensation.The controller is designed based on the partial feedback linearization which transforms the nonlinear system into a reduced-order linear system and an autonomous system whose dynamics are known as internal dynamics of the system. This paper also investigates the stability of internal dynamics of a DSTATCOM as it is a basic requirement to design partial feedback linearizing controllers. The performance of the proposed controller is evaluated in terms reactive power compensation to enhance the voltage stability of distribution with DG.

Nonlinear adaptive backstepping controller design for controlling bidirectional power flow of BESSs in DC microgrids

In this paper, a nonlinear adaptive backstepping controlleris designed to control the bidirectional power flow (charging/discharging) of battery energy storage systems (BESSs) in a DCmicrogrid under different operating conditions. The controller isdesigned in such a manner that the BESSs can store the excess energyfrom the renewable energy sources (RESs) in a DC microgrid aftersatisfying the load demand and also feeding back the stored energyto the load when RESs are not sufficient. The proposed controller isalso designed to maintain a constant voltage at the DC bus, whereall components of DC microgrids are connected, while controllingthe power flow of BESSs. This paper considers solar photovoltaic(PV) systems as the RES whereas a diesel generator equipped witha rectifier is used as a backup supply to maintain the continuity ofpower supply in the case of emergency situations. The controller isdesigned recursively based on the Lyapunov control theory whereall parameters within the model of BESSs are assumed to beunknown. These unknown parameters are then estimated throughthe adaptation laws and whose stability is ensured by formulatingsuitable control Lyapunov functions (CLFs) at different stages ofthe design process. Moreover, a scheme is also presented to monitorthe state of charge (SOC) of the BESS. Finally, the performanceof the proposed controller is verified on a test DC microgrid undervarious operating conditions. The proposed controller ensures the DCbus voltage regulation within the acceptable limits under differentoperating conditions.

Ellipsoidal neighbourhood outlier factor for distributed anomaly detection in resource constrained networks

Anomaly detection in resource constrained wireless networks is an important challenge for tasks such as intrusion detection, quality assurance and event monitoring applications. The challenge is to detect these interesting events or anomalies in a timely manner, while minimising energy consumption in the network. We propose a distributed anomaly detection architecture, which uses multiple hyperellipsoidal clusters to model the data at each sensor node, and identify global and local anomalies in the network. In particular, a novel anomaly scoring method is proposed to provide a score for each hyperellipsoidal model, based on how remote the ellipsoid is relative to their neighbours. We demonstrate using several synthetic and real datasets that our proposed scheme achieves a higher detection performance with a significant reduction in communication overhead in the network compared to centralised and existing schemes. © 2014 Elsevier Ltd.