Distributed versus Centralized Storage and Control for Parallel Branch and Bound: Mixed Integer Programming on the CM-5

This paper describes parallel, non-shared-memoryimplementation of the classical general mixed integer branch and boundalgorithm, with experiments on the CM-5 family of parallel processors. Themain issue in such an implementation is whether task scheduling and certaindata-storage functions should be handled by a single processor, orspread among multiple processors. The centralized approach riskscreating processing bottlenecks, while the more decentralizedimplementations differ more from the fundamental serial algorithm.Extensive computational tests on standard MIPLIB problems comparecentralized, clustered, and fully decentralized task scheduling methods, using a novel combination of random work scattering and rendezvous-basedglobal load balancing, along with a distributed control by tokentechnique. Further experiments compare centralized and distributedschemes for storing heuristic pseudo-cost branching data. The distributed storage method is based on continual asynchronous reductionalong a tree of redundant storage sites. On average, decentralized taskscheduling appears at least as effective as central control, butpseudo-cost storage should be kept as centralized as possible.     

A unified framework for pull control mechanisms in multi‐stage manufacturing systems

This paper presents a unified framework for pull production control mechanisms in multistage manufacturing systems. A pull production control mechanism in a multistage manufacturing system is a mechanism that coordinates the release of parts into each stage of the system with the arrival of customer demands for final products. Four basic pull production control mechanisms are presented: Base Stock, Kanban, Generalized Kanban, and Extended Kanban. It is argued that on top of any of these basic coordination mechanisms, a local mechanism to control the workinprocess in each stage may be superimposed. Several cases of basic stage coordination mechanisms with stage workinprocess control are presented, and several production control systems that have appeared in the literature are shown to be equivalent to some of these cases.     

The Residue of p(N) Modulo Small Primes

For primes we obtain a simple formula for p(N) (mod ) as a weighted sum over -square affine partitions of N. When {3,5,7,11}, the weights are explicit divisor functions. The Ramanujan congruences modulo 5, 7, 11, 25, 49, and 121 follow immediately from these formulae.     

Completeness and Admissibility for General Heuristic Search Algorithms—A Theoretical Study: Basic Concepts and Proofs

We propose a formal generalization for various works dealing with Heuristic Search in State Graphs. This generalization focuses on the properties of the evaluation functions, on the characteristics of the state graphs, on the notion of path length, on the procedures that control the node expansions, on the rules that govern the update operations. Consequently, we present the algorithm family and the sub-family Ã, which include Nilsson's A or A_* and many of their successors such as HPA, B, A ^* , A, C, BF^*, B, IDA^*, D, A^**, SDW. We prove general theorems about the completeness and the sub-admissibility that widely extend the previous results and provide a theoretical support for using diverse kinds of Heuristic Search algorithms in enlarged contexts, specially when the state graphs and the evaluation functions are less constrained than ordinarily.     

Partially Observed Analytic Systems with Fully Unbounded Actuators and Sensors-FEM Algorithms

Partially observed control systems described by analytic semigroup are considered. Finite-dimensional feedback control based on FEM approximations and accounting for incomplete observations is constructed. It is shown that this feedback control provides uniform stability (in time) of the originally unstable system. The main novel feature of the problem is that both—control and observation operators—are modeled by fully unbounded operators as they frequently arise in modeling of smart sensors and actuators. This contributes to technical difficulties at the level of perturbation theory for analytic semigroups. It is shown that a careful and rather special approximation in the area of support of the unbounded control/observation operators allows to obtain the right stability estimates. Theoretical results are illustrated with several examples of control problems governed by heat and plate equations.     

Controlled and optimally controlled multiplexing systems: A numerical exploration

Large controlled multiplexing systems are approximated by diffusion type processes yielding a very efficient way of approximation and good numerical methods. The limit equations are an efficient aggregation of the original system, and provide the basis of the actual numerical approximation to the control problem. The numerical approximations have the structure of the original problem, but are generally much simpler. The control can occur in a variety of places; e.g., leaky bucket controllers, control of marked cells at the transmitter buffer, or control of the transmitter speed. From the point of view of the limit equations, those are equivalent. Various forms of the optimal control problem are explored, where the main aim is to control or balance the losses at the control with those due to buffer overflow. It is shown that much can be saved via the use of optimal controls or reasonable approximations to them. We discuss systems with one to three classes of sources, various aggregation methods and control approximation schemes. There are qualitative comparisons of various systems with and without control and a discussion of the variations of control and performance as the systems data and control bounds vary. The approach is a very useful tool for providing both qualitative and quantitative information which would be hard to get otherwise. The results have applications to various forms of the ATM and broadband integrated data networks.The work was partially supported by AFOSR-91-0375 and (AFOSR) F49620-92-J-088-1DEF.The work was partially supported by grants (AFOSR) F49620-92-J-008-1DEF, AFOSR-91-03750.This work was partially supported by DAAH04-93-0070 (ARO) and AFOSR-91-0375.     

A generalization of the prolate spheroidal wave functions

Many systems of orthogonal polynomials and functions are bases of a variety of function spaces, such as the Hermite and Laguerre functions which are orthogonal bases of and and the Jacobi polynomials which are an orthogonal basis of a weighted The associated Legendre functions, and more generally, the spheroidal wave functions are also an orthogonal basis of

The prolate spheroidal wave functions, which are a special case of the spheroidal wave functions, possess a very surprising and unique property. They are an orthogonal basis of both and a subspace of known as the Paley-Wiener space of bandlimited functions. They also satisfy a discrete orthogonality relation. No other system of classical orthogonal functions is known to possess this strange property. This raises the question of whether there are other systems possessing this property.

The aim of the article is to answer this question in the affirmative by providing an algorithm to generate such systems and then demonstrating the algorithm by a new example.

     

Distributed control for cooperative systems involving parabolic operators with an infinite number of variables

^** Email: serraghm{at}yahoo.com The optimal control for cooperative systems involving parabolicoperators with an infinite number of variables is considered.First the existence and uniqueness of the states are proved;then the necessary and sufficient condition for the controlto be optimal is obtained by a set of inequalities. The controlin our problems is of distributed type and is allowed to bein the Hilbert space (L²(0, T, L²()))ⁿ.     

On a functional inequality connected with quadratic functionals

In the present paper we investigate some functional inequalities which are closely connected with quadratic functionals. In particular, we are interested in inequalities of the type

     

Representations of exceptional simple alternative superalgebras of characteristic 3

We study representations of simple alternative superalgebras and . The irreducible bimodules and bimodules with superinvolution over these superalgebras are classified, and some analogues of the Kronecker factorization theorem are proved for alternative superalgebras that contain and .

     

On polynomial products in nilpotent and solvable Lie groups

We are dealing with Lie groups which are diffeomorphic to , for some . After identifying with , the multiplication on can be seen as a map . We show that if is a polynomial map in one of the two (sets of) variables or , then is solvable. Moreover, if one knows that is polynomial in one of the variables, the group is nilpotent if and only if is polynomial in both its variables.

     

Boundaries of the receding horizon control for interconnected systems

In recent years, the finite-horizon quadratic minimization problem has become popular in process control, where the horizon is constantly rolled back. In this paper, this type of control, which is also called the receding horizon control, is considered for interconnected systems. First, the receding horizon control equations are formulated; then, some stability conditions depending on the interconnection norms and the horizon lengths are presented. For -coupled systems, stability results similar to centralized systems are obtained. For interconnected systems which are not -coupled, the existence of a horizon length and a corresponding stabilizing receding horizon control are derived. Finally, the performance of a locally computed receding horizon control for time-invariant and time-varying systems with different updating intervals is examined in an example.     

Piecewise-Convex Maximization Problems

A function F:Rⁿ R is called a piecewise convex function if it can be decomposed into , where f _j:Rⁿ R is convex for all jM={1,2...,m}. We consider subject to xD. It generalizes the well-known convex maximization problem. We briefly review global optimality conditions for convex maximization problems and carry one of them to the piecewise-convex case. Our conditions are all written in primal space so that we are able to proposea preliminary algorithm to check them.     

Optimization of pressure control in a gas pipeline

We consider the synthesis of an approximate optimal control for a gas transport system when state information is acquired at the points X₁,...,x_n of the interval 0 x during the entire control period 0 t . This means that the functions (t, x₁),...,(t, x_n) characterizing the state of the controlled system at the points X₁,...,x_n are known. The approximate optimal control is determined using this information. We solve the control optimization problem which, for a given deviation of the approximate optimal control from the optimum, produces a minimum-information approximate optimal control, i.e., a control determined by a formula with the least number of points x_i, and establishes the location of these points.Translated from Vychislitel'naya i Prikladnaya Matematika, No. 63, pp. 118–123, 1987.     

Experiments with an interactive paired comparison simplex method for molp problems

In this paper, an interactive paired comparison simplex based method formultipleobjectivelinearprogramming (MOLP) problems is developed and compared to other interactive MOLP methods. Thedecisionmaker (DM)'s utility function is assumed to be unknown, but is an additive function of his known linearized objective functions. A test for utilityefficiency for MOLP problems is developed to reduce the number of efficient extreme points generated and the number of questions posed to the DM. The notion of strength ofpreference is developed for the assessment of the DM's unknown utility function where he can express his preference for a pair of extreme points as strong, weak, or almost indifferent. The problem of inconsistency of the DM is formalized and its resolution is discussed. An example of the method and detailed computational results comparing it with other interactive MOLP methods are presented. Several performance measures for comparative evaluations of interactive multiple objective programming methods are also discussed.All rights reserved. This study, or parts thereof, may not be reproduced in any form without written permission of the authors.     

Solution of Some Weight Problems for the Riemann–Liouville and Weyl Operators

The necessary and sufficient conditions are found for the weight function v, which provide the boundedness and compactness of the Riemann–Liouville operator R from L ^p to . The criteria are also established for the weight function w, which guarantee the boundedness and compactness of the Weyl operator W from to L ^q.     

Control of systems to sets and their interiors

For a closed target setS ⁿ and a control system (formulated as a differential inclusion and defined nearS), the present paper considers a sufficient condition for the property that every point nearS can be steered toS in finite time by some trajectory of the system. Estimates are obtained revealing how fast some such trajectory is nearing the target. A strong form of this condition is shown to imply that every trajectory of the system hits the target. With a further assumption on the target setS, we also consider conditions that guarantee that some trajectories enter the interior ofS.This work was supported by the Natural Sciences and Engineering Research Council of Canada and by FCAR, Québec, Canada.