Optimal reservoir operation for irrigation of multiple crops using genetic algorithms

This paper presents a genetic algorithm (GA) model for obtaining an optimal operating policy and optimal crop water allocations from an irrigation reservoir. The objective is to maximize the sum of the relative yields from all crops in the irrigated area. The model takes into account reservoir inflow, rainfall on the irrigated area, intraseasonal competition for water among multiple crops, the soil moisture dynamics in each cropped area, the heterogeneous nature of soils. and crop response to the level of irrigation applied. The model is applied to the Malaprabha single-purpose irrigation reservoir in Karnataka State, India. The optimal operating policy obtained using the GA is similar to that obtained by linear programming. This model can be used for optimal utilization of the available water resources of any reservoir system to obtain maximum benefits.

Integration-free algorithms for fixed end-point regulator problems

A new formulation is suggested for the fixed end-point regulator problem, which, in conjunction with the recently developed integration-free algorithms, provides an efficient means of obtaining numerical solutions to such problems.

Efficient algorithms for domination and Hamilton circuit problems on permutation graphs

The domination and Hamilton circuit problems are of interest both in algorithm design and complexity theory. The domination problem has applications in facility location and the Hamilton circuit problem has applications in routing problems in communications and operations research.The problem of deciding if G has a dominating set of cardinality at most k, and the problem of determining if G has a Hamilton circuit are NP-Complete. Polynomial time algorithms are, however, available for a large number of restricted classes. A motivation for the study of these algorithms is that they not only give insight into the characterization of these classes but also require a variety of algorithmic techniques and data structures. So the search for efficient algorithms, for these problems in many classes still continues.A class of perfect graphs which is practically important and mathematically interesting is the class of permutation graphs. The domination problem is polynomial time solvable on permutation graphs. Algorithms that are already available are of time complexity O(n2) or more, and space complexity O(n2) on these graphs. The Hamilton circuit problem is open for this class.We present a simple O(n) time and O(n) space algorithm for the domination problem on permutation graphs. Unlike the existing algorithms, we use the concept of geometric representation of permutation graphs. Further, exploiting this geometric notion, we develop an O(n2) time and O(n) space algorithm for the Hamilton circuit problem.

Effect of favorable pressure gradient on transitional spot formation rate

The calculation of the transitional boundary layer requires estimates of the extent of the transition zone, which in turn depends on the rate at which turbulent spots are formed. This rate has been found to scale with local boundary layer thickness and viscosity, and the resulting nondimensional group (called crumble) is a function of the pressure gradient, among other parameters. Available experimental data are analyzed to show that the crumble increases slowly with increasing favorable pressure gradients, being about four times as large as in constant-pressure flow when the Thwaites pressure gradient parameter at the effective origin of the resulting turbulent boundary layer is 0.1 and when transition is driven by free-stream turbulence.

Tree 3-spanners in 2-sep chordal graphs: Characterization and algorithms

A spanning tree T of a graph G is said to be a tree t-spanner if the distance between any two vertices in T is at most t times their distance in G. A graph that has a tree t-spanner is called a tree t-spanner admissible graph. The problem of deciding whether a graph is tree t-spanner admissible is NP-complete for any fixed t >= 4 and is linearly solvable for t <= 2. The case t = 3 still remains open. A chordal graph is called a 2-sep chordal graph if all of its minimal a - b vertex separators for every pair of non-adjacent vertices a and b are of size two. It is known that not all 2-sep chordal graphs admit tree 3-spanners This paper presents a structural characterization and a linear time recognition algorithm of tree 3-spanner admissible 2-sep chordal graphs. Finally, a linear time algorithm to construct a tree 3-spanner of a tree 3-spanner admissible 2-sep chordal graph is proposed. (C) 2010 Elsevier B.V. All rights reserved.

A Deterministic Optimization Approach to Protein Sequence Design Using Continuous Models

Determining the sequence of amino acid residues in a heteropolymer chain of a protein with a given conformation is a discrete combinatorial problem that is not generally amenable for gradient-based continuous optimization algorithms. In this paper we present a new approach to this problem using continuous models. In this modeling, continuous "state functions" are proposed to designate the type of each residue in the chain. Such a continuous model helps define a continuous sequence space in which a chosen criterion is optimized to find the most appropriate sequence. Searching a continuous sequence space using a deterministic optimization algorithm makes it possible to find the optimal sequences with much less computation than many other approaches. The computational efficiency of this method is further improved by combining it with a graph spectral method, which explicitly takes into account the topology of the desired conformation and also helps make the combined method more robust. The continuous modeling used here appears to have additional advantages in mimicking the folding pathways and in creating the energy landscapes that help find sequences with high stability and kinetic accessibility. To illustrate the new approach, a widely used simplifying assumption is made by considering only two types of residues: hydrophobic (H) and polar (P). Self-avoiding compact lattice models are used to validate the method with known results in the literature and data that can be practically obtained by exhaustive enumeration on a desktop computer. We also present examples of sequence design for the HP models of some real proteins, which are solved in less than five minutes on a single-processor desktop computer Some open issues and future extensions are noted.

Latitudinal gradient in aerosol properties over the Indian and Southern Oceans during the austral summer

Extensive measurements of columnar aerosol optical depth (AOD), composite (M-T) and black carbon aerosol mass (M-B) concentrations were made over the tropical Indian and Southern Oceans as a part of the Pilot Expedition to the Southern Ocean during the boreal winter. The AOD, M-T and M-B show large latitudinal gradient towards south up to ITCZ. Beyond ITCZ, up to 56 degrees S, AOD and M-B show very low and steady values. However M-T shows large variations in the Southern Ocean due to the enhanced production of sea salt aerosols associated with high sea surface winds. The short wave aerosol radiative forcing at the surface over north of equator is in the range - 10 to -23 W m(-2), whereas that over the Southern Ocean was in the range -4 to -5 W m(-2). The corresponding atmospheric forcing was in the range of 6-13 W m(-2) and 0.8-1.4 W m(-2). This large north south change in the aerosol radiative forcing has important implications to the meridional circulation and hence to climate.

Gradient solid-electrolyte for use with dissimilar gas electrodes

The EMF of a solid-state cell, incorporating a composite solid-electrolyte with gradual variation in composition, and dissimilar gas electrodes, has been studied as a function of temperature and partial pressures at the electrodes. The cell with the configuration: Pt, CO2' + O2' parallel-to Na2CO3\Na(SO4)x(CO3)1-x\Na2SO4 parallel-to SO3'' + SO2'' + O2'', Pt x=0 x=1 was investigated in the temperature range 973 to 1079 K. The solid-electrolyte surface exposed to SO3 + SO2 + O2 gas mixture was doped-Na2SO4, whereas the CO2 + O2 gas mixture was in contact with pure Na2CO3. The composition of the solid solution between the carbonate and sulfate, with hexagonal structure, was varied gradually between the boundary values. It has been found that the EMF of the cell is close to that calculated from thermodynamic data, assuming unit transport number for Na+ ions. The gradient in the concentration of sulfate and carbonate ions in the electrolyte does not give rise to a significant diffusion potential.

Algorithms for Routing and Centralized Scheduling in IEEE 802.16 Mesh Networks

IEEE 802.16 standards for Wireless Metropolitan Area Networks (WMANs) include a mesh mode of operation for improving the coverage and throughput of the network. In this paper, we consider the problem of routing and centralized scheduling for such networks. We first fix the routing, which reduces the network to a tree. We then present a finite horizon dynamic programming framework. Using it we obtain various scheduling algorithms depending upon the cost function. Next we consider simpler suboptimal algorithms and compare their performances.

Thermodynamic Study of Mixed Anionic Solid Solutions Using Gradient Solid Electrolytes System K2CO3 - K2SO4

The thermodynamic properties of K2CO3 -KSO, solid solutions with hexagonal structure have been measured using a solid-state cell, incorporating a composite solid electrolyte with step-changes in composition. The cell with the configuration Pt, CO2' + O2' || K2CO3 | K2(CO3)x(SO4)1-x || CO2'' + O2'' + Pt X =1 X=X was investigated in the temperature range of 925 to 1165 K. The composite gradient solid electrolyte consisted of pure K2CO3 at one extremity and the solid solution under study at the other. The Nernstian response of the cell to changes in partial pressures of CO2 and O2 at the electrodes and temperature was demonstrated. The activity of K2CO3 in the solid solution was measured by three techniques. All three methods gave identical results, indicating unit transport number for K+ ions and negligible diffusion potential due to concentration gradients of carbonate and sulfate ions. The activity of K2CO3 exhibits positive deviation from Raoult's law. The excess Gibbs energy of mixing of the solid solution can be represented using a subregular solution model DELTAG(E) = X(1 - X)[5030X + 4715(1 - X)] J mol-1 By combining this information with the phase diagram, mixing properties of the liquid phase were obtained.

New Approximation Algorithms for Minimum Cycle Bases of Graphs

We consider the problem of computing an approximate minimum cycle basis of an undirected non-negative edge-weighted graph G with m edges and n vertices; the extension to directed graphs is also discussed. In this problem, a {0,1} incidence vector is associated with each cycle and the vector space over F-2 generated by these vectors is the cycle space of G. A set of cycles is called a cycle basis of G if it forms a basis for its cycle space. A cycle basis where the sum of the weights of the cycles is minimum is called a minimum cycle basis of G. Cycle bases of low weight are useful in a number of contexts, e.g. the analysis of electrical networks, structural engineering, chemistry, and surface reconstruction. Although in most such applications any cycle basis can be used, a low weight cycle basis often translates to better performance and/or numerical stability. Despite the fact that the problem can be solved exactly in polynomial time, we design approximation algorithms since the performance of the exact algorithms may be too expensive for some practical applications. We present two new algorithms to compute an approximate minimum cycle basis. For any integer k >= 1, we give (2k - 1)-approximation algorithms with expected running time O(kmn(1+2/k) + mn((1+1/k)(omega-1))) and deterministic running time O(n(3+2/k) ), respectively. Here omega is the best exponent of matrix multiplication. It is presently known that omega < 2.376. Both algorithms are o(m(omega)) for dense graphs. This is the first time that any algorithm which computes sparse cycle bases with a guarantee drops below the Theta(m(omega) ) bound. We also present a 2-approximation algorithm with expected running time O(M-omega root n log n), a linear time 2-approximation algorithm for planar graphs and an O(n(3)) time 2.42-approximation algorithm for the complete Euclidean graph in the plane.

Load balancing algorithms for an extended hypercube

Reduction of the execution time of a job through equitable distribution of work load among the processors in a distributed system is the goal of load balancing. Performance of static and dynamic load balancing algorithms for the extended hypercube, is discussed. Threshold algorithms are very well-known algorithms for dynamic load balancing in distributed systems. An extension of the threshold algorithm, called the multilevel threshold algorithm, has been proposed. The hierarchical interconnection network of the extended hypercube is suitable for implementing the proposed algorithm. The new algorithm has been implemented on a transputer-based system and the performance of the algorithm for an extended hypercube is compared with those for mesh and binary hypercube networks

Absolutely expedient algorithms for learning Nash equilibria

This paper considers a multi-person discrete game with random payoffs. The distribution of the random payoff is unknown to the players and further none of the players know the strategies or the actual moves of other players. A class of absolutely expedient learning algorithms for the game based on a decentralised team of Learning Automata is presented. These algorithms correspond, in some sense, to rational behaviour on the part of the players. All stable stationary points of the algorithm are shown to be Nash equilibria for the game. It is also shown that under some additional constraints on the game, the team will always converge to a Nash equilibrium.