Search

In their paper [1], Doulliez and Rao present algorithms that solve two flow problems for a single source, multi-terminal network. The first problem that they solve is the construction of a flow that maximizes the value of t, where the demand at each sink is a nondecreasing, linear function of t. Given such a flow, the second problem that they solve is the construction of a flow that maximizes the value of t when the capacity of an arc is reduced. This paper supplies a finiteness proof for the first algorithm and sketches a finiteness proof for the second algorithm. The proofs are based on the well-known fact that a network possesses only a finite number of different spanning trees. [ABSTRACT FROM AUTHOR]

Nonlinear, i.e., pseudo-concave, programming algorithms attempt to maximize an objective function ƒ(x) subject to x in a feasible set. Large step algorithms seek this maximum by recursively generating both a sequence of points {xk} and a sequence of directions {sk}. Given a point xk and a direction sk the next point xk+1 is the feasible point that gives the largest value to the objective function along the ray emanating from xk in the direction sk. The key difference among large step procedures is in the choice of sk. This paper explores several means for selecting the direction sk. Some of these methods are particularly suited for large scale systems with a large number of constraints, as they decompose the problem and require the solution of only a finite number of subproblems. These algorithms have an interesting interpretation in terms of management by exception. They also lead naturally into a discussion of jamming or zigzagging; that phenomenon which plagues all large step methods and can lead to non-convergence. Jamming is studied for its cause and curve via an example and counter-example. For linear constraints a special large step method which proceeds by suboptimization in manifolds is proposed that avoids jamming. It is then shown that the DANTZIG quadratic programming algorithm is a special case of this method. A straightforward geometric proof of the Dantzig method is then possible. [ABSTRACT FROM AUTHOR]

Controlled stationary Markov chains with a finite number of states and possible actions and continuous time have been studied by many authors. It is well known that a control maximizing the expected reward in a finite time interval can be obtained from the equation of dynamic programming, and that there exists a stationary control giving maximal (discounted or average) reward in an infinite time interval. In this paper controlled Markov chains whose transition probabilities are periodic in time are considered. It is shown that there exists a periodic control giving maximal expected future reward, and that it can be approximatively calculated by making a discretization in time. An example of a system that can be described by such a process is a service system or an inventory whose input is, e.g., a Poisson process with an intensity that varies seasonally. [ABSTRACT FROM AUTHOR]