An amoeboid algorithm for solving linear transportation problem

Transportation Problem (TP) is one of the basic operational research problems, which plays an important role in many practical applications. In this paper, a bio-inspired mathematical model is proposed to handle the Linear Transportation Problem (LTP) in directed networks by modifying the original amoeba model Physarum Solver. Several examples are used to prove that the provided model can effectively solve Balanced Transportation Problem (BTP), Unbalanced Transportation Problem (UTP), especially the Generalized Transportation Problem (GTP), in a nondiscrete way. © 2013 Elsevier B.V. All rights reserved.

Smoothing Lipschitz functions

This paper describes a new approach to multivariate scattered data smoothing. It is assumed that the data are generated by a Lipschitz continuous function f, and include random noise to be filtered out. The proposed approach uses known, or estimated value of the Lipschitz constant of f, and forces the data to be consistent with the Lipschitz properties of f. Depending on the assumptions about the distribution of the random noise, smoothing is reduced to a standard quadratic or a linear programming problem. We discuss an efficient algorithm which eliminates the redundant inequality constraints. Numerical experiments illustrate applicability and efficiency of the method. This approach provides an efficient new tool of multivariate scattered data approximation.

Blind source separation by fully nonnegative constrained iterative volume maximization

Blind source separation (BSS) has been widely discussed in many real applications. Recently, under the assumption that both of the sources and the mixing matrix are nonnegative, Wang develop an amazing BSS method by using volume maximization. However, the algorithm that they have proposed can guarantee the nonnegativities of the sources only, but cannot obtain a nonnegative mixing matrix necessarily. In this letter, by introducing additional constraints, a method for fully nonnegative constrained iterative volume maximization (FNCIVM) is proposed. The result is with more interpretation, while the algorithm is based on solving a single linear programming problem. Numerical experiments with synthetic signals and real-world images are performed, which show the effectiveness of the proposed method.

Semi-supervised classification based on subspace sparse representation

Graph plays an important role in graph-based semi-supervised classification. However, due to noisy and redundant features in high-dimensional data, it is not a trivial job to construct a well-structured graph on high-dimensional samples. In this paper, we take advantage of sparse representation in random subspaces for graph construction and propose a method called Semi-Supervised Classification based on Subspace Sparse Representation, SSC-SSR in short. SSC-SSR first generates several random subspaces from the original space and then seeks sparse representation coefficients in these subspaces. Next, it trains semi-supervised linear classifiers on graphs that are constructed by these coefficients. Finally, it combines these classifiers into an ensemble classifier by minimizing a linear regression problem. Unlike traditional graph-based semi-supervised classification methods, the graphs of SSC-SSR are data-driven instead of man-made in advance. Empirical study on face images classification tasks demonstrates that SSC-SSR not only has superior recognition performance with respect to competitive methods, but also has wide ranges of effective input parameters.

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.

Home range of the squirrel glider (Petaurus norfolcensis) in a network of remnant linear habitats

Linear strips of natural or semi-natural vegetation are a characteristic feature of rural landscapes throughout the world. Their value for the conservation of fauna in heavily modified landscapes depends on the response of species to the linear shape of the habitat, and the pressures this imposes on population processes and spatial organization. In south-eastern Australia, woodland habitats occupied by the squirrel glider Petaurus norfolcensis, a threatened species of arboreal marsupial, have been preferentially cleared for agriculture leaving only remnants within cleared farmland. In this study, the home range of P. norfolcensis was investigated by radio-tracking 40 gliders within a highly modified landscape where the majority (83%) of remaining wooded habitat occurs as a network of linear strips along roadsides and streams. Individuals were tracked for one to four seasons, resulting in the collection of 4213 independent locational 'fixes'. All fixes of animals were from remnant woodland. Home ranges were elongated and linear, primarily determined by the shape and arrangement of woodland habitat. Seasonal home ranges were small (mean of 1.4–2.8 ha) and ranged between 320 and 840 m long. Small patches of trees in farmland adjacent to the linear habitats were also extensively used. Despite the highly modified landscape structure, home ranges of P. norfolcensis in the linear network were smaller than those estimated from other studies of this species in continuous habitat. The apparent high quality of the linear habitats is attributed to the density of large old trees, which provide foraging and breeding resources, and the productivity of the environment. Linear landscape elements may have a valuable conservation function where they provide resident habitat or enhance landscape connectivity, but their long-term viability is vulnerable to disturbance.

Control loop for finding initial translator position of linear synchronous motor

This article presents a simple and reliable method for controlling the relative orientation between the two magnetic fields of a permanent magnet synchronous motor. Finding the initial (at motor powering- up time) value of this relative location is essential for the proper operation of the motor. After showing the system controllability, the utilized feedback control loop finds this initial relative orientation quickly and accurately. Further, using the proposed method allows considerable cost saving, as a transducer that is usually used for this purpose can be eliminated. The cost saving is most obvious in the case of linear motors and angle motors with large diameters. The way the problem is posed is an essential part of this work, and it is the reason behind the apparent simplicity of the solution. The method proposed relies on a single sensor, and it was tested when a relative encoder was used.

A new algorithm for blind separation of cyclostationary source from linear mixtures

This paper addresses the problem of separating a cyclostationary source from linear mixtures. It first shows that if the cyclic frequencies of the source of interest are known and different from those of the interfering sources, perfect source separation can be achieved using the proposed separation criterion. Then an algorithm is derived to perform the blind source separation. Simulation results demonstrate the validity of the proposed algorithm

Design of a common observer for two linear systems with unknown inputs

This paper considers the design of a common linear functional observer for two linear time-invariant systems with unknown inputs. A structure for a common observer which only uses the available output information is proposed. Here, for the proposed structure, we show that the simultaneous functional observation problem of two plants is reduced to a problem of designing two observers: the first is a full-order unknown input observer of one of the two systems; the second observer is a common unknown input observer of a system comprises two-connected systems. In general, the existence conditions for the second observer are very difficult to satisfy. This paper thus concludes that it is indeed very difficult to find a common observer for two linear systems with unknown inputs.

Polyhedral results and exact algorithms for the asymmetric travelling salesman problem with replenishment arcs

The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems.

A low-order linear functional observer for time delay systems

This paper presents an efficient technique to design low order state function observers for linear time-delay systems. Assuming the existence of a linear state feedback controller to achieve stability or some control performance criteria of the time-delay system, a design procedure is proposed for
reconstruction of the state feedback control action. The procedure involves solving an optimisation problem with the objective to generate a matrix that is as close as possible to the given feedback gain of the required feedback controller. A condition for robust stability of the time-delay system using the observer-based control scheme is given. The attractive features of the proposed design procedure are that the resulted linear functional state observer is of a very low order and it requires information of a small number of outputs. Numerical examples are given to demonstrate the design procedure and its merits.

An algebraic approach for delay-independent and delay-dependent stability of linear time-delay systems

This paper addresses the problem of asymptotic stability of a linear system with many delay units. A novel algebraic test is proposed for the delay-independent stability of the system, based on the root distribution of the system's characteristic equation. If the system is only stable dependent of delay, the whole stable regions of the system can be perfectly obtained. Two algorithms are derived to examine the delay-independent stability, and to compute the whole stable regions if the system is of delay-dependent stability. These algorithms are computationally efficient and applicable to both certain and uncertain systems. Some illustrative examples demonstrate the validity of the approach.

A common disturbance decoupled observer for linear systems with unknown inputs

This paper presents a solution to the problem of designing a common linear functional observer that can observe a partial set of the state vector of two linear systems with unknown inputs. A new structure of a decoupled linear functional observer is proposed for systems subject unknown disturbances, using only the available output information. Existence conditions as well as a design procedure are given for constructing the proposed observer. A numerical example is given to illustrate the effectiveness of the new observer structure.

Optimal multisensor data fusion for linear systems with missing measurements

Multisensor data fusion has attracted a lot of research in recent years. It has been widely used in many applications especially military applications for target tracking and identification. In this paper, we will handle the multisensor data fusion problem for systems suffering from the possibility of missing measurements. We present the optimal recursive fusion filter for measurements obtained from two sensors subject to random intermittent measurements. The noise covariance in the observation process is allowed to be singular which requires the use of generalized inverse. Illustration example shows the effectiveness of the proposed filter in the measurements loss case compared to the available optimal linear fusion methods.

Localization of mobile transmitters by means of linear state estimation using RSS measurements

This paper investigates the problem of estimating the location and velocity of a mobile agent using the received signal strength (RSS) measurements. Typical power measurements are inherently nonlinear and in this approach we derive a linear measurement scheme using an analytical measurement conversion technique which can readily be used with RSS measuring sensors. Power measurements are hence used in our robust version of a linear Kalman filter to estimate the dynamic parameters of the moving transmitter.