A Branch and Bound Algorithm for a Transportation Type Problem with Piecewise Linear Convex Objective Function

A branch and bound type algorithm is presented in this paper to the problem of finding a transportation schedule which minimises the total transportation cost, where the transportation cost over each route is assumed to be a piecewice linear continuous convex function with increasing slopes. The algorithm is an extension of the work done by Balachandran and Perry, in which the transportation cost over each route is assumed to beapiecewise linear discontinuous function with decreasing slopes. A numerical example is solved illustrating the algorithm.

Bottleneck assignment problems under categorization

This paper considers two special cases of bottleneck grouped assignment problems when n jobs belong to m distinct categories (m < n). Solving these special problems through the available branch and bound algorithms will result in a heavy computational burden. Sequentially identifying nonopitmal variables, this paper provides more efficient methods for those cases. Propositions leading to the algorithms have been established. Numerical examples illustrate the respective algorithms.

A time minimising transportation problem with quality dependent time

The usual assumption made in time minimising transportation problem is that the time for transporting a positive amount in a route is independent of the actual amount transported in that route. In this paper we make a more general and natural assumption that the time depends on the actual amount transported. We assume that the time function for each route is an increasing piecewise constant function. Four algorithms - (1) a threshold algorithm, (2) an upper bounding technique, (3) a primal dual approach, and (4) a branch and bound algorithm - are presented to solve the given problem. A method is also given to compute the minimum bottle-neck shipment corresponding to the optimal time. A numerical example is solved illustrating the algorithms presented in this paper.

Implementation of placement and routing algorithms for computer aided design of printed circuit boards

The Printed Circuit Board (PCB) layout design is one of the most important and time consuming phases during equipment design process in all electronic industries. This paper is concerned with the development and implementation of a computer aided PCB design package. A set of programs which operate on a description of the circuit supplied by the user in the form of a data file and subsequently design the layout of a double-sided PCB has been developed. The algorithms used for the design of the PCB optimise the board area and the length of copper tracks used for the interconnections. The output of the package is the layout drawing of the PCB, drawn on a CALCOMP hard copy plotter and a Tektronix 4012 storage graphics display terminal. The routing density (the board area required for one component) achieved by this package is typically 0.8 sq. inch per IC. The package is implemented on a DEC 1090 system in Pascal and FORTRAN and SIGN(1) graphics package is used for display generation.

Free-to-bound and bound exciton transitions at isoelectronic impurities: GaP(Zn,O)

We show, for sufficiently high temperatures and sufficiently weak majority-carrier binding energies, that the dominant radiative transition at an isoelectronic acceptor (donor) in p-type (n-type) material consists of the recombination of singly trapped minority carriers (bound by central-cell forces) with free majority carriers attracted by a Coulomb interaction. There are two reasons why the radiative recombination rate of the free-to-bound process is greater than the bound exciton process, which dominates at lower temperatures: (i) The population of free majority-carrier states greatly exceeds that of exciton states at higher temperatures, and (ii) the oscillator strength of the free-to-bound transition is greatly enhanced by the Coulomb attraction between the free carrier and the charged isoelectronic impurity. This enhancement is important for isoelectronic centers and is easily calculable from existing exciton models. We show that the free carrier attracted by a Coulomb interaction can be viewed as a continuum excited state of the bound exciton. When we apply the results of our calculations to the GaP(Zn, O) system, we find that the major part of the room-temperature luminescence from nearest-neighbor isoelectronic Zn-O complexes results from free-to-bound recombination and not exciton recombination as has been thought previously. Recent experiments on impulse excitation of luminescence in GaP(Zn, O) are reevaluated in the light of our calculations and are shown to be consistent with a strong free-to-bound transition. For deep isoelectronic centers with weakly bound majority carriers, we predict an overwhelming dominance of the free-to-bound process at 300°K.

Swarm intelligence algorithms for integrated optimization of piezoelectric actuator and sensor placement and feedback gains

Swarm intelligence algorithms are applied for optimal control of flexible smart structures bonded with piezoelectric actuators and sensors. The optimal locations of actuators/sensors and feedback gain are obtained by maximizing the energy dissipated by the feedback control system. We provide a mathematical proof that this system is uncontrollable if the actuators and sensors are placed at the nodal points of the mode shapes. The optimal locations of actuators/sensors and feedback gain represent a constrained non-linear optimization problem. This problem is converted to an unconstrained optimization problem by using penalty functions. Two swarm intelligence algorithms, namely, Artificial bee colony (ABC) and glowworm swarm optimization (GSO) algorithms, are considered to obtain the optimal solution. In earlier published research, a cantilever beam with one and two collocated actuator(s)/sensor(s) was considered and the numerical results were obtained by using genetic algorithm and gradient based optimization methods. We consider the same problem and present the results obtained by using the swarm intelligence algorithms ABC and GSO. An extension of this cantilever beam problem with five collocated actuators/sensors is considered and the numerical results obtained by using the ABC and GSO algorithms are presented. The effect of increasing the number of design variables (locations of actuators and sensors and gain) on the optimization process is investigated. It is shown that the ABC and GSO algorithms are robust and are good choices for the optimization of smart structures.

Near-optimal large-MIMO detection using randomized MCMC and randomized search algorithms

Low-complexity near-optimal detection of signals in MIMO systems with large number (tens) of antennas is getting increased attention. In this paper, first, we propose a variant of Markov chain Monte Carlo (MCMC) algorithm which i) alleviates the stalling problem encountered in conventional MCMC algorithm at high SNRs, and ii) achieves near-optimal performance for large number of antennas (e.g., 16×16, 32×32, 64×64 MIMO) with 4-QAM. We call this proposed algorithm as randomized MCMC (R-MCMC) algorithm. Second, we propose an other algorithm based on a random selection approach to choose candidate vectors to be tested in a local neighborhood search. This algorithm, which we call as randomized search (RS) algorithm, also achieves near-optimal performance for large number of antennas with 4-QAM. The complexities of the proposed R-MCMC and RS algorithms are quadratic/sub-quadratic in number of transmit antennas, which are attractive for detection in large-MIMO systems. We also propose message passing aided R-MCMC and RS algorithms, which are shown to perform well for higher-order QAM.

Maximum likelihood algorithms for joint estimation of synchronisation impairments and channel in multiple input multiple output-orthogonal frequency division multiplexing system

Maximum likelihood (ML) algorithms, for the joint estimation of synchronisation impairments and channel in multiple input multiple output-orthogonal frequency division multiplexing (MIMO-OFDM) system, are investigated in this work. A system model that takes into account the effects of carrier frequency offset, sampling frequency offset, symbol timing error and channel impulse response is formulated. Cramer-Rao lower bounds for the estimation of continuous parameters are derived, which show the coupling effect among different impairments and the significance of the joint estimation. The authors propose an ML algorithm for the estimation of synchronisation impairments and channel together, using the grid search method. To reduce the complexity of the joint grid search in the ML algorithm, a modified ML (MML) algorithm with multiple one-dimensional searches is also proposed. Further, a stage-wise ML (SML) algorithm using existing algorithms, which estimate less number of parameters, is also proposed. Performance of the estimation algorithms is studied through numerical simulations and it is found that the proposed ML and MML algorithms exhibit better performance than SML algorithm.

Importance of non-conserved distal carboxyl terminal amino acids in two peptidases belonging to the M1 family: Thermoplasma acidophilum Tricorn interacting factor F2 and Escherichia coli Peptidase N

Enzymes belonging to the M1 family play important cellular roles and the key amino acids (aa) in the catalytic domain are conserved. However, C-terminal domain aa are highly variable and demonstrate distinct differences in organization. To address a functional role for the C-terminal domain, progressive deletions were generated in Tricorn interacting factor F2 from Thermoplasma acidophilum (F2) and Peptidase N from Escherichia coli (PepN). Catalytic activity was partially reduced in PepN lacking 4 C-terminal residues (PepNΔC4) whereas it was greatly reduced in F2 lacking 10 C-terminal residues (F2ΔC10) or PepN lacking eleven C-terminal residues (PepNΔC11). Notably, expression of PepNΔC4, but not PepNΔC11, in E. coliΔpepN increased its ability to resist nutritional and high temperature stress, demonstrating physiological significance. Purified C-terminal deleted proteins demonstrated greater sensitivity to trypsin and bound stronger to 8-amino 1-napthalene sulphonic acid (ANS), revealing greater numbers of surface exposed hydrophobic aa. Also, F2 or PepN containing large aa deletions in the C-termini, but not smaller deletions, were present in high amounts in the insoluble fraction of cell extracts probably due to reduced protein solubility. Modeling studies, using the crystal structure of E. coli PepN, demonstrated increase in hydrophobic surface area and change in accessibility of several aa from buried to exposed upon deletion of C-terminal aa. Together, these studies revealed that non-conserved distal C-terminal aa repress the surface exposure of apolar aa, enhance protein solubility, and catalytic activity in two soluble and distinct members of the M1 family.

Dual-DSP system for signal and image processing

The design of a dual-DSP microprocessor system and its application for parallel FFT and two-dimensional convolution are explained. The system is based on a master-salve configuration. Two ADSP-2101s are configured as slave processors and a PC/AT serves as the master. The master serves as a control processor to transfer the program code and data to the DSPs. The system architecture and the algorithms for the two applications, viz. FFT and two-dimensional convolutions, are discussed.

Mobile Base Stations Placement and Energy Aware Routing in Wireless Sensor Networks

Increasing network lifetime is important in wireless sensor/ad-hoc networks. In this paper, we are concerned with algorithms to increase network lifetime and amount of data delivered during the lifetime by deploying multiple mobile base stations in the sensor network field. Specifically, we allow multiple mobile base stations to be deployed along the periphery of the sensor network field and develop algorithms to dynamically choose the locations of these base stations so as to improve network lifetime. We propose energy efficient low-complexity algorithms to determine the locations of the base stations; they include i) Top-K-max algorithm, ii) maximizing the minimum residual energy (Max-Min-RE) algorithm, and iii) minimizing the residual energy difference (MinDiff-RE) algorithm. We show that the proposed base stations placement algorithms provide increased network lifetimes and amount of data delivered during the network lifetime compared to single base station scenario as well as multiple static base stations scenario, and close to those obtained by solving an integer linear program (ILP) to determine the locations of the mobile base stations. We also investigate the lifetime gain when an energy aware routing protocol is employed along with multiple base stations.

Distance measures on intersecting objects and their applications

Let A and B be two objects. We define measures to characterize the penetration of A and B when A boolean AND B not equal 0. We then present properties of the measures and efficient algorithms to compute them for planar and polyhedral objects. We explore applications of the measures and present some experimental results.

Crystal structure of Salmonella typhimurium 2-methylcitrate synthase: Insights on domain movement and substrate specificity

2-Methylcitric acid (2-MCA) cycle is one of the well studied pathways for the utilization of propionate as a source of carbon and energy in bacteria such as Salmonella typhimurium and Escherichia coli. 2-Methylcitrate synthase (2-MCS) catalyzes the conversion of oxaloacetate and propionyl-CoA to 2-methylcitrate and CoA in the second step of 2-MCA cycle. Here, we report the X-ray crystal structure of S. typhimurium 2-MCS (StPrpC) at 2.4 A resolution and its functional characterization. StPrpC was found to utilize propionyl-CoA more efficiently than acetyl-CoA or butyryl-CoA. The polypeptide fold and the catalytic residues of StPrpC are conserved in citrate synthases (CSs) suggesting similarities in their functional mechanisms. In the triclinic P1 cell, StPrpC molecules were organized as decamers composed of five identical dimer units. In solution, StPrpC was in a dimeric form at low concentrations and was converted to larger oligomers at higher concentrations. CSs are usually dimeric proteins. In Gram-negative bacteria, a hexameric form, believed to be important for regulation of activity by NADH, is also observed. Structural comparisons with hexameric E. coil CS suggested that the key residues involved in NADH binding are not conserved in StPrpC. Structural comparison with the ligand free and bound states of CSs showed that StPrpC is in a nearly closed conformation despite the absence of bound ligands. It was found that the Tyr197 and Leu324 of StPrpC are structurally equivalent to the ligand binding residues His and Val, respectively, of CSs. These substitutions might determine the specificities for acyl-CoAs of these enzymes. (C) 2010 Elsevier Inc. All rights reserved.