Detecting embedded pure network structures in LP problems

Recently, linear programming problems with special structures have assumed growing importance in mathematical programming. It is well known that exploiting network structures within linear programs can lead to considerable improvement of the computational solution of large-scale linear programming problems. A linear program is said to contain an embedded network structure provided that some subset of its constraints can be interpreted as specifying conservation of flow. If a column of the constraint matrix has at most two non-zeros, then it leads to embedded generalized network structure and if these non-zeros are unit elements and of opposite signs, then it leads to embedded pure network structure. In this paper, we are concerned with algorithms for detecting embedded pure network structures within linear programs. The network extraction methods are presented in two groups. The first group covers deletion and addition based algorithms and the second group covers GUB based algorithms. We have extended the GUB based algorithm appearing in the second group by introducing Markowitz merit count approach for exploiting matrix non zeros. A set of well known test problems has been used to carry out computational experiments which show that our extensions to the GUB based algorithms give better results than the algorithms reported earlier.     

Broadcasting, Scalability, and Reconfigurability Aspects in an All-Optical Network Architecture

All-optical networks are a sound answer to the huge data traffic demand expected for the forthcoming information society. Interesting networking aspects are the broadcasting, scalability, and reconfiguration in an all-optical environment. These issues are addressed in the present article for an all-optical network called MATRIX, which is time slotted and uses packet switching. The architecture enables the all-optical interconnection of a large number of nodes with both a small number of wavelengths and wavelength continuity based on a consequent exploitation of wavelength-division multiplexing and space-division multiplexing (i.e., multiple fibers per cable are used). For an efficient use of the resources, each node is equipped with multiple transmitters and receivers, respectively. Two different broadcasting schemes are investigated. An analytical model is developed, and the corresponding simulation results are in good agreement. It is further shown how different networks of arbitrary size can be interconnected to larger all-optical network clusters, thereby providing scalability not only with respect to the number of nodes but also to the geographical extension. Finally, wavelength reassignments allow change of optical paths through the network in case of changing traffic patterns or network failures in order to best exploit the available network resources. The total number of possible configurations is determined by the theory of Latin Squares.     

Optimal numerical method for simulating dynamic flow of gas in pipelines

Finite difference methods for solving the linear model describing unsteady state flow in pipelines are considered in the present paper. These methods are compared with each other in order to determine the best one, which meets the criteria of accuracy and relatively small computation time.     

Spinal effects of acupuncture stimulation assessed by proton density-weighted functional magnetic resonance imaging at 0.2 T

Signal changes can be detected by proton density-weighted functional imaging in both the brain and the spinal cord. These are attributed to changes in extravascular water proton (signal enhancement by extravascular protons) density during neuronal activation. In this study, we used this technique to detect correlations between acupoint stimulation and neural activity in the spinal cord. Stimulation of acupoints associated with treatment of sensorimotor deficits (LI4 and LI11) was performed on 11 volunteers. During stimulation, 8 of the 11 subjects had consistent functional activations in C6/C7. A bilateral activation pattern was common. Our findings show that acupoint stimulation modulates activity in the spinal cord.     

Moderate Deviations for the overlap parameter in the Hopfield model

We derive moderate deviation principles for the overlap parameter in the Hopfield model of spin glasses and neural networks. If the inverse temperature is different from the critical inverse temperature _c=1 and the number of patterns M(N) satisfies M(N)/N 0, the overlap parameter multiplied by N, 1/2 < < 1, obeys a moderate deviation principle with speed N^1–2 and a quadratic rate function (i.e. the Gaussian limit for = 1/2 remains visible on the moderate deviation scale). At the critical temperature we need to multiply the overlap parameter by N, 1/4 < < 1. If then M(N) satisfies (M(N)⁶ log N M(N)²N⁴ log N)/N 0, the rescaled overlap parameter obeys a moderate deviation principle with speed N^1–4 and a rate function that is basically a fourth power. The random term occurring in the Central Limit theorem for the overlap at _c = 1 is no longer present on a moderate deviation scale. If the scaling is even closer to N^1/4, e.g. if we multiply the overlap parameter by N^1/4 log log N the moderate deviation principle breaks down. The case of variable temperature converging to one is also considered. If _N converges to _c fast enough, i.e. faster than the non-Gaussian rate function persists, whereas for _N converging to one slower than the moderate deviations principle is given by the Gaussian rate. At the borderline the moderate deviation rate function is the one at criticality plus an additional Gaussian term.Research supported by the Volkswagen-Stiftung (RiP-program at Oberwolfach, Germany).Mathematics Subject Classification (2000): 60F10 (primary), 60K35, 82B44, 82D30 (secondary)     

Efficient Hopfield pattern recognition on a scale-free neural network

Neural networks are supposed to recognise blurred images (or patterns) of N pixels (bits) each. Application of the network to an initial blurred version of one of P pre-assigned patterns should converge to the correct pattern. In the “standard" Hopfield model, the N “neurons” are connected to each other via N² bonds which contain the information on the stored patterns. Thus computer time and memory in general grow with N². The Hebb rule assigns synaptic coupling strengths proportional to the overlap of the stored patterns at the two coupled neurons. Here we simulate the Hopfield model on the Barabási-Albert scale-free network, in which each newly added neuron is connected to only m other neurons, and at the end the number of neurons with q neighbours decays as 1/q ³. Although the quality of retrieval decreases for small m, we find good associative memory for 1 ≪ m ≪ N. Hence, these networks gain a factor N/m ≫ 1 in the computer memory and time. Received 12 January 2003 Published online 11 April 2003 RID="a" ID="a"e-mail: stauffer@thp.uni-koeln.de     

Inevitable self-similar topology of binary trees and their diverse hierarchical density

Self-similar topology, which can be characterized as power law size distribution, has been found in diverse tree networks ranging from river networks to taxonomic trees. In this study, we find that the statistical self-similar topology is an inevitable consequence of any full binary tree organization. We show this by coding a binary tree as a unique bifurcation string. This coding scheme allows us to investigate trees over the realm from deterministic to entirely random trees. To obtain partial random trees, partial random perturbation is added to the deterministic trees by an operator similar to that used in genetic algorithms. Our analysis shows that the hierarchical density of binary trees is more diverse than has been described in earlier studies. We find that the connectivity structure of river networks is far from strict self-similar trees. On the other hand, organization of some social networks is close to deterministic supercritical trees.     

Inferring topological features of proteins from amino acid residue networks

Topological properties of native folds are obtained from statistical analysis of 160 low homology proteins covering the four structural classes. This is done analyzing one, two and three-vertex joint distribution of quantities related to the corresponding network of amino acid residues. Emphasis on the amino acid residue hydrophobicity leads to the definition of their center of mass as vertices in this contact network model with interactions represented by edges. The network analysis helps us to interpret experimental results such as hydrophobic scales and fraction of buried accessible surface area in terms of the network connectivity. Moreover, those networks show assortative mixing by degree. To explore the vertex-type dependent correlations, we build a network of hydrophobic and polar vertices. This procedure presents the wiring diagram of the topological structure of globular proteins leading to the following attachment probabilities between hydrophobic–hydrophobic 0.424(5), hydrophobic-polar 0.419(2) and polar–polar 0.157(3) residues.     

Growth kinetics of borided layers: Artificial neural network and least square approaches

The present study evaluates the growth kinetics of the boride layer Fe₂B in AISI 1045 steel, by means of neural networks and the least square techniques. The Fe₂B phase was formed at the material surface using the paste boriding process. The surface boron potential was modified considering different boron paste thicknesses, with exposure times of 2, 4 and 6 h, and treatment temperatures of 1193, 1223 and 1273 K. The neural network and the least square models were set by the layer thickness of Fe₂B phase, and assuming that the growth of the boride layer follows a parabolic law. The reliability of the techniques used is compared with a set of experiments at a temperature of 1223 K with 5 h of treatment time and boron potentials of 2, 3, 4 and 5 mm. The results of the Fe₂B layer thicknesses show a mean error of 5.31% for the neural network and 3.42% for the least square method.