Distributed nonlinear optimization algorithms for general network problems

There are a number of large networks which occur in many problems dealing with the flow of power, communication signals, water, gas, transportable goods, etc. Both design and planning of these networks involve optimization problems. The first part of this paper introduces the common characteristics of a nonlinear network (the network may be linear, the objective function may be non linear, or both may be nonlinear). The second part develops a mathematical model trying to put together some important constraints based on the abstraction for a general network. The third part deals with solution procedures; it converts the network to a matrix based system of equations, gives the characteristics of the matrix and suggests two solution procedures, one of them being a new one. The fourth part handles spatially distributed networks and evolves a number of decomposition techniques so that we can solve the problem with the help of a distributed computer system. Algorithms for parallel processors and spatially distributed systems have been described.There are a number of common features that pertain to networks. A network consists of a set of nodes and arcs. In addition at every node, there is a possibility of an input (like power, water, message, goods etc) or an output or none. Normally, the network equations describe the flows amoungst nodes through the arcs. These network equations couple variables associated with nodes. Invariably, variables pertaining to arcs are constants; the result required will be flows through the arcs. To solve the normal base problem, we are given input flows at nodes, output flows at nodes and certain physical constraints on other variables at nodes and we should find out the flows through the network (variables at nodes will be referred to as across variables).The optimization problem involves in selecting inputs at nodes so as to optimise an objective function; the objective may be a cost function based on the inputs to be minimised or a loss function or an efficiency function. The above mathematical model can be solved using Lagrange Multiplier technique since the equalities are strong compared to inequalities. The Lagrange multiplier technique divides the solution procedure into two stages per iteration. Stage one calculates the problem variables % and stage two the multipliers lambda. It is shown that the Jacobian matrix used in stage one (for solving a nonlinear system of necessary conditions) occurs in the stage two also.A second solution procedure has also been imbedded into the first one. This is called total residue approach. It changes the equality constraints so that we can get faster convergence of the iterations.Both solution procedures are found to coverge in 3 to 7 iterations for a sample network.The availability of distributed computer systems — both LAN and WAN — suggest the need for algorithms to solve the optimization problems. Two types of algorithms have been proposed — one based on the physics of the network and the other on the property of the Jacobian matrix. Three algorithms have been deviced, one of them for the local area case. These algorithms are called as regional distributed algorithm, hierarchical regional distributed algorithm (both using the physics properties of the network), and locally distributed algorithm (a multiprocessor based approach with a local area network configuration). The approach used was to define an algorithm that is faster and uses minimum communications. These algorithms are found to converge at the same rate as the non distributed (unitary) case.

Algorithms for Colouring Random k-colourable Graphs

The k-colouring problem is to colour a given k-colourable graph with k colours. This problem is known to be NP-hard even for fixed k greater than or equal to 3. The best known polynomial time approximation algorithms require n(delta) (for a positive constant delta depending on k) colours to colour an arbitrary k-colourable n-vertex graph. The situation is entirely different if we look at the average performance of an algorithm rather than its worst-case performance. It is well known that a k-colourable graph drawn from certain classes of distributions can be ii-coloured almost surely in polynomial time. In this paper, we present further results in this direction. We consider k-colourable graphs drawn from the random model in which each allowed edge is chosen independently with probability p(n) after initially partitioning the vertex set into ii colour classes. We present polynomial time algorithms of two different types. The first type of algorithm always runs in polynomial time and succeeds almost surely. Algorithms of this type have been proposed before, but our algorithms have provably exponentially small failure probabilities. The second type of algorithm always succeeds and has polynomial running time on average. Such algorithms are more useful and more difficult to obtain than the first type of algorithms. Our algorithms work as long as p(n) greater than or equal to n(-1+is an element of) where is an element of is a constant greater than 1/4.

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.

Use of metastable equilibria for determination of Gibbs energy of solids

Attempts are made to measure activities of both components of a binary alloy (A�B) at 650 K using a solid-state galvanic cell incorporating a new composite solid electrolyte. Since the ionic conductivity of the composite solid electrolyte is three orders of magnitude higher than that of pure CaF2, the cell can be operated at lower temperatures. The alloy phase is equilibrated in separate experiments with flourides of each component and fluorine potential is measured. The mixture of the alloy (A�B) and the fluoride of the more reactive component (BF2) is stable, while (A�B) + AF2 mixture is metastable, Factors governing the possible use of metastable equilibria have been elucidated in this study. In the Co�Ni system, where the difference in Gibbs energies of formation of the fluorides is 21.4 kJ/mol, emf of the cell with metastable phases at the electrode is constant for periods ranging from 90 to 160 ks depending on alloy composition. Subsequently, the emf decreases because of the onset of the displacement reaction. In the Ni�Mn system, measurement of the activity of Ni using metastable equilibria is not fully successful at 650 K because of the large driving force for the displacement reaction (208.8 kJ/mol). Critical factors in the application of metastable equilibria are the driving force for displacement reaction and diffusion coefficients in both the alloy and fluoride solid solution.

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.

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.

Standard Gibbs' energies of formation of BaCuO2, Y2Cu2O5 and Y2BaCuO5

The Gibbs' energies of formation of BaCuO2, Y2Cu2O5 and Y2BaCuO5 from component oxides have been measured using solid state galvanic cells incorporating CaF2 as the solid electrolyte under pure oxygen at a pressure of 1.01 x 10(5) Pa Because the superconducting compound YBa2Cu3O7-delta coexists with any two of the phases CuO, BaCuO2 and Y2BaCuO5, the data on BaCuO2 and Y2BaCuO5 obtained in this study provide the basis for the evaluation of the Gibbs' energy of formation of the 1-2-3 compound at high temperatures.

Phase Relations in the System Cu-Gd-O and Gibbs Energy of Formation of CuGd204

The phase relations in the system Cu-Gd-O have been determined at 1273 K by X-ray diffrac- tion, optical microscopy, and electron microprobe analysis of samples equilibrated in quartz ampules and in pure oxygen. Only one ternary compound, CuGd2O4, was found to be stable. The Gibbs free energy of formation of this compound has been measured using the solid-state cell Pt, Cu2O + CuGd2O4 + Gd2O3 // (Y2O3) ZrO2 // CuO + Cu2O, Pt in the temperature range of 900 to 1350 K. For the formation of CuGd2O4 from its binary component oxides, CuO (s) + Gd2O3 (s) → CuGd2O4 (s) ΔG° = 8230 - 11.2T (±50) J mol-1 Since the formation is endothermic, CuGd2O4 becomes thermodynamically unstable with respect to CuO and Gd2O3 below 735 K. When the oxygen partial pressure over CuGd2O4 is lowered, it decomposes according to the reaction 4CuGd2O4 (s) → 4Gd2O3 (s) + 2Cu2O (s) + O2 (g) for which the equilibrium oxygen potential is given by Δμo 2 = −227,970 + 143.2T (±500) J mol−1 An oxygen potential diagram for the system Cu-Gd-O at 1273 K is presented.

Phase relations in the systems Cu–O–R2O3(R = Tm, Lu) and Gibbs energies of formation of Cu2R2O5 compounds

The phase relations in the systems Cu–O–R2O3(R = Tm, Lu) have been determined at 1273 K by X-ray diffraction, optical microscopy and electron probe microanalysis of samples equilibrated in evacuated quartz ampules and in pure oxygen. Only ternary compounds of the type Cu2R2O5 were found to be stable. The standard Gibbs energies of formation of the compounds have been measured using solid-state galvanic cells of the type, Pt|Cu2O + Cu2R2O5+ R2O3‖(Y2O3)ZrO2‖CuO + Cu2O‖Pt in the temperature range 950–1325 K. The standard Gibbs energy changes associated with the formation of Cu2R2O5 compounds from their binary component oxides are: 2CuO(s)+ Tm2O3(s)→Cu2Tm2O5(s), ΔG°=(10400 – 14.0 T/K)± 100 J mol–1, 2CuO(s)+ Lu2O3(s)→Cu2Lu2O5(s), ΔG°=(10210 – 14.4 T/K)± 100 J mol–1 Since the formation is endothermic, the compounds become thermodynamically unstable with respect to component oxides at low temperatures, Cu2Tm2O5 below 743 K and Cu2Lu2O5 below 709 K. When the chemical potential of oxygen over the Cu2R2O5 compounds is lowered, they decompose according to the reaction, 2Cu2R2O5(s)→2R2O3(s)+ 2Cu2O(s)+ O2(g) The equilibrium oxygen potential corresponding to this reaction is obtained from the emf. Oxygen potential diagrams for the Cu–O–R2O3 systems at 1273 K are presented.

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.

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