Lyapunov formulation of the ISS cyclic-small-gain theorem for hybrid dynamical networks

This paper presents a Lyapunov-based cyclic-small-gain theorem for the hybrid dynamical networks composed of input-to-state stable (ISS) subsystems whose motions may be continuous, impulsive or piecewise constant on the time-line. On the one hand, it is shown that hybrid dynamic networks with interconnection gains less than the identity function are ISS by means of Lyapunov functions. Additionally, an ISS-Lyapunov function for the total network is constructed using the ISS-Lyapunov functions of the subsystems. On the other hand, a novel result of this paper shows that a hybrid dynamic network satisfying the cyclic-small-gain condition can be transformed into one with interconnection gains less than the identity. In sharp contrast with several previously known results, the impulses of the subsystems are time triggered and the impulsive times for different subsystems may be different.     

Lyapunov formulation of the ISS cyclic-small-gain theorem for hybrid dynamical networks

This paper presents a Lyapunov-based cyclic-small-gain theorem for the hybrid dynamical networks composed of input-to-state stable (ISS) subsystems whose motions may be continuous, impulsive or piecewise constant on the time-line. On the one hand, it is shown that hybrid dynamic networks with interconnection gains less than the identity function are ISS by means of Lyapunov functions. Additionally, an ISS-Lyapunov function for the total network is constructed using the ISS-Lyapunov functions of the subsystems. On the other hand, a novel result of this paper shows that a hybrid dynamic network satisfying the cyclic-small-gain condition can be transformed into one with interconnection gains less than the identity. In sharp contrast with several previously known results, the impulses of the subsystems are time triggered and the impulsive times for different subsystems may be different.     

Multicommodity flow models for spanning trees with hop constraints

In this paper we compare the linear programming relaxations of undirected and directed multicommodity flow formulations for the terminal layout problem with hop constraints. Hop constraints limit the number of hops (links) between the computer center and any terminal in the network. These constraints model delay constraints since a smaller number of hops decreases the maximum delay transmission time in the network. They also model reliability constraints because with a smaller number of hops there is a lower route loss probability. Hop constraints are easily modelled with the variables involved in multicommodity flow formulations. We give some empirical evidence showing that the linear programming relaxation of such formulations give sharp lower bounds for this hop constrained network design problem. On the other hand, these formulations lead to very large linear programming models. Therefore, for bounding purposes we also derive several lagrangean based procedures from a directed multicommodity flow formulation and present some computational results taken from a set of instances with up to 40 nodes.     

The problem of conflicting control with mixed constraints

The control problem for a linear dynamical system is considered at a minimax of the terminal quality index. Feasible controls are simultaneously restricted by geometrical constraints and by integrated momentum constraints, the latter being thought of as a store of control resources. The problem is formalized as a differential game [1–4] using concepts [5–8] developed at Ekaterinburg. Here, because of the geometrical constraints, the momentum formulation and its associated difficulties [2–4] do not appear. On the other hand the presence of the integral restrictions leads to the appearance of additional variables whose evolution describes the dynamics of the expenditure of the control resources. These variables are subject to phase restrictions, which is a peculiarity of the problem. A reasonably informative picture and a class of strategies for which the given game has a value and a saddle point are given. A constructive method for computing the value function of the game and constructing optimal strategies is presented. This method is conceptually related to the construction of a stochastic programming synthesis [5] and is based on the recursive construction of upper-convex envelopes for certain auxiliary functions. The possibility of exchanging the minimum and maximum operations over the resource parameters when calculating the value of the game using these procedure is established.     

Entropy and set cardinality inequalities for partition‐determined functions

A new notion of partition‐determined functions is introduced, and several basic inequalities are developed for the entropies of such functions of independent random variables, as well as for cardinalities of compound sets obtained using these functions. Here a compound set means a set obtained by varying each argument of a function of several variables over a set associated with that argument, where all the sets are subsets of an appropriate algebraic structure so that the function is well defined. On the one hand, the entropy inequalities developed for partition‐determined functions imply entropic analogues of general inequalities of Plünnecke‐Ruzsa type. On the other hand, the cardinality inequalities developed for compound sets imply several inequalities for sumsets, including for instance a generalization of inequalities proved by Gyarmati, Matolcsi and Ruzsa (2010). We also provide partial progress towards a conjecture of Ruzsa (2007) for sumsets in nonabelian groups. All proofs are elementary and rely on properly developing certain information‐theoretic inequalities. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 40, 399–424, 2012     

The Waveform Relaxation method for systems of differential/algebraic equations

This paper reports efforts towards establishing a parallel numerical algorithm known as Waveform Relaxation (WR) for simulating large systems of differential/algebraic equations. The WR algorithm was established as a relaxation based iterative method for the numerical integration of systems of ODEs over a finite time interval. In the WR approach, the system is broken into subsystems which are solved independently, with each subsystem using the previous iterate waveform as “guesses” about the behavior of the state variables in other subsystems. Waveforms are then exchanged between subsystems, and the subsystems are then resolved repeatedly with this improved information about the other subsystems until convergence is achieved.

In this paper, a WR algorithm is introduced for the simulation of generalized high-index DAE systems. As with ODEs, DAE systems often exhibit a multirate behavior in which the states vary as differing speeds. This can be exploited by partitioning the system into subsystems as in the WR for ODEs. One additional benefit of partitioning the DAE system into subsystems is that some of the resulting subsystems may be of lower index and, therefore, do not suffer from the numerical complications that high-index systems do. These lower index subsystems may therefore be solved by less specialized simulations. This increases the efficiency of the simulation since only a portion of the problem must be solved with specially tailored code. In addition, this paper established solvability requirements and convergence theorems for varying index DAE systems for WR simulation.     

The Gradient Projection Method with Exact Line Search

The gradient projection algorithm for function minimization is often implemented using an approximate local minimization along the projected negative gradient. On the other hand, for some difficult combinational optimization problems, where a starting guess may be far from a solution, it may be advantageous to perform a nonlocal (exact) line search. In this paper we show how to evaluate the piece-wise smooth projection associated with a constraint set described by bounds on the variables and a single linear equation. When the NP hard graph partitioning problem is formulated as a continuous quadratic programming problem, the constraints have this structure.     

Strong polynomiality of resource constraint propagation

Constraint-based schedulers have been widely successful in tackling complex, disjunctive, and cumulative scheduling applications by combining tree search and constraint propagation. The constraint-propagation step is a fixpoint algorithm that applies pruning operators to tighten the release and due dates of activities using precedence or resource constraints. A variety of pruning operators for resource constraints have been proposed; they are based on edge finding or energetic reasoning and handle a single resource.

Complexity results in this area are only available for a single application of these pruning operators, which is problematic for at least two reasons. On the one hand, the operators are not idempotent, so a single application is rarely sufficient. On the other hand, the operators are not used in isolation but interact with each other. Existing results thus provide a very partial picture of the complexity of propagating resource constraints in constraint-based scheduling.

This paper aims at addressing these limitations. It studies the complexity of applying pruning operators for resource constraints to a fixpoint. In particular, it shows that: (1) the fixpoint of the edge finder for both release and due dates can be reached in strongly polynomial time for disjunctive scheduling; (2) the fixpoint can be reached in strongly polynomial time for updating the release dates or the due dates but not both for the cumulative scheduling; and (3) the fixpoint of “reasonable” energetic operators cannot be reached in strongly polynomial time, even for disjunctive scheduling and even when only the release dates or the due dates are considered.     

Closed formulas in local sensitivity analysis for some classes of linear and non-linear problems

This paper presents an integrated approach to sensitivity analysis in some linear and non-linear programming problems. Closed formulas for the sensitivities of the objective function and primal and dual variables with respect to all parameters for some classes of problems are obtained. As particular cases, the sensitivities with respect to all data values, i.e., cost coefficients, constraints coefficients and right hand side terms of the constraints are provided for these classes of problems as closed formulas. The method is illustrated by its application to several examples.      

SYNCHRONIZATION STABILITY OF COMPLEX CONNECTED NETWORKS WITH DELAYS

Recently, much work has been devoted to the study of a large-scale complex system described by a network or a graph with complex topology, whose nodes are the elements of the system and whose edges represent the interactions among them. On the other hand, realistic modelling of many large networks with nonlocal interaction inevitably requires connection delays to be taken into account, since they naturally arise as a consequence of finite information transmission and processing speeds among the units. This paper gives the sufficient conditions guaranteeing the local and global synchronization stability of the complex connected networks by using Lyapunov functional.     

Scheduling multiprocessor tasks with chain constraints

This paper is concerned with a new model in deterministic scheduling theory, where certain tasks may require more than one processor at a time. This model is motivated by several applications of multimicroprocessor systems and it has received much attention in the last years. In the paper it is assumed that each task can be processed on any processor subset of a given task-dependent size. Tasks are nonpreemptable and there are precedence constraints among them. It is proved that the problem of minimizing schedule length is NP-hard for three processors even if all the tasks have unit processing times and precedence constraints form a set of chains. Thus, it is unlikely to be solvable in polynomial time. On the other hand, two low order polynomial-time algorithms are given for the m processor case if processor requirements of the tasks in each chain are either uniform or monotonically decreasing (increasing).     

Stochastic programming problems with generalized integrated chance constraints

If the constraints in an optimization problem are dependent on a random parameter, we would like to ensure that they are fulfilled with a high level of reliability. The most natural way is to employ chance constraints. However, the resulting problem is very hard to solve. We propose an alternative formulation of stochastic programs using penalty functions. The expectations of penalties can be left as constraints leading to generalized integrated chance constraints, or incorporated into the objective as a penalty term. We show that the penalty problems are asymptotically equivalent under quite mild conditions. We discuss applications of sample-approximation techniques to the problems with generalized integrated chance constraints and propose rates of convergence for the set of feasible solutions. We will direct our attention to the case when the set of feasible solutions is finite, which can appear in integer programming. The results are then extended to the bounded sets with continuous variables. Additional binary variables are necessary to solve sample-approximated chance-constrained problems, leading to a large mixed-integer non-linear program. On the other hand, the problems with penalties can be solved without adding binary variables; just continuous variables are necessary to model the penalties. The introduced approaches are applied to the blending problem leading to comparably reliable solutions.     

Convergence Criteria for Hierarchical Overlapping Coordination of Linearly Constrained Convex Design Problems

Decomposition of multidisciplinary engineering system design problems into smaller subproblems is desirable because it enhances robustness and understanding of the numerical results. Moreover, subproblems can be solved in parallel using the optimization technique most suitable for the underlying mathematical form of the subproblem. Hierarchical overlapping coordination (HOC) is an interesting strategy for solving decomposed problems. It simultaneously uses two or more design problem decompositions, each of them associated with different partitions of the design variables and constraints. Coordination is achieved by the exchange of information between decompositions. This article presents the HOC algorithm and several new sufficient conditions for convergence of the algorithm to the optimum in the case of convex problems with linear constraints. One of these equivalent conditions involves the rank of the constraint matrix that is computationally efficient to verify. Computational results obtained by applying the HOC algorithm to quadratic programming problems of various sizes are included for illustration.     

An improved local branching approach for train formation planning

The train formation plan (TFP) determines routing and frequency of trains, and assigns the demands to trains. In this paper, an improved local branching algorithm is proposed for the TFP model in Iranian railway. This solution strategy is exact in nature, although it is designed to improve the heuristic behavior of the mixed integer programming (MIP) solver at hand. In the local branching algorithm, additional constraints are built in the model for the binary variables, but in the improved local branching algorithm, the additional constraints are built in the model for integer variables. A state-of-the-art method is applied for parameter tuning using design of experiments approach. To evaluate the proposed solution method, we have simulated and solved twenty test problems. The results show the efficiency and effectiveness of the proposed approach. The proposed algorithm is implemented for Iranian Railway network as a case study.     

Ant colony approach to constrained redundancy optimization in binary systems

This paper presents an ant colony optimization algorithm to address the constrained redundancy allocation problem in order to maximize system reliability for complex binary systems. The constraints involved, though separable, are both linear and non-linear. We couple an adaptive penalty function with the basic ant colony approach to handle highly constrained problems and embed a local search technique to find still better locally optimal solutions. The proposed algorithm has been tested on a large number of problems, containing even up to 500 subsystems, with both fixed and randomly generated parameters. Experimental results demonstrate the advantage of the proposed algorithm to solve similar types of problems.     

Complex analysis in subsystems of second order arithmetic

This research is motivated by the program of Reverse Mathematics. We investigate basic part of complex analysis within some weak subsystems of second order arithmetic, in order to determine what kind of set existence axioms are needed to prove theorems of basic analysis. We are especially concerned with Cauchy’s integral theorem. We show that a weak version of Cauchy’s integral theorem is proved in RCAo. Using this, we can prove that holomorphic functions are analytic in RCAo. On the other hand, we show that a full version of Cauchy’s integral theorem cannot be proved in RCAo but is equivalent to weak König’s lemma over RCAo.     

Commuting differential operators and higher-dimensional algebraic varieties

Several algebro-geometric properties of commutative rings of partial differential operators (PDOs) as well as several geometric constructions are investigated. In particular, we show how to associate a geometric data by a commutative ring of PDOs, and we investigate the properties of these geometric data. This construction is in some sense similar to the construction of a formal module of Baker–Akhieser functions. On the other hand, there is a recent generalization of Sato’s theory, which belongs to the third author of this paper. We compare both approaches to the commutative rings of PDOs in two variables. As a by-product, we get several necessary conditions on geometric data describing commutative rings of PDOs.     

Estimates of reachable sets of multidimensional control systems with nonlinear interconnections

The paper is devoted to the problem of constructing external estimates for the reachable set of a multidimensional control system by means of vector estimators. A system is considered that permits a decomposition into several independent subsystems with simple structure (for example, linear subsystems), which are connected to each other by means of nonlinear interconnections. For each of the subsystems, an external estimate of the reachable set is assumed to be known; this estimate is representable in the form of a level set of some function satisfying a differential inequality. An estimate for the reachable set of the combined system is constructed with the use of estimates for subsystems. The method of deriving the estimates is based on constructing comparison systems for analogs of vector Lyapunov functions (value functions).     

Approximate Analysis of Decentralized, Multi-Stage, Pull-Type Production/Inventory Systems

We consider a decentralized, pull-type manufacturing system with each stage having its own input and output stock keeping activities. Material handling between stages is carried out according to a fixed quantity, non-constant withdrawal cycle. We approximate the system behavior using a two-node decomposition approach, which decomposes the system into smaller subsystems. The analysis of two-node subsystems is achieved using a matrix-recursive approach due to phase-type modeling of certain random variables. Our solution algorithm resolved a major difficulty (due to batch transfers) in the analytical approach to study multi-stage manufacturing systems. We also discuss system behavior and suggest several rules-of-thumb to improve system performance.